CodeTop一刷

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一、力扣56. 合并区间

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));if(intervals.length == 1){return intervals;}List<int[]> res = new ArrayList<>();for(int i = 1; i < intervals.length; i ++){if(intervals[i][0] <= intervals[i-1][1]){intervals[i][0] = Math.min(intervals[i-1][0], intervals[i][0]);intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);}else{res.add(intervals[i-1]);}}res.add(intervals[intervals.length-1]);int n = res.size();int[][] arr = new int[n][2];for(int i = 0; i < n; i ++){arr[i] = res.get(i);}return arr;}
}

在这里插入代码片

二、力扣42. 接雨水

class Solution {public int trap(int[] height) {Deque<Integer> deq = new LinkedList<>();int sum = 0;if(height.length <= 2){return sum;}deq.offerLast(0);for(int i = 1; i < height.length; i ++){int pre = height[deq.peekLast()];if(height[i] < pre){deq.offerLast(i);}else if(height[i] == pre){deq.pollLast();deq.offerLast(i);}else{while(!deq.isEmpty() && height[i] > pre){int mid = deq.pollLast();if(!deq.isEmpty()){int p = deq.peekLast();int h = Math.min(height[p], height[i]) - height[mid];int c = i - p - 1;if(h * c > 0){sum += h * c;}pre = height[deq.peekLast()];}}deq.offerLast(i);}}return sum;}
}

三、力扣72. 编辑距离

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), 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], Math.min(dp[i-1][j-1], dp[i][j-1])) + 1;}}}return dp[m][n];}
}

四、力扣124. 二叉树中的最大路径和

在这里插入代码片/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root == null){return 0;}int l = Math.max(0, fun(root.left));int r = Math.max(0, fun(root.right));res = Math.max(res, l+r+root.val);return l > r ? l + root.val : r + root.val;}
}

五、力扣142. 环形链表 II

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){return null;}ListNode fast = new ListNode(-1, head);ListNode slow = new ListNode(-1, head);while(fast.next != null && slow.next != null){if(fast.next.next != null){fast = fast.next.next;slow = slow.next;}else{return null;}if(fast == slow){ListNode p = new ListNode(-1, head);while(p != slow){p = p.next;slow = slow.next;}return p;}}return null;}
}

六、力扣19. 删除链表的倒数第 N 个结点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode fast = new ListNode(-1, head);ListNode slow = new ListNode(-1, head);while(n -- > 0){fast = fast.next;}while(fast != null){fast = fast.next;slow = slow.next;}return slow;}
}

七、力扣4. 寻找两个正序数组的中位数

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int[] arr = new int[m+n];int i = 0, j = 0, k = 0;while(i < m && j < n){if(nums1[i] < nums2[j]){arr[k ++] = nums1[i ++];}else{arr[k ++] = nums2[j ++];}}while(i < m){arr[k ++] = nums1[i ++];}while(j < n){arr[k ++] = nums2[j ++];}if((m+n) % 2 == 0){int cur = (m+n) / 2;double a = arr[cur-1];double b = arr[cur];return (a+b)/2;}else{return (double)arr[(m+n)/2];}}
}

八、力扣94. 二叉树的中序遍历

在这里插入代码片/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new LinkedList<>();TreeNode p = root;while(p != null || !deq.isEmpty()){if(p != null){deq.offerLast(p);p = p.left;}else{p = deq.pollLast();res.add(p.val);p = p.right;}}return res;}
}

九、力扣148. 排序链表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null){return head;}List<Integer> list = new ArrayList<>();ListNode p = head;while(p != null){list.add(p.val);p = p.next;}list.sort(Comparator.comparingInt(o -> o));ListNode L = new ListNode(-1, head);p = L;for(int a : list){ListNode cur = new ListNode(a, null);p.next = cur;p = p.next;}return L.next;}
}

十、力扣2. 括号生成

class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();if(n == 0){return res;}fun("", n, n, res);return res;}public void fun(String cur, int l, int r, List<String> res){if(l == 0 && r == 0){res.add(cur);return ;}if(l > r){return ;}if(l > 0){fun(cur + "(", l-1, r, res);}if(r > l && r > 0){fun(cur + ")", l , r-1, res);}}
}

