LeetCode 热题 HOT 100 算法题参考解法
力扣链接：LeetCode 热题 HOT 100
1. 两数之和
力扣链接：1. 两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> mp = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(mp.containsKey(target-nums[i])){
return new int[]{i,mp.get(target-nums[i])};
}
mp.put(nums[i],i);
}
return new int[]{};
}
}
2. 两数相加
力扣链接：2. 两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
}
3. 无重复字符的最长子串
力扣链接：3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int r=0;
int n = s.length();
int res =0;
for(int i=0;i<n;i++){
while(r<n && !set.contains(s.charAt(r))){
set.add(s.charAt(r));
r++;
}
res = Math.max(res,r-i);
set.remove(s.charAt(i));
}
return res;
}
}
4. 寻找两个正序数组的中位数
力扣链接：4. 寻找两个正序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int len = m+n;
int i = 0,j=0;
int prev =-1,last = -1;
for(int k=0;k<=len/2;k++){
prev = last;
if(i<m && (j>=n || nums1[i]<nums2[j])){
last = nums1[i++];
}else{
last = nums2[j++];
}
}
return len%2==1 ? last : (prev+last)/2.0;
}
}
5. 最长回文子串
力扣链接：5. 最长回文子串
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
for(int i=0;i<2*n-1;i++){
int l = i/2;
int r = l + i%2;
while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){
String t = s.substring(l,r+1);
if(t.length()> res.length()){
res = t;
}
l--;
r++;
}
}
return res;
}
}
class Solution {
public String longestPalindrome(String s) {
if(s==null || s.length() == 0){
return "";
}
int start=0;
int end = 0;
for(int i=0;i<s.length();i++){
int len1 = extend(s,i,i);
int len2 = extend(s,i,i+1);
int len = Math.max(len1,len2);
if(len > end-start){
start = i- (len-1)/2;
end = i+ len/2;
}
}
return s.substring(start,end+1);
}
public int extend(String s,int left,int right){
while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return right-left-1;
}
}
10. 正则表达式匹配
力扣链接：10. 正则表达式匹配
11. 盛最多水的容器
力扣链接：11. 盛最多水的容器
class Solution {
public int maxArea(int[] height) {
int left =0;
int right = height.length-1;
int res = 0;
while(left<right){
if(height[left]<height[right]){
res = Math.max(res,(right-left)*height[left++] );
}else{
res = Math.max(res,(right-left)*height[right--]);
}
}
return res;
}
}
15. 三数之和
力扣链接：15. 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
if(n<3){return res;}
for(int i=0;i<n;i++){
if(nums[i]>0){
break;
}
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int l = i+1;
int r = n-1;
while(l<r){
int sum = nums[i]+nums[l]+nums[r];
if(sum==0){
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(l<r && nums[l] == nums[l+1]) l++;
while(l<r && nums[r] == nums[r-1]) r--;
l++;
r--;
}else if (sum>0){
r--;
}else{
l++;
}
}
}
return res;
}
}
17. 电话号码的字母组合
力扣链接：17. 电话号码的字母组合
class Solution {
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.length() == 0){
return res;
}
Map<Character,String> mp = new HashMap<>();
mp.put('2',"abc");
mp.put('3',"def");
mp.put('4',"ghi");
mp.put('5',"jkl");
mp.put('6',"mno");
mp.put('7',"pqrs");
mp.put('8',"tuv");
mp.put('9',"wxyz");
backtrack(res,digits,mp,0,new StringBuilder());
return res;
}
public void backtrack(List<String> res,String digits,Map<Character,String> mp,int idx,
StringBuilder t){
if(idx == digits.length()){
res.add(new String(t.toString()));
return;
}
char c = digits.charAt(idx);
String words = mp.get(c);
for(char ch : words.toCharArray()){
t.append(ch);
backtrack(res,digits,mp,idx+1,new StringBuilder(t));
t.deleteCharAt(idx);
}
}
}
19. 删除链表的倒数第 N 个结点
力扣链接：19. 删除链表的倒数第 N 个结点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode node = head;
while(n-->0){
node= node.next;
}
ListNode newhead = new ListNode(0,head);
ListNode prev = newhead;
while(node!=null){
node = node.next;
prev = prev.next;
}
prev.next = prev.next.next;
return newhead.next;
}
}
20. 有效的括号
力扣链接：20. 有效的括号
class Solution {
public boolean isValid(String s) {
Map<Character,Character> mp = new HashMap<>();
mp.put('(',')');
mp.put('[',']');
mp.put('{','}');
if(s==null || s.length()==0 || s.length()%2==1){
return false;
}
Stack<Character> stack = new Stack<>();
for(Character c:s.toCharArray()){
if(mp.containsKey(c)){
stack.push(c);
}else{
if(stack.isEmpty() || mp.get(stack.pop()) != c ) return false;
}
}
return stack.isEmpty();
}
}
21. 合并两个有序链表
力扣链接：21. 合并两个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val<list2.val){
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next = mergeTwoLists(list1,list2.next);
return list2;
}
}
}
22. 括号生成
力扣链接：22. 括号生成
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
dfs(res,n,n,new String());
return res;
}
public void dfs(List<String> res,int left,int right,String t){
if(left == 0 && right ==0){
res.add(new String(t));
return;
}
if(left>right || left<0 || right<0){
return;
}
dfs(res,left-1,right,t+"(");
dfs(res,left,right-1,t+")");
}
}
23. 合并K个升序链表
力扣链接：23. 合并K个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length ==0){
return null;
}
return merge(lists,0,lists.length-1);
}
public ListNode merge(ListNode[] lists,int left,int right){
if(left<right){
int mid = (left+right)/2;
ListNode l1 = merge(lists,left,mid);
ListNode l2 = merge(lists,mid+1,right);
return mergeTwoLists(l1,l2);
}
return lists[left];
}
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
if(l1==null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
31. 下一个排列
力扣链接：31. 下一个排列★
32. 最长有效括号
力扣链接：32. 最长有效括号
class Solution {
public int longestValidParentheses(String s) {
int left =0,right = 0,res = 0;
for(char c:s.toCharArray()){
if(c == '(') left++;
if(c == ')') right++;
if(left == right){
res = Math.max(res,2*right);
}
if(right>left){
left = 0;
right = 0;
}
}
left = 0;
right = 0;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)==')'){
right++;
}else{
left++;
}
if(left == right){
res = Math.max(res,2*left);
}
if(left > right){
left = 0;
right = 0;
}
}
return res;
}
}
33. 搜索旋转排序数组
力扣链接：33. 搜索旋转排序数组
将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。
就这样循环.
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if(n==0) return -1;
if(n==1) return nums[0] == target ? 0 : -1;
int l =0;
int r = n-1;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid] == target){
return mid;
}
if(nums[l]<=nums[mid]){
if(target >= nums[l] && target<nums[mid]){
r = mid-1;
}else{
l = mid+1;
}
}else{
if(target> nums[mid] && target<=nums[r]){
l = mid + 1;
}else{
r = mid - 1;
}
}
}
return -1;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
力扣链接：34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length ==0){
return new int[]{-1,-1};
}
int first = first(nums,target);
int second = second(nums,target);
return new int[]{first,second};
}
public int first(int[] nums,int target){
int n = nums.length;
int l = 0;
int r = n-1;
while(l<r){
int mid = (l+r)/2;
if(target < nums[mid]){
r = mid-1;
}else if (target> nums[mid]){
l = mid +1;
}else{
r= mid;
}
}
return nums[l] == target ? l : -1;
}
public int second(int[] nums,int target){
int n = nums.length;
int l = 0;
int r = n-1;
while(l<r){
int mid = (l+r)/2+1;
if(target < nums[mid]){
r = mid-1;
}else if (target> nums[mid]){
l = mid +1;
}else{
l = mid;
}
}
return nums[r] == target ? l : -1;
}
}
39. 组合总和
力扣链接：39. 组合总和
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
dfs(candidates,target,res,0,new ArrayList<>());
return res;
}
public void dfs(int[] candidates,int target,List<List<Integer>> res,int idx,List<Integer> t){
if(target == 0){
res.add(new ArrayList<Integer>(t));
return ;
}
if(idx == candidates.length){
return;
}
dfs(candidates,target,res,idx+1,new ArrayList<>(t));
if(target >=candidates[idx]){
t.add(candidates[idx]);
dfs(candidates,target - candidates[idx],res,idx,new ArrayList<>(t));
}
}
}
42. 接雨水
力扣链接：42. 接雨水
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
for(int i=1;i<n;i++){
left[i] = Math.max(left[i-1],height[i]);
}
right[n-1] = height[n-1];
for(int i=n-2;i>=0;i--){
right[i] = Math.max(right[i+1],height[i]);
}
int res = 0;
for(int i=0;i<n;i++){
res += (Math.min(left[i],right[i])-height[i]);
}
return res;
}
}
class Solution {
public int trap(int[] height) {
int n = height.length;
int left = 0;
int right = n - 1;
int leftMax = 0;
int rightMax = 0;
int res = 0;
while(left <right){
leftMax = Math.max(height[left],leftMax);
rightMax = Math.max(height[right],rightMax);
if(leftMax<rightMax){
res += leftMax-height[left];
left ++;
}else{
res += rightMax-height[right];
right --;
}
}
return res;
}
}
46. 全排列
力扣链接：46. 全排列
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] visit = new boolean[nums.length];
backtrack(res,nums,0,visit,new ArrayList<Integer>());
return res;
}
public void backtrack(List<List<Integer>> res,int[] nums,int idx,boolean[] visit,List<Integer> t){
if(idx == nums.length){
res.add(new ArrayList<>(t));
return ;
}
for(int i=0;i<nums.length;i++){
if(visit[i]) continue;
visit[i]=true;
t.add(nums[i]);
backtrack(res,nums,idx+1,visit,t);
t.remove(idx);
visit[i] = false;
}
}
}
48. 旋转图像
力扣链接：48. 旋转图像
class Solution {
public void rotate(int[][] matrix) {
int m = matrix.length-1;
int n = matrix[0].length-1;
for(int i=0;i<=m;i++){
for(int j=0;j<=i;j++){
swap(matrix,i,j,j,i);
}
}
for(int i=0;i<=m;i++){
for(int j=0;j<=n/2;j++){
swap(matrix,i,j,i,n-j);
}
}
}
public void swap(int[][] matrix,int x,int y,int m,int n){
int t = matrix[x][y];
matrix[x][y] = matrix[m][n];
matrix[m][n] = t;
}
}
49. 字母异位词分组
力扣链接：49. 字母异位词分组
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> mp = new HashMap<>();
for(String str : strs){
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> t = mp.getOrDefault(key,new ArrayList<>());
t.add(str);
mp.put(key,t);
}
return new ArrayList<>(mp.values());
}
}
53. 最大子数组和
力扣链接：53. 最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int res = Integer.MIN_VALUE;
for(int num:nums){
pre = Math.max(num,pre+num);
res = Math.max(res,pre);
}
return res;
}
}
55. 跳跃游戏
力扣链接：55. 跳跃游戏
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int max = 0;
for(int i=0;i<n;i++){
if(i<=max){
max = Math.max(max,i+nums[i]);
if(max >= n-1){
return true;
}
}
}
return false;
}
}
56. 合并区间
力扣链接：56. 合并区间
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length==0 || intervals[0].length==0){
return new int[][]{};
}
Arrays.sort(intervals,(x,y)->(x[0]-y[0] != 0 ? x[0]-y[0] : x[1]-y[1]));
List<int[]> merged = new ArrayList<>();
for(int[] t : intervals){
int l = t[0];
int r = t[1];
int n = merged.size();
if(n == 0 || merged.get(n -1)[1]<l){
merged.add(new int[]{l,r});
}else{
merged.get(n-1)[1] = Math.max(merged.get(n-1)[1],r);
}
}
int[][] res = new int[merged.size()][];
for(int i=0;i<merged.size();i++){
res[i] = merged.get(i);
}
return res;
}
}
62. 不同路径
力扣链接：62. 不同路径
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
dp[i][1]=1;
}
for(int i =1;i<=n;i++){
dp[1][i] =1;
}
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
}
64. 最小路径和
力扣链接：64. 最小路径和
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
}
70. 爬楼梯
力扣链接：70. 爬楼梯
class Solution {
public int climbStairs(int n) {
if(n==0 || n==1){
return 1;
}
int a = 1;
int b = 1;
int c = 0;
for(int i=2;i<=n;i++){
c = a+b;
a= b;
b = c;
}
return c;
}
}
72. 编辑距离
力扣链接：72. 编辑距离
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m+1][n+1];
for(int i=0;i<=m;i++){
dp[i][0] = i;
}
for(int i=0;i<=n;i++){
dp[0][i] = i;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1;
}
}
}
return dp[m][n];
}
}
75. 颜色分类
力扣链接：75. 颜色分类
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int p0 = 0;
int p2 = n-1;
int i =p0;
while(i<=p2){
if(nums[i]==0){
swap(nums,i,p0);
p0++;
i++;
}else if(nums[i]==2){
swap(nums,i,p2);
p2--;
}else{
i++;
}
}
}
public void swap(int[] nums,int x,int y){
int t = nums[x];
nums[x] = nums[y];
nums[y] = t;
}
}
76. 最小覆盖子串
力扣链接：76. 最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> s_mp = new HashMap<>();
Map<Character,Integer> t_mp = new HashMap<>();
for(int i=0;i<t.length();i++){
t_mp.put(t.charAt(i),t_mp.getOrDefault(t.charAt(i),0)+1);
}
String res ="";
int len = Integer.MAX_VALUE;
int cnt = 0;
int j = 0;
for(int i=0;i<s.length();i++){
char rc = s.charAt(i);
s_mp.put(rc,s_mp.getOrDefault(rc,0)+1);
if(t_mp.containsKey(rc) && s_mp.get(rc) <= t_mp.get(rc)){
cnt++;
}
char lc = s.charAt(j);
while(j<i && (!t_mp.containsKey(lc) || s_mp.get(lc) > t_mp.get(lc))){
s_mp.put(lc,s_mp.get(lc)-1);
j++;
lc = s.charAt(j);
}
if(cnt == t.length() && i-j+1<len){
len = i-j+1;
res= s.substring(j,i+1);
}
}
return res;
}
}
import java.util.HashMap;
class Solution {
public String minWindow(String s, String t) {
HashMap<Character,Integer> need = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for (char ch : t.toCharArray()){
need.put(ch,need.getOrDefault(ch,0)+1);
}
int start = 0;
int valid = 0;
int left = 0;
int right = 0;
int len = Integer.MAX_VALUE;
while (right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.getOrDefault(d,0)-1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}
}
78. 子集
力扣链接：78. 子集
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums.length == 0){
return res;
}
res.add(new ArrayList<>());
for(int i=0;i<nums.length;i++){
int size = res.size();
for(int j=0;j<size;j++){
List<Integer> list = new ArrayList<>(res.get(j));
list.add(nums[i]);
res.add(list);
}
}
return res;
}
}
79. 单词搜索
力扣链接：79. 单词搜索
class Solution {
public boolean exist(char[][] board, String word) {
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(dfs(board,word,0,i,j)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board,String word,int idx,int x,int y){
if(x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y] != word.charAt(idx)){
return false;
}
if(idx == word.length()-1){
return true;
}
board[x][y] = '\0';
boolean res = dfs(board,word,idx+1,x+1,y) || dfs(board,word,idx+1,x,y+1)
|| dfs(board,word,idx+1,x-1,y) || dfs(board,word,idx+1,x,y-1);
board[x][y] = word.charAt(idx);
return res;
}
}
84. 柱状图中最大的矩形
力扣链接：84. 柱状图中最大的矩形
85. 最大矩形
力扣链接：85. 最大矩形
94. 二叉树的中序遍历
力扣链接：94. 二叉树的中序遍历
class Solution {
List<Integer> list= new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return list;
}
public void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
}
96. 不同的二叉搜索树
力扣链接：96. 不同的二叉搜索树
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i] += (dp[j-1] * dp[i-j]);
}
}
return dp[n];
}
}
98. 验证二叉搜索树
力扣链接：98. 验证二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root,long left,long right){
if(root == null){
return true;
}
if(root.val <= left || root.val >= right){
return false;
}
return isValidBST(root.left,left,root.val) && isValidBST(root.right,root.val,right);
}
}
102. 二叉树的层序遍历
力扣链接：102. 二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null){
return res;
}
Queue<TreeNode> qu = new LinkedList<>();
qu.offer(root);
while(!qu.isEmpty()){
int size = qu.size();
List<Integer> t = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode node = qu.poll();
t.add(node.val);
if(node.left != null){
qu.offer(node.left);
}
if(node.right!=null){
qu.offer(node.right);
}
}
res.add(t);
}
return res;
}
}
104. 二叉树的最大深度
力扣链接：104. 二叉树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
return depth(root);
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
return 1+Math.max(left,right);
}
}
105. 从前序与中序遍历序列构造二叉树
力扣链接：105. 从前序与中序遍历序列构造二叉树
class Solution {
int[] preorder;
Map<Integer,Integer> mp = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0;i<inorder.length;i++){
mp.put(inorder[i],i);
}
return build(0,0,inorder.length-1);
}
public TreeNode build(int root,int left,int right){
if(left>right){
return null;
}
TreeNode node = new TreeNode(preorder[root]);
int i = mp.get(preorder[root]);
node.left = build(root+1,left,i-1);
node.right = build(root+1+i-left,i+1,right);
return node;
}
}
114. 二叉树展开为链表
力扣链接：114. 二叉树展开为链表
class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
TreeNode cur = root;
while(cur!=null){
if(cur.left !=null){
TreeNode next = cur.left;
TreeNode prev = next;
while(prev.right!=null){
prev = prev.right;
}
prev.right = cur.right;
cur.right = next;
cur.left = null;
}
cur = cur.right;
}
}
}
121. 买卖股票的最佳时机
力扣链接：121. 买卖股票的最佳时机
class Solution {
public int maxProfit(int[] prices) {
int pre = Integer.MAX_VALUE;
int res = 0;
for(int p:prices){
pre = Math.min(pre,p);
res = Math.max(p-pre,res);
}
return res;
}
}
124. 二叉树中的最大路径和
力扣链接：124. 二叉树中的最大路径和
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return res;
}
public int maxGain(TreeNode root){
if(root == null){
return 0;
}
int left = Math.max(maxGain(root.left),0) ;
int right = Math.max(maxGain(root.right),0);
int t = left + right + root.val;
res = Math.max(t,res);
return root.val + Math.max(left,right);
}
}
128. 最长连续序列
力扣链接：128. 最长连续序列
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num:nums){
set.add(num);
}
int res = 0;
for(int num:nums){
if(!set.contains(num-1)){
int t = 0;
int curr = num;
while(set.contains(curr)){
t++;
curr ++;
}
res = Math.max(res,t);
}
}
return res;
}
}
136. 只出现一次的数字
力扣链接：136. 只出现一次的数字
class Solution {
public int singleNumber(int[] nums) {
int n = 0;
for(int num:nums){
n ^= num;
}
return n;
}
}
139. 单词拆分
力扣链接：139. 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && set.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
141. 环形链表
力扣链接：141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if(head ==null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow!=fast){
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
142. 环形链表 II
力扣链接：142. 环形链表 II
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(true){
if(fast == null || fast.next ==null){
return null;
}
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
fast = head;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
146. LRU 缓存
力扣链接：146. LRU 缓存
class LRUCache {
class Node{
int key;
int value;
Node prev;
Node next;
public Node(){}
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
Map<Integer,Node> mp = new HashMap<>();
Node head;
Node tail;
int capacity;
int size = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if(!mp.containsKey(key)){
return -1;
}else{
Node node = mp.get(key);
deleteNode(node);
moveToHead(node);
return node.value;
}
}
public void put(int key, int value) {
if(!mp.containsKey(key)){
if(capacity == size){
Node node = deleteTail();
mp.remove(node.key);
size--;
}
Node node = new Node(key,value);
mp.put(key,node);
moveToHead(node);
size++;
}else{
Node node = mp.get(key);
node.value = value;
deleteNode(node);
moveToHead(node);
}
}
public void deleteNode(Node node){
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
public void moveToHead(Node node){
node.prev = head;
node.next = head.next;
head.next = node;
node.next.prev = node;
}
public Node deleteTail(){
Node node = tail.prev;
deleteNode(node);
return node;
}
}
148. 排序链表
力扣链接：148. 排序链表
# 有个小细节，无头节点链表的快慢指针，快指针要快慢指针一步，不然slow指针不能从中间分隔
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode fast = head;
ListNode slow = head;
while(fast.next!=null && fast.next.next !=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode t = slow.next;
slow.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(t);
ListNode res = new ListNode();
ListNode p = res;
while(l1 !=null && l2 !=null){
if(l1.val < l2.val){
p.next = l1;
l1=l1.next;
}else{
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
p.next = (l1==null) ? l2 :l1;
return res.next;
}
}
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast!=null && fast.next !=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode t = slow.next;
slow.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(t);
return merge(l1,l2);
}
public ListNode merge(ListNode l1,ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = merge(l1.next,l2);
return l1;
}else{
l2.next = merge(l1,l2.next);
return l2;
}
}
}
152. 乘积最大子数组
力扣链接：152. 乘积最大子数组
class Solution {
public int maxProduct(int[] nums) {
int res = Integer.MIN_VALUE,max = 1,min = 1;
for(int num:nums){
if(num<0){
int t = max;
max = min;
min = t;
}
max = Math.max(num,num*max);
min = Math.min(num,num*min);
res = Math.max(res,max);
}
return res;
}
}
155. 最小栈
力扣链接：155. 最小栈
class MinStack {
Stack<Integer> stack;
Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
min_stack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
min_stack.push(Math.min(val,min_stack.peek()));
}
public void pop() {
stack.pop();
min_stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}
}
160. 相交链表
力扣链接：160. 相交链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p!=q){
p = (p==null) ? headB : p.next;
q = (q==null) ? headA : q.next;
}
return p;
}
}
169. 多数元素
力扣链接：169. 多数元素
class Solution {
public int majorityElement(int[] nums) {
int cnt = 0;
int res = nums[0];
for(int num:nums){
if(cnt == 0){
res = num;
}
if(num == res){
cnt++;
}else{
cnt--;
}
}
return res;
}
}
198. 打家劫舍
力扣链接：198. 打家劫舍
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==0) return 0;
if(n==1) return nums[0];
int[] dp = new int[n+1];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<n;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}
}
200. 岛屿数量
力扣链接：200. 岛屿数量
class Solution {
public int numIslands(char[][] grid) {
int cnt = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]=='1'){
dfs(grid,i,j);
cnt++;
}
}
}
return cnt;
}
public void dfs(char[][] grid,int x,int y){
if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y] == '0'){
return;
}
grid[x][y] = '0';
dfs(grid,x+1,y);
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
}
206. 反转链表
力扣链接：206. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newhead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newhead;
}
}
207. 课程表
力扣链接：207. 课程表
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indeg = new int[numCourses];
List<List<Integer>> list = new ArrayList<>();
for(int i=0;i<numCourses;i++){
list.add(new ArrayList<>());
}
for(int[] e : prerequisites){
indeg[e[0]]++;
list.get(e[1]).add(e[0]);
}
Queue<Integer> qu = new LinkedList<>();
for(int i=0;i<numCourses;i++){
if(indeg[i]==0){
qu.offer(i);
}
}
while(!qu.isEmpty()){
Integer node = qu.poll();
numCourses--;
for(int t : list.get(node)){
indeg[t]--;
if(indeg[t]==0){
qu.offer(t);
}
}
}
return numCourses == 0;
}
}
208. 实现 Trie (前缀树)
力扣链接：208. 实现 Trie (前缀树)
class Trie {
Trie[] child;
boolean isEnd;
public Trie() {
child = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for(char c : word.toCharArray()){
if(node.child[c-'a']==null){
node.child[c-'a'] = new Trie();
}
node = node.child[c-'a'];
}
node.isEnd = true;
}
public Trie prefixWith(String word){
Trie node = this;
for(char c : word.toCharArray()){
if(node.child[c-'a']==null){
return null;
}
node = node.child[c-'a'];
}
return node;
}
public boolean search(String word) {
Trie node = prefixWith(word);
return node!=null && node.isEnd;
}
public boolean startsWith(String prefix) {
return prefixWith(prefix)==null ? false: true;
}
}
215. 数组中的第K个最大元素
力扣链接：215. 数组中的第K个最大元素
class Solution {
public int findKthLargest(int[] nums, int k) {
return find(nums,0,nums.length-1,nums.length -k);
}
public int find(int[] nums,int l,int r,int k){
int j = partition(nums,l,r);
if(j== k){
return nums[j];
}
return k<j ? find(nums,l,j-1,k) : find(nums,j+1,r,k);
}
public int partition(int[] nums,int l,int r){
int t = nums[l];
while(l<r){
while(l<r && nums[r]>=t){
r--;
}
nums[l] = nums[r];
while(l<r && nums[l]<=t){
l++;
}
nums[r] = nums[l];
}
nums[l] = t;
return l;
}
}
221. 最大正方形
力扣链接：221. 最大正方形
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int res = 0;
for(int i=0;i<m;i++){
dp[i][0] = matrix[i][0] - '0';
res = Math.max(res,dp[i][0]);
}
for(int i=0;i<n;i++){
dp[0][i] = matrix[0][i] - '0';
res = Math.max(res,dp[0][i]);
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j] == '1'){
dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
res = Math.max(dp[i][j],res);
}
}
}
return res*res;
}
}
class Solution {
public int maximalSquare(char[][] matrix) {
int res = 0;
if(matrix.length ==0 || matrix[0].length == 0){
return 0;
}
int m = matrix.length,n= matrix[0].length;
int[][] dp = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1'){
if(i==0 || j==0){
dp[i][j] = 1;
}else{
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
}
res = Math.max(res,dp[i][j]);
}
}
}
return res*res;
}
}
226. 翻转二叉树
力扣链接：226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
234. 回文链表
力扣链接：234. 回文链表
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head.next;
ListNode slow = head;
while(fast !=null && fast.next !=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode l1 = head;
ListNode l2 = reverse(slow);
slow.next = null;
while(l1!=null && l2!=null && l1.val == l2.val){
l1 = l1.next;
l2 = l2.next;
}
return l1==null ;
}
public ListNode reverse(ListNode head){
ListNode newhead = new ListNode();
while(head !=null){
ListNode cur = head;
head= head.next;
cur.next = newhead.next;
newhead.next = cur;
}
return newhead.next;
}
}
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null || head.next == null){
return true;
}
ListNode fast = head;
ListNode slow = head;
while(fast.next!=null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode t = reverse(slow.next);
slow.next = null;
ListNode p = head;
ListNode q = t;
boolean flg = true;
while(q!=null){
if(flg && p.val != q.val){
flg = false;
}
p = p.next;
q = q.next;
}
reverse(t);
return flg;
}
public ListNode reverse(ListNode head){
ListNode prev = null;
ListNode curr = head;
while(curr !=null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
236. 二叉树的最近公共祖先
力扣链接：236. 二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null){
return right;
}
if(right == null){
return left;
}
return root;
}
}
238. 除自身以外数组的乘积
力扣链接：238. 除自身以外数组的乘积
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = 1;
for(int i=1;i<n;i++){
left[i] = left[i-1]*nums[i-1];
}
right[n-1] = 1;
for(int i = n-2;i>=0;i--){
right[i] = right[i+1]*nums[i+1];
}
for(int i=0;i<n;i++){
nums[i] = left[i]* right[i];
}
return nums;
}
}
239. 滑动窗口最大值
力扣链接：239. 滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n-k+1];
Deque<Integer> qu = new LinkedList<>();
for(int i=0;i<n;i++){
while(!qu.isEmpty() && nums[qu.peekLast()] < nums[i]){
qu.pollLast();
}
qu.offerLast(i);
if(qu.peekFirst() <= i-k){
qu.pollFirst();
}
if(i+1>=k){
res[i+1-k] = nums[qu.peekFirst()];
}
}
return res;
}
}
240. 搜索二维矩阵 II
力扣链接：240. 搜索二维矩阵 II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i = 0;
int j = n-1;
while(i<m && j>=0){
if(matrix[i][j]==target){
return true;
}
if(matrix[i][j]<target){
i++;
}else{
j--;
}
}
return false;
}
}
279. 完全平方数
力扣链接：279. 完全平方数
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j*j<=i;j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
283. 移动零
力扣链接：283. 移动零
class Solution {
public void moveZeroes(int[] nums) {
int p = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
int t = nums[i];
nums[i] = nums[p];
nums[p] = t;
p++;
}
}
}
}
287. 寻找重复数
力扣链接：287. 寻找重复数
class Solution {
public int findDuplicate(int[] nums) {
int n =nums.length;
int fast = 0;
int slow = 0;
while(true){
fast = nums[nums[fast]];
slow = nums[slow];
if(fast==slow){
break;
}
}
fast = 0;
while(fast!=slow){
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}
297. 二叉树的序列化与反序列化
力扣链接：297. 二叉树的序列化与反序列化
300. 最长递增子序列
力扣链接：300. 最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int res=1;
Arrays.fill(dp,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
res = Math.max(dp[i],res);
}
return res;
}
}
301. 删除无效的括号
力扣链接：301. 删除无效的括号
309. 最佳买卖股票时机含冷冻期
力扣链接：309. 最佳买卖股票时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
//dp[i][0] : 今天不持股，今天没卖
//dp[i][1] : 今天不持股，今天卖的
//dp[i][2] : 持股
int[][] dp = new int[n][3];
dp[0][0]=0;
dp[0][1]=0;
dp[0][2]=-prices[0];
for(int i=1;i<n;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][2]+prices[i];
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0]-prices[i]);
}
return Math.max(dp[n-1][0],dp[n-1][1]);
}
}
312. 戳气球
力扣链接：312. 戳气球
322. 零钱兑换
力扣链接：322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp =new int[amount+1];
int n = coins.length;
Arrays.fill(dp,amount+1);
dp[0] = 0;
for(int i=0;i<n;i++){
for(int j=1;j<=amount;j++){
if(j>=coins[i]){
dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);
}
}
}
return dp[amount]==amount+1?-1:dp[amount];
}
}
337. 打家劫舍 III
力扣链接：337. 打家劫舍 III
// arr[0] : 当前节点不偷
// arr[1] : 当前节点偷
class Solution {
public int rob(TreeNode root) {
int[] arr = func(root);
return Math.max(arr[0],arr[1]);
}
public int[] func(TreeNode root){
if(root == null){
return new int[2];
}
int[] l = func(root.left);
int[] r = func(root.right);
int[] arr = new int[2];
arr[0] = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
arr[1] = l[0] +r[0] + root.val;
return arr;
}
}
338. 比特位计数
力扣链接：338. 比特位计数
class Solution {
public int[] countBits(int n) {
int[] res = new int[n+1];
for(int i=0;i<=n;i++){
res[i] = func(i);
}
return res;
}
public int func(int n){
int cnt = 0;
while(n!=0){
n = (n&(n-1));
cnt++;
}
return cnt;
}
}
347. 前 K 个高频元素
力扣链接：347. 前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> mp = new HashMap<>();
for(int num:nums){
mp.put(num,mp.getOrDefault(num,0)+1);
}
PriorityQueue<int[]> qu = new PriorityQueue<>((x,y)-> x[1]==y[1] ? x[0]-y[0] : x[1]-y[1]);
for(int key:mp.keySet()){
int val = mp.get(key);
if(qu.size()==k){
if(qu.peek()[1]<val){
qu.poll();
qu.offer(new int[]{key,val});
}
}else{
qu.offer(new int[]{key,val});
}
}
int[] res= new int[k];
for(int i=0;i<k;i++){
res[i] = qu.poll()[0];
}
return res;
}
}
394. 字符串解码
力扣链接：394. 字符串解码
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int num =0;
Stack<String> res_stack = new Stack<>();
Stack<Integer> num_stack = new Stack<>();
for(char c : s.toCharArray()){
if(c == '['){
res_stack.push(res.toString());
num_stack.push(num);
res = new StringBuilder();
num = 0;
}else if(c == ']'){
int cur = num_stack.pop();
StringBuilder t = new StringBuilder();
for(int i=0;i<cur;i++){
t.append(res);
}
res = new StringBuilder(res_stack.pop() + t);
}else if(c>='0' && c<='9'){
num = num*10 + c-'0';
}else{
res.append(c);
}
}
return res.toString();
}
}
399. 除法求值
力扣链接：399. 除法求值
406. 根据身高重建队列
力扣链接：406. 根据身高重建队列
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(x,y)->(x[0]==y[0] ? x[1]-y[1] : y[0]-x[0]));
List<int[]> res = new ArrayList<>();
for(int[] e : people){
res.add(e[1],e);
}
int[][] ans = new int[res.size()][];
for(int i=0;i<ans.length;i++){
ans[i] = res.get(i);
}
return ans;
}
}
416. 分割等和子集
力扣链接：416. 分割等和子集
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for(int num:nums){
sum += num;
}
if(sum%2!=0){
return false;
}
int target = sum/2;
boolean[][] dp = new boolean[n+1][target+1];
dp[0][0] = true;
for(int i=1;i<=n;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1]){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
}
437. 路径总和 III
力扣链接：437. 路径总和 III
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long,Integer> mp = new HashMap<>();
mp.put(0L,1);
return dfs(root,mp,targetSum,0);
}
public int dfs(TreeNode root,Map<Long,Integer> mp,int targetSum,long curSum){
if(root == null){
return 0;
}
int res = 0;
curSum += root.val;
res += mp.getOrDefault(curSum-targetSum,0);
mp.put(curSum,mp.getOrDefault(curSum,0)+1);
res += dfs(root.left,mp,targetSum,curSum);
res += dfs(root.right,mp,targetSum,curSum);
mp.put(curSum,mp.get(curSum)-1);
return res;
}
}
438. 找到字符串中所有字母异位词
力扣链接：438. 找到字符串中所有字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int m = s.length();
int n = p.length();
List<Integer> res = new ArrayList<>();
if(m<n){
return res;
}
int[] s_arr = new int[26];
int[] p_arr = new int[26];
for(int i=0;i<n;i++){
s_arr[s.charAt(i)-'a']++;
p_arr[p.charAt(i)-'a']++;
}
if(Arrays.equals(s_arr,p_arr)){
res.add(0);
}
for(int i=0;i<m-n;i++){
s_arr[s.charAt(i)-'a']--;
s_arr[s.charAt(i+n)-'a']++;
if(Arrays.equals(s_arr,p_arr)){
res.add(i+1);
}
}
return res;
}
}
448. 找到所有数组中消失的数字
力扣链接：448. 找到所有数组中消失的数字
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
for(int num:nums){
int x = (num-1)%n;
nums[x] += n;
}
List<Integer> ret = new ArrayList<>();
for(int i=0;i<n;i++){
if(nums[i] <=n ){
ret.add(i+1);
}
}
return ret;
}
}
461. 汉明距离
力扣链接：461. 汉明距离
class Solution {
public int hammingDistance(int x, int y) {
int n =x^y;
int cnt = 0;
while(n!=0){
n = n&(n-1);
cnt++;
}
return cnt;
}
}
494. 目标和
力扣链接：494. 目标和
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
538. 把二叉搜索树转换为累加树
力扣链接：538. 把二叉搜索树转换为累加树
class Solution {
int res = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
public void dfs(TreeNode root){
if(root == null){
return ;
}
dfs(root.right);
res += root.val;
root.val = res;
dfs(root.left);
}
}
543. 二叉树的直径
力扣链接：543. 二叉树的直径
class Solution {
int res=0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return res;
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
res = Math.max(res,left+right);
return Math.max(left,right)+1;
}
}
560. 和为 K 的子数组
力扣链接：560. 和为 K 的子数组
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> mp = new HashMap<>();
mp.put(0,1);
int cnt = 0,pre = 0;
for(int num:nums){
pre+=num;
cnt += mp.getOrDefault(pre-k,0);
mp.put(pre,mp.getOrDefault(pre,0)+1);
}
return cnt;
}
}
581. 最短无序连续子数组
力扣链接：581. 最短无序连续子数组
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int max = nums[0];
int min = nums[n-1];
int end=-1,start=-1;
for(int i=0;i<n;i++){
if(nums[i]<max){
end = i;
}else{
max = nums[i];
}
}
for(int i=n-1;i>=0;i--){
if(nums[i]>min){
start= i;
}else{
min = nums[i];
}
}
return end==-1 ? 0:end-start +1;
}
}
617. 合并二叉树
力扣链接：617. 合并二叉树
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
root1.val = root1.val+root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}
621. 任务调度器
力扣链接：621. 任务调度器
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] arr = new int[26];
Arrays.fill(arr,0);
for(char c: tasks){
arr[c-'A']++;
}
int max = 0;
for(int num:arr){
max = Math.max(max,num);
}
int time= (max-1)*(n+1);
for(int num:arr){
if(num==max){
time++;
}
}
return Math.max(time,tasks.length);
}
}
647. 回文子串
力扣链接：647. 回文子串
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int cnt = 0;
for(int i=0;i<2*n+1;i++){
int l = i/2;
int r = l + i %2;
while(l>=0 && r<n && s.charAt(l)==s.charAt(r)){
cnt++;
l--;
r++;
}
}
return cnt;
}
}
739. 每日温度
力扣链接：739. 每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=0;i<n;i++){
while(!stack.isEmpty() && temperatures[stack.peek()]<temperatures[i]){
int idx = stack.pop();
res[idx] =i-idx;
}
stack.push(i);
}
return res;
}
}
如有侵权，请联系我