十一、力扣31. 下一个排列

class Solution {public void nextPermutation(int[] nums) {int n = nums.length;if(n <= 1){return;}int i = n - 2;int j = n - 1;int k = n - 1;while(i >= 0 && nums[i] >= nums[j]){i --;j --;}if(i >= 0){while(nums[i] >= nums[k]){k --;}swap(nums, i, k);}reverse(nums, j, n-1);}public void swap(int[] nums, int left, int right){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}public void reverse(int[] nums, int start, int end){while(start < end){swap(nums, start, end);start ++;end --;}}
}

十二、力扣239. 滑动窗口最大值

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deq = new LinkedList<>();List<Integer> list = new ArrayList<>();for(int i = 0; i < nums.length; i ++){if(!deq.isEmpty() && deq.peekFirst() <= i-k){deq.pollFirst();}if(deq.isEmpty()){deq.offerLast(i);}else{while(!deq.isEmpty() && nums[i] > nums[deq.peekLast()]){deq.pollLast();}deq.offerLast(i);}if(i >= k-1){list.add(nums[deq.peekFirst()]);}}int[] res = list.stream().mapToInt(Integer::intValue).toArray();return res;}
}

十三、力扣2. 两数相加

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = new ListNode(-1, null);ListNode pre = head, p1 = l1, p2 = l2;int k = 0;while(p1 != null && p2 != null){int cur = p1.val + p2.val + k;if(cur > 9){k = cur / 10;cur = cur % 10;}else{k = 0;}ListNode t = new ListNode(cur, null);pre.next = t;pre = pre.next;p1 = p1.next;p2 = p2.next;}while(p1 != null){int cur = p1.val + k;if(cur > 9){k = cur / 10;cur = cur % 10;}else{k = 0;}ListNode t = new ListNode(cur, null);pre.next = t;pre = pre.next;p1 = p1.next;}while(p2 != null){int cur = p2.val + k;if(cur > 9){k = cur / 10;cur = cur % 10;}else{k = 0;}ListNode t = new ListNode(cur, null);pre.next = t;pre = pre.next;p2 = p2.next;}if(k != 0){ListNode t = new ListNode(k, null);pre.next = t;pre = pre.next;}return head.next;}
}

十四、力扣70. 爬楼梯

class Solution {public int climbStairs(int n) {if(n <= 2){return n;}int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i ++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

十五、力扣32. 最长有效括号

class Solution {public int longestValidParentheses(String s) {int res = 0;int left = 0, right = 0;for(int i = 0; i < s.length(); i ++){if(s.charAt(i) == '('){left ++;}else{right ++;}if(right > left){right = 0;left = 0;}else if(right == left){res = Math.max(res, 2* right);}}left = 0;right = 0;for(int i = s.length()-1; i >= 0; i --){if(s.charAt(i) == ')'){right ++;}else{left ++;}if(left > right){left = 0;right = 0;}else if(left == right){res = Math.max(res, 2*left);}}return res;}
}

十六、力扣322. 零钱兑换

在这里插入代码片class Solution {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] dp = new int[amount+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int i = 0; i < n; i ++){for(int j = coins[i]; j <= amount; j ++){int t = dp[j-coins[i]] == Integer.MAX_VALUE ? Integer.MAX_VALUE : dp[j-coins[i]]+1;dp[i] = Math.min(dp[j], t);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

十七、力扣76. 最小覆盖子串

class Solution {public String minWindow(String s, String t) {String res = s + "-";Map<Character,Integer> map = new HashMap<>();for(char c : t.toCharArray()){map.put(c, map.getOrDefault(c,0)+1);}int left = 0, right = 0;int count = map.size();char[] sh = s.toCharArray();while(right < s.length()){if(map.containsKey(sh[right])){map.put(sh[right], map.get(sh[right])-1);if(map.get(sh[right]) == 0){count --;}}right ++;while(left < right && count == 0){if(map.containsKey(sh[left])){if(map.get(sh[left]) == 0){res = right - left < res.length() ? s.substring(left,right) : res;count ++;}map.put(sh[left], map.get(sh[left]) + 1);}left ++;}}return res.equals(s + "-") ? "" : res;}
}

十八、力扣105. 从前序与中序遍历序列构造二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer,Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i = 0; i < inorder.length; i ++){map.put(inorder[i], i);}return fun(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}public TreeNode fun(int[] preorder, int[] inorder,int preStart,int preEnd,int inStart,int inEnd){if(preStart > preEnd){return null;}TreeNode cur = new TreeNode(preorder[preStart]);int index = map.get(preorder[preStart]);cur.left = fun(preorder, inorder, preStart+1, preStart+index-inStart, inStart, index-1);cur.right = fun(preorder, inorder, preStart+index-inStart+1, preEnd, index+1, inEnd);return cur;}
}

十九、力扣78. 子集

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {res.add(new ArrayList<>());fun(nums, 0);return res;}public void fun(int[] nums, int index){for(int i = index; i < nums.length; i ++){path.add(nums[i]);res.add(new ArrayList<>(path));fun(nums, i + 1);path.remove(path.size()-1);}}
}

二十、力扣155. 最小栈

class MinStack {Deque<Integer> deq = new ArrayDeque<>();Deque<Integer> deqMin = new ArrayDeque<>();public MinStack() {}public void push(int val) {deq.offerLast(val);if(deqMin.isEmpty() || val <= deqMin.peekLast()){deqMin.offerLast(val);}}public void pop() {int val = deq.pollLast();if(!deqMin.isEmpty() && deqMin.peekLast() == val){deqMin.pollLast();}}public int top() {return deq.peekLast();}public int getMin() {return deqMin.peekLast();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

二十一、力扣101. 对称二叉树

在这里插入代码片/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {return fun(root.left, root.right);}public boolean fun(TreeNode l, TreeNode r){if(l == null && r == null){return true;}if((l == null && r != null) || (l != null && r == null)){return false;}if(l.val != r.val){return false;}boolean bl = fun(l.left, r.right);boolean br = fun(l.right, r.left);return bl && br;}
}

二十二、力扣104. 二叉树的最大深度

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {return fun(root);}public int fun(TreeNode root){if(root == null){return 0;}int l = fun(root.left);int r = fun(root.right);return l > r ? l + 1 : r + 1;}
}

二十三、力扣34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {public int[] searchRange(int[] nums, int target) {int[] res = new int[]{-1,-1};if(nums == null || nums.length == 0){return res;}int left = firstIndex(nums, target);int right = secondIndex(nums, target);res[0] = left;res[1] = right;return res;}public int firstIndex(int[] nums, int target){int left = 0, right = nums.length-1;while(left <= right){int mid = (right - left)/2 + left;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{while(mid > 0 && nums[mid] == nums[mid-1]){mid --;}return mid;}}return -1;}public int secondIndex(int[] nums, int target){int left = 0, right = nums.length-1;while(left <= right){int mid = (right - left)/2 + left;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{while(mid < nums.length-1 && nums[mid] == nums[mid+1]){mid ++;}return mid;}}return -1;}
}

二十四、力扣39. 组合总和

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);fun(candidates, target, 0, 0);return res;}public void fun(int[] candidates, int target, int cur, int sum){if(sum == target){res.add(new ArrayList<>(path));return;}for(int i = cur; i < candidates.length; i ++){if(cur + sum > target){return ;}path.add(candidates[i]);fun(candidates, target, i, sum+candidates[i]);path.remove(path.size() - 1);}}
}

二十五、力扣394. 字符串解码

**class Solution {public String decodeString(String s) {Deque<Integer> deq = new LinkedList<>();Deque<StringBuilder> dsb = new LinkedList<>();StringBuilder cur = new StringBuilder();int k = 0;for(char c : s.toCharArray()){if(Character.isDigit(c)){k = k * 10 + (c-'0');}else if(c == '['){dsb.offerLast(cur);deq.offerLast(k);cur = new StringBuilder();k = 0;}else if(c == ']'){int t = deq.pollLast();StringBuilder pre = dsb.pollLast();for(int i = 0; i < t; i ++){pre.append(cur);}cur = pre;}else{cur.append(c);}}return cur.toString();}
}**

二十六、力扣64. 最小路径和

class Solution {public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];for(int i = 0, j = 0; i < m; i ++){j += grid[i][0];dp[i][0] = j;}for(int i = 0, j = 0; i < n; i ++){j += grid[0][i];dp[0][i] = 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];}
}

二十七、力扣48. 旋转图像

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for(int i = 0; i < n; i ++){for(int j = i+1; j < n; j ++){int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}for(int i = 0; i < n; i ++){for(int j = 0; j < n/2; j ++){int temp = matrix[i][j];matrix[i][j] = matrix[i][n-j-1];matrix[i][n-j-1] = temp;}}}
}

二十八、力扣240. 搜索二维矩阵 II

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;for(int i = 0, j = n-1; i < m && j >= 0; ){if(target == matrix[i][j]){return true;}else if(target > matrix[i][j]){i ++;}else{j --;}}return false;}
}

二十九、力扣98. 验证二叉搜索树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> res = new ArrayList<>();public boolean isValidBST(TreeNode root) {fun(root);if(res.size() == 1){return true;}for(int i = 1; i < res.size(); i ++){if(res.get(i) <= res.get(i-1)){return false;}}return true;}public void fun(TreeNode root){if(root == null){return ;}fun(root.left);res.add(root.val);fun(root.right);}
}

三十、力扣543. 二叉树的直径

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = 0;public int diameterOfBinaryTree(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root == null){return 0;}int l = fun(root.left);int r = fun(root.right);res = Math.max(res, l+r);return l > r ? l + 1 : r + 1;}
}

三十一、力扣221. 最大正方形

class Solution {public int maximalSquare(char[][] matrix) {int m = matrix.length, n = matrix[0].length;int[] dp = new int[n+1];int prev = 0;int res = 0;for(int i = 1; i <= m; i ++){prev = 0;for(int j = 1; j <= n; j ++){int temp = dp[j];if(matrix[i-1][j-1] == '1'){dp[j] = Math.min(Math.min(dp[j],dp[j-1]), prev)+1;res = Math.max(res, dp[j]);}else{dp[j] = 0;}prev = temp;}}return res * res;}
}

三十二、力扣234. 回文链表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ListNode L = new ListNode(-1, head);ListNode f = L, s = L;while(f.next != null){f = f.next;s = s.next;if(f.next != null){f = f.next;}else{break;}}ListNode p = s, p2 = s, p1 = head;reverse(s);p = p.next;while(p != null){if(p1.val != p.val){return false;}p1 = p1.next;p = p.next;}reverse(p2);return true;}public void reverse(ListNode node){ListNode p = node.next;node.next = null;while(p != null){ListNode r = p;p = p.next;r.next = node.next;node.next = r;}}
}

三十三、力扣128. 最长连续序列

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for(int n : nums){set.add(n);}int res = 0;for(int a : set){if(!set.contains(a-1)){int cur = a;int l = 1;while(set.contains(cur + 1)){cur ++;l ++;}res = Math.max(res, l);}}return res;}
}

三十四、力扣62. 不同路径

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0; i < m; i ++){dp[i][0] = 1;}for(int i = 0; i < n; i ++){dp[0][i] = 1;}for(int i = 1; i < m; i ++){for(int j = 1; j < n; j ++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

三十五、力扣152. 乘积最大子数组

class Solution {public int maxProduct(int[] nums) {int res = nums[0], max = nums[0], min = nums[0];for(int i = 1; i < nums.length; i ++){int cur = nums[i];int premax = max;int premin = min;max = Math.max(Math.max(cur, cur*premax), cur*premin);min = Math.min(Math.min(cur, cur*premax), cur*premin);res = Math.max(max, res);}return res;}
}

三十六、力扣198. 打家劫舍

class Solution {public int rob(int[] nums) {int n = nums.length;int[] dp = new int[n];if(n == 1){return nums[0];}if(n == 2){return nums[0] > nums[1] ? nums[0] : nums[1];}dp[0] = nums[0];dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];for(int i = 2; i < n; i ++){dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[n-1];}
}

三十七、力扣560. 和为 K 的子数组

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;int presum = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0,1);for(int i = 0; i < nums.length; i ++){presum += nums[i];if(map.containsKey(presum - k)){count += map.get(presum - k);}map.put(presum, map.getOrDefault(presum,0) + 1);}啊啊啊啊啊啊啊啊啊啊  return count;}
}

三十八、力扣169. 多数元素

class Solution {public int majorityElement(int[] nums) {int num = nums[0], count = 0;for(int a : nums){if(count == 0){num = a;}count += (num == a ? 1 : -1);}return num;}
}

三十八、力扣139. 单词拆分

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set = new HashSet<>(wordDict);int n = s.length();boolean[] dp = new boolean[n+1];dp[0] = true;for(int i = 1; i <= n; i ++){for(int j = 0; j < i; j ++){String sub = s.substring(j,i);if(dp[j] && set.contains(sub)){dp[i] = true;}}}return dp[n];}
}

三十九、力扣226. 翻转二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {return fun(root);}public TreeNode fun(TreeNode root){if(root == null){return null;}TreeNode l = root.left;TreeNode r = root.right;fun(root.left);fun(root.right);root.left = r;root.right = l;return root;}
}

四十、力扣283. 移动零

class Solution {public void moveZeroes(int[] nums) {for(int i = 0, j = 0; j < nums.length; ){if(nums[j] != 0){nums[i] = nums[j];i ++; j ++;}else{j ++;}if(j == nums.length){while(i < nums.length){nums[i] = 0;i ++;}}}}
}

四十一、力扣739. 每日温度

class Solution {public int[] dailyTemperatures(int[] temperatures) {Deque<Integer> deq = new LinkedList<>();int n = temperatures.length;int[] res = new int[n];deq.offerLast(0);for(int i = 1; i < n; i ++){if(temperatures[i] < temperatures[deq.peekLast()]){deq.offerLast(i);}else{while(!deq.isEmpty() && temperatures[i] > temperatures[deq.peekLast()]){int idx = deq.pollLast();res[idx] = i - idx;}deq.offerLast(i);}}return res;}
}

四十二、力扣297. 二叉树的序列化与反序列化

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null){return "";}Deque<TreeNode> deq = new LinkedList<>();StringBuilder sb = new StringBuilder();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();for(int i = 0; i < size; i ++){TreeNode cur = deq.pollFirst();if(cur == null){sb.append("#").append(",");continue;}sb.append(cur.val).append(",");deq.offerLast(cur.left);deq.offerLast(cur.right);}}return sb.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data.isEmpty()){return null;}String[] str = data.split(",");int idx = 0;Deque<TreeNode> deq = new ArrayDeque<>();TreeNode root = new TreeNode(Integer.parseInt(str[idx]));deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();for(int i = 0; i < size; i ++){TreeNode cur = deq.pollFirst();idx ++;if(!str[idx].equals("#")){TreeNode l = new TreeNode(Integer.parseInt(str[idx]));cur.left = l;deq.offerLast(l);}idx ++;if(!str[idx].equals("#")){TreeNode r = new TreeNode(Integer.parseInt(str[idx]));cur.right = r;deq.offerLast(r);}}}return root;}
}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

四十二、力扣207. 课程表

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int n = numCourses;List<List<Integer>> graph = new ArrayList<>();int[] indrgee = new int[n];for(int i = 0; i < n; i ++){graph.add(new ArrayList<>());}for(int[] arr : prerequisites){int course = arr[0];int pre = arr[1];graph.get(pre).add(course);indrgee[course] ++;}Deque<Integer> deq = new LinkedList<>();for(int i = 0; i < n; i ++){if(indrgee[i] == 0){deq.offerLast(i);}}int count = 0;while(!deq.isEmpty()){int course = deq.pollFirst();count ++;for(int cur : graph.get(course)){indrgee[cur] --;if(indrgee[cur] == 0){deq.offerLast(cur);}}}return count == n;}
}

四十二、力扣79. 单词搜索

class Solution {public boolean exist(char[][] board, String word) {int m = board.length, n = board[0].length;for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(dfs(board, word, 0, i , j)){return true;}}}return false;}public boolean dfs(char[][] board, String word, int idx, int i, int j){if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)){return false;}if(idx == word.length()-1){return true;}char temp = board[i][j];board[i][j] = '#';boolean res = dfs(board, word, idx+1, i+1, j) ||dfs(board, word, idx+1, i-1, j) ||dfs(board, word, idx+1, i, j+1) ||dfs(board, word, idx+1, i, j-1);board[i][j] = temp;return res;}
}

四十二、力扣136. 只出现一次的数字

class Solution {public int singleNumber(int[] nums) {int res = 0;for(int a : nums){res ^= a;}return res;}
}

四十二、力扣11. 盛最多水的容器

class Solution {public int maxArea(int[] height) {int res = 0;int left = 0, rigth = height.length-1;while(left < rigth){int cur = Math.min(height[left], height[rigth]) * (rigth - left);if(height[left] < height[rigth]){left ++;}else{rigth --;}res = Math.max(res, cur);}return res;}
}

四十二、力扣55. 跳跃游戏

class Solution {public boolean canJump(int[] nums) {int cur = 0;for(int i = 0; i < nums.length; i ++){if(cur < i){return false;}cur = Math.max(cur, i+nums[i]);}return true;}
}

四十二、力扣114. 二叉树展开为链表

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<TreeNode> res = new ArrayList<>();public void flatten(TreeNode root) {fun(root);for(int i = 1; i < res.size(); i ++){TreeNode pre = res.get(i-1);TreeNode cur = res.get(i);pre.right = cur;pre.left = null;}}public void fun(TreeNode root){if(root == null){return;}res.add(root);fun(root.left);fun(root.right);}
}

四十二、力扣75. 颜色分类

class Solution {public void sortColors(int[] nums) {int l = 0, i = 0, r = nums.length-1;while(i <= r){if(nums[i] == 0){swap(nums, l, i);l ++;i ++;}else if(nums[i] == 2){swap(nums, r, i);r --;}else{i ++;}}}public void swap(int[] nums, int a, int b){int temp = nums[a];nums[a] = nums[b]; nums[b] = temp;}
}

四十二、力扣10. 正则表达式匹配

class Solution {public boolean isMatch(String s, String p) {int m = s.length(), n = p.length();boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for(int j = 2; j <= n; j ++){if(p.charAt(j-1) == '*'){dp[0][j] = dp[0][j-2];}}for(int i = 1; i <= m; i ++){for(int j = 1; j <= n; j ++){if(p.charAt(j-1) != '*'){dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.');}else{dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.'));}}}return dp[m][n];}
}

四十二、力扣347. 前 K 个高频元素

在这里插入代码片class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();for(int a : nums){map.put(a, map.getOrDefault(a,0)+1);}List<List<Integer>> bucket = new ArrayList<>();for(int i = 0; i < nums.length+1; i ++){bucket.add(new ArrayList<>());}for(int key : map.keySet()){int fre = map.get(key);bucket.get(fre).add(key);}List<Integer> res = new ArrayList<>();for(int i = bucket.size() - 1; i >= 0 && k > 0; i --){if(!bucket.get(i).isEmpty()){for(int a : bucket.get(i)){if(k > 0){res.add(a);k --;}else{break;}}}}int[] arr = new int[res.size()];for(int i = 0; i < arr.length; i ++){arr[i] = res.get(i);}return arr;}
}

四十二、力扣208. 实现 Trie (前缀树)

class Trie {private TreeNode root;public Trie() {root = new TreeNode();}public void insert(String word) {TreeNode node = root;for(char c : word.toCharArray()){if(node.children[c-'a'] == null){node.children[c-'a'] = new TreeNode();}node = node.children[c-'a'];}node.isEnd = true;}public boolean search(String word) {TreeNode node = fun(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {TreeNode node = fun(prefix);return node != null;}private TreeNode fun(String word){TreeNode node = root;for(char c : word.toCharArray()){if(node.children[c-'a'] == null){return null;}node = node.children[c-'a'];}return node;}private static class TreeNode{boolean isEnd = false;TreeNode[] children = new TreeNode[26];}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

四十二、力扣96. 不同的二叉搜索树

class Solution {public int numTrees(int n) {if(n <= 2){return n;}if(n == 3){return 5;}int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;dp[2] = 2;dp[3] = 5;for(int i = 4; i <= n; i ++){for(int j = 1; j <= i; j ++){dp[i] += (dp[j-1] * dp[i-j]);}}return dp[n];}
}

四十二、力扣287. 寻找重复数

class Solution {public int findDuplicate(int[] nums) {int fast = nums[0];int slow = nums[0];do{slow = nums[slow];fast = nums[nums[fast]];}while(slow != fast);slow = nums[0];while(slow != fast){slow = nums[slow];fast = nums[fast];}return slow;}
}

四十二、力扣85. 最大矩形

class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length, n = matrix[0].length;int[] row = new int[n];int res = 0;for(char[] ch : matrix){for(int i = 0; i < n; i ++){row[i] = ch[i] == '1' ? row[i] + 1 : 0;}res = Math.max(res, fun(row));}return res;}public int fun(int[] high){Deque<Integer> deq = new LinkedList<>();int[] newhigh = new int[high.length+2];System.arraycopy(high, 0, newhigh, 1, high.length);int res = 0;for(int i = 0; i < newhigh.length; i ++){while(!deq.isEmpty() && newhigh[deq.peekLast()] > newhigh[i]){int h = newhigh[deq.pollLast()];res = Math.max(res, h * (i-deq.peekLast()-1));}deq.offerLast(i);}return res;}
}

四十二、力扣84. 柱状图中最大的矩形

class Solution {public int largestRectangleArea(int[] heights) {int res = 0;int[] newHigh = new int[heights.length+2];System.arraycopy(heights, 0, newHigh, 1, heights.length);Deque<Integer> deq = new LinkedList<>();for(int i = 0; i < newHigh.length; i ++){while(!deq.isEmpty() && newHigh[deq.peekLast()] > newHigh[i]){int h = newHigh[deq.pollLast()];res = Math.max(res, h * (i - deq.peekLast() - 1));}deq.offerLast(i);}return res;}
}

四十二、力扣494. 目标和

在这里插入代码片class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int a : nums){sum += a;}if((sum+target)%2 != 0 || (sum+target) < 0){return 0;}int len = (sum+target)/2;int[] dp = new int[len+1];dp[0] = 1;for(int a : nums){for(int j = len; j >= a; j --){dp[j] += dp[j-a];}}return dp[len];}
}

四十二、力扣253. 会议室 II

	/*** Definition of Interval:* public class Interval {*     int start, end;*     Interval(int start, int end) {*         this.start = start;*         this.end = end;*     }* }*/public class Solution {/*** @param intervals: an array of meeting time intervals* @return: the minimum number of conference rooms required*/public int minMeetingRooms(List<Interval> intervals) {// Write your code hereif(intervals == null || intervals.size() == 0){return 0;}intervals.sort(Comparator.comparingInt(a -> a.start));PriorityQueue<Integer> pq = new PriorityQueue<>();for(Interval cur : intervals){if(!pq.isEmpty() && cur.start >= pq.peek()){pq.poll();}pq.offer(cur.end);}return pq.size();}
}

四十二、力扣279. 完全平方数

class Solution {public int numSquares(int n) {int m = (int) Math.sqrt(n);int[] arr = new int[m+1];for(int i = 1; i <= m; i ++){arr[i] = i*i;}int[] dp = new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int i = 1; i <= m; i ++){for(int j = arr[i]; j <= n; j ++){if(dp[j- arr[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j - arr[i]]+1);}}}return dp[n];}
}

四十二、力扣416. 分割等和子集

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int a : nums){sum += a;}if(sum % 2 != 0){return false;}sum /= 2;int[] dp = new int[sum+1];for(int i = 0; i < nums.length; i ++){for(int j = sum; j >= nums[i]; j --){dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}return dp[sum] == sum;}
}

四十二、力扣647. 回文子串

class Solution {public int countSubstrings(String s) {int res = 0;for(int i = 0; i < s.length(); i ++){int a = fun(s, i, i);int b = fun(s, i, i+1);res += (a+b);}return res;}public int fun(String s, int l, int r){int res = 0;for( ; l >= 0 && r < s.length(); l --, r ++){if(s.charAt(l) != s.charAt(r)){return res;}else{res ++;}}return res;}
}

四十二、力扣301. 删除无效的括号

class Solution {public List<String> removeInvalidParentheses(String s) {List<String> res = new ArrayList<>();Deque<String> deq = new LinkedList<>();Set<String> set = new HashSet<>();deq.offerLast(s);set.add(s);boolean flag = false;while(!deq.isEmpty()){String cur = deq.pollFirst();if(fun(cur)){res.add(cur);flag = true;}if(flag){continue;}for(int i = 0; i < cur.length(); i ++){if(cur.charAt(i) != '(' && cur.charAt(i) != ')'){continue;}String str = cur.substring(0,i) + cur.substring(i+1);if(!set.contains(str)){set.add(str);deq.offerLast(str);}}}return res;}public boolean fun(String s){int count = 0;for(char c : s.toCharArray()){if(c == '('){count ++;}else if(c == ')'){if(count == 0){return false;}count --;}}return count == 0;}
}

四十二、力扣337. 打家劫舍 III

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] res = fun(root);return Math.max(res[0], res[1]);}public int[] fun(TreeNode root){if(root == null){return new int[]{0,0};}int[] l = fun(root.left);int[] r = fun(root.right);int[] cur = new int[]{0,0};cur[0] = root.val + l[1] + r[1];cur[1] = Math.max(l[0],l[1]) + Math.max(r[0], r[1]);return cur;}
}

四十二、力扣17. 电话号码的字母组合

class Solution {List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();String[] str = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits.equals("")){return res;}fun(digits, 0);return res;}public void fun(String digits, int cur){if(sb.length() >= digits.length()){res.add(sb.toString());return;}String s = str[digits.charAt(cur) - '0'];for(int i = 0; i < s.length(); i ++){sb.append(s.charAt(i));fun(digits, cur+1);sb.deleteCharAt(sb.length()-1);}}
}

四十二、力扣438. 找到字符串中所有字母异位词

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();int slen = s.length(), plen = p.length();int[] sarr = new int[26];int[] parr = new int[26];if(slen < plen){return res;}for(int i = 0; i < plen; i ++){sarr[s.charAt(i) - 'a'] ++;parr[p.charAt(i) - 'a'] ++;}int l = 0, r = plen - 1;while(r < slen){boolean flag = true;for(int i = 0; i < 26; i ++){if(sarr[i] != parr[i]){flag = false;}}if(flag){res.add(l);}r ++;if(r >= slen){break;}sarr[s.charAt(r) - 'a'] ++;sarr[s.charAt(l) - 'a'] --;l ++;}return res;}
}

四十二、力扣617. 合并二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return fun(root1, root2);}public TreeNode fun(TreeNode root1, TreeNode root2){if(root1 == null && root2 == null){return null;}if(root1 == null && root2 != null){return root2;}if(root1 != null && root2 == null){return root1;}root1.val += root2.val;root1.left = fun(root1.left, root2.left);root1.right = fun(root1.right, root2.right);return root1;}
}

四十二、力扣49. 字母异位词分组

class Solution {
List<List> res = new ArrayList<>();
public List<List> groupAnagrams(String[] strs) {
Map<String,List> map = new HashMap<>();
for(String s : strs){
int[] arr = new int[26];
for(char c : s.toCharArray()){
arr[c-‘a’] ++;
}
String s1 = “”;
for(int i = 0; i < arr.length; i ++){
if(arr[i] != 0){
s1 += i;
s1 += “_”;
s1 += arr[i];
}
}
if(!map.containsKey(s1)){
map.put(s1, new ArrayList<>());
}
List list = map.get(s1);
list.add(s);
}
for(String ss : map.keySet()){
List l1 = map.get(ss);
res.add(l1);
}
return res;
}
}

四十二、力扣437. 路径总和 III

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Long,Integer> map = new HashMap<>();long curPath , targetSum;int res = 0;public int pathSum(TreeNode root, int targetSum) {this.curPath = 0L;this.targetSum = targetSum;map.put(0L, 1);fun(root, targetSum);return res;}public void fun(TreeNode root, int targetSum){if(root == null){return;}curPath += root.val;res += map.getOrDefault(curPath-targetSum,0);map.put(curPath, map.getOrDefault(curPath,0) + 1);fun(root.left, targetSum);fun(root.right, targetSum);map.put(curPath, map.getOrDefault(curPath,0) - 1);curPath -= root.val;}
}