1.两数之和

public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }else {
                map.put(nums[i], i);
            }
        }
        return new int[]{};
    }

2.两数相加

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; }
  }
    //2
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        int sum = 0, carry = 0;
        while(l1 != null|| l2 != null){
            int v1 = l1 == null? 0: l1.val;
            int v2 = l2 == null? 0: l2.val;
            sum = v1 + v2 + carry;
            carry = sum/10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            l1 = l1 == null? null : l1.next;
            l2 = l2 == null? null : l2.next;
        }
        if(carry != 0)
            cur.next = new ListNode(1);
        return dummyHead.next;
    }

3.无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0|| s == null)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))){
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}

4.两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = (nums1.length + nums2.length + 1) / 2;
        int l2 = (nums1.length + nums2.length + 2) / 2;
        return (getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, l1) + getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, l2)) * 0.5;
    }
    private int getKth(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int k) {
        int len1 = e1 - s1 + 1;
        int len2 = e2 - s2 + 1;
        if(len1 > len2) return getKth(nums2, s2, e2, nums1, s1, e1, k);
        if(len1 == 0) return nums2[s2 + k - 1];
        if(k == 1) return Math.min(nums1[s1], nums2[s2]);
        int i = s1 + Math.min(len1, k/2) - 1;
        int j = s2 + Math.min(len2, k/2) - 1;
        if(nums1[i] > nums2[j]){
            return getKth(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1));
        }else 
            return getKth(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1));
    }
}

5.最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 0|| s== null)
            return null;
        if(s.length() == 1)
            return s;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int max = 1;
        int start = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if(s.charAt(i) != s.charAt(j))
                    continue;
                if(i == j)
                    dp[i][i] = true;
                else
                    dp[i][j] = i - j <= 2|| dp[i-1][j+1];
                if(dp[i][j]&& i - j + 1 > max){
                    max = i - j + 1;
                    start = j;
                }
            }
        }
        return s.substring(start, start + max);
    }
}

10.正则表达式

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

11.盛水最多的容器

public int maxArea(int[] height) {
        int res = 0;
        int i = 0, j = height.length - 1;
        while (i < j){
            res = height[i] < height[j]?
                    Math.max(res, (j-i) * height[i++]):
                    Math.max(res, (j-i) * height[j--]);
        }
        return res;
    }

15.三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null|| nums.length == 0)
            return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) break;
            if(i > 0&& nums[i] == nums[i - 1]) continue;
            int j = i + 1, l = nums.length - 1;
            while (j < l){
                int sum = nums[i] + nums[j] + nums[l];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[j], nums[l]));
                    while (j<l&&nums[j] == nums[j + 1])
                        j++;
                    while (j<l&&nums[l] == nums[l - 1])
                        l--;
                    j++;
                    l--;
                }else if(sum > 0)
                    l--;
                else 
                    j++;
            }
        }
        return res;
    }
}

17电话号码组合

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if(digits.length() == 0|| digits == null)
            return res;
        char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},{'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},{'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
        dfs17(res, digits, 0, tab, "");
        return res;
    }

    private void dfs17(List<String> res, String digits, int i, char[][] tab, String s) {
        if(s.length() == digits.length()){
            res.add(s);
            return;
        }
        char[] cur = tab[digits.charAt(i) - '2'];
        for (int j = 0; j < cur.length; j++) {
            dfs17(res, digits, i + 1, tab, s + cur[j]);
        }
    }
}

19.删除链表倒数第n个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

20.有效地括号

public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (char c: chars){
            if(c == '('){
                stack.push(')');
            }else if(c == '{'){
                stack.push('}');
            }else if(c == '['){
                stack.push(']');
            }else if(stack.isEmpty()|| stack.pop() != c)
                return false;
        }
        return stack.isEmpty();
    }

21.合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null|| list2 == null)
            return list1 == null? list2: list1;
        ListNode first = (list1.val < list2.val)? list1: list2;
        first.next = mergeTwoLists(first.next, first == list1? list2: list1);
        return first;
    }
}

22.括号生成

public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs22(0, 0, res, n, "");
        return  res;
    }

    private void dfs22(int l, int r, List<String> res, int n, String cur) {
        if(l == n&& r == n){
            res.add(cur);
            return;
        }
        if(l < r|| l > n)
            return;
        cur += '(';
        dfs22(l + 1, r, res, n, cur);
        cur = cur.substring(0, cur.length() - 1);
        cur += ')';
        dfs22(l, r + 1, res, n, cur);
        cur = cur.substring(0, cur.length() - 1);
    }

23.合并K个升序链表

 public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null)
            return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode node : lists){
            if(node != null)
                queue.offer(node);
        }
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
            if(cur.next != null)
                queue.offer(cur.next);
        }
        return dummyHead.next;
    }

31下一个排列

public void nextPermutation(int[] nums) {
        int left = nums.length - 2;
        int right = nums.length - 1;
        while(left >= 0&& nums[left] >= nums[left+1]){
            left--;
        }
        if(left >= 0){
            while (right > left&& nums[right] <= nums[left])
                right--;
            swap31(nums, left, right);
        }
        reverse31(nums, left + 1, nums.length - 1);
    }

    private void reverse31(int[] nums, int left, int right) {
        while(left < right){
            swap31(nums, left++, right--);
        }
    }

    private void swap31(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

32.最长的有效括号

 public int longestValidParentheses(String s) {
        if(s == null|| s.length() == 0)
            return 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        int max = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(i);
            }else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

33.旋转排序数组

public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            if(nums[left] <= nums[mid]){
                if(target >= nums[left]&& target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else {
                if(target > nums[mid]&& target <= nums[right]){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

34排序数组第一个位置和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null|| nums.length == 0)
            return new int[]{-1, -1};
        if(findFirst34(nums, target) == -1)
            return new int[]{-1, -1};
        return new int[]{findFirst34(nums, target), findLast34(nums, target)};
    }

    private int findLast34(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while(left < right){
            mid = left + (right - left + 1) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] == target){
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    private int findFirst34(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] == target){
                right = mid;
            }else {
                right = mid - 1;
            }
        }
        if(nums[left] == target)
            return left;
        return -1;
    }
}

39.组合总和

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        back39(res, new ArrayList<Integer>(), 0, candidates, target);
        return res;
    }

    private void back39(List<List<Integer>> res, ArrayList<Integer> list, int i, int[] candidates, int target) {
        if(target == 0){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for (int j = i; j < candidates.length; j++) {
            if(candidates[j] > target)
                break;
            list.add(candidates[j]);
            back39(res, list, j, candidates, target - candidates[j]);
            list.remove(list.size() - 1);
        }
    }

42.接雨水

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        if(height == null|| height.length == 0)
            return res;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty()&& height[stack.peek()] < height[i]){
                int cur = stack.pop();
                while (!stack.isEmpty()&& height[stack.peek()] == height[cur]){
                    stack.pop();
                }
                if(!stack.isEmpty()){
                    int wid = i - stack.peek() - 1;
                    int high = Math.min(height[stack.peek()] - height[cur], height[i] - height[cur]);
                    res += wid * high;
                }
            }
            stack.push(i);
        }
        return res;
    }
}

46.全排列

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        back46(res, new ArrayList<Integer>(), nums);
        return res;
    }

    private void back46(List<List<Integer>> res, ArrayList<Integer> list, int[] nums) {
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(list.contains(nums[i]))
                continue;
            list.add(nums[i]);
            back46(res, list, nums);
            list.remove(list.size() - 1);
        }
    }

48.旋转图像

public static void rotate(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = matrix.length - 1;
            int dC = matrix[0].length - 1;
            while (tR < dR) {
                rotateEdge(matrix, tR++, tC++, dR--, dC--);
            }
    }
    public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {
            int times = dC - tC;
            int tmp = 0;
            for (int i = 0; i != times; i++) {
                tmp = m[tR][tC + i];
                m[tR][tC + i] = m[dR - i][tC];
                m[dR - i][tC] = m[dR][dC - i];
                m[dR][dC - i] = m[tR + i][dC];
                m[tR + i][dC] = tmp;
            }
    }

49.字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if(strs == null|| strs.length == 0)
            return res;
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String str = String.valueOf(chars);
            if(!map.containsKey(str)){
                map.put(str, new ArrayList<>());
            }
            map.get(str).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }

53.最大子数组和

public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num: nums){
            if(sum > 0)
                sum += num;
            else 
                sum = num;
            ans = Math.max(ans, sum);
        }
        return ans;
    }

55.跳跃游戏

public boolean canJump(int[] nums) {
        int last = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if(nums[i] + i >= last)
                last = i;
        }
        return last == 0;
    }

62.不同路径

public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 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];
    }

64.最小路径和

public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i == 0&& j == 0)
                    continue;
                else if(j == 0)
                    grid[i][0] = grid[i - 1][0] + grid[i][0];
                else if(i == 0)
                    grid[0][j] = grid[0][j - 1] + grid[0][j];
                else
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

70.爬楼梯

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

72.编辑距离

public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if(len1 * len2 == 0)
            return len1 == 0? len2: len1;
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[len1][len2];
    }

75.颜色分类

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

    private void swap75(int[] nums, int i, int i1) {
        int temp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }

76.最小覆盖子串

public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c: t.toCharArray()){
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        int l = 0, r = 0;
        int winLen = Integer.MAX_VALUE;
        int strStart = 0;
        while (r < s.length()){
            char rChar = s.charAt(r);
            if(map.containsKey(rChar))
                map.put(rChar, map.get(rChar) - 1);
            r++;
            while(check76(map)){
                if(r - l < winLen){
                    winLen = r - l;
                    strStart = l;
                }
                char lChar = s.charAt(l);
                if(map.containsKey(lChar))
                    map.put(lChar, map.get(lChar) + 1);
                l++;
            }
        }
        return winLen == Integer.MAX_VALUE? "": s.substring(strStart, strStart + winLen);
    }

    private boolean check76(Map<Character, Integer> map) {
        for (int v: map.values()){
            if(v > 0)
                return false;
        }
        return true;
    }

78.子集

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        back78(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }

    private void back78(List<List<Integer>> res, ArrayList<Integer> list, int[] nums, int i) {
        res.add(new ArrayList<>(list));
        for (int j = i; j < nums.length; j++) {
            list.add(nums[j]);
            back78(res, list, nums, j + 1);
            list.remove(list.size() - 1);
        }
    }

79.单词搜索

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(back79(board, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }

    private boolean back79(char[][] board, int i, int j, String word, int index) {
        if(i < 0||i >= board.length|| j < 0|| j >= board[0].length|| board[i][j] != word.charAt(index))
            return false;
        if(index == word.length() - 1)
            return true;
        char temp = board[i][j];
        board[i][j] = '.';
        boolean res = back79(board, i + 1, j, word, index + 1)|| back79(board, i - 1, j, word, index + 1)||
                back79(board, i, j + 1, word, index + 1)||back79(board, i, j - 1, word, index + 1);
        board[i][j] = temp;
        return res;
    }

84.柱状图矩形最大面积

public int largestRectangleArea(int[] heights) {
        int[] nums = new int[heights.length + 2];
        System.arraycopy(heights, 0, nums, 1, heights.length);
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty()&& nums[i] < nums[stack.peek()]){
                int h = nums[stack.pop()];
                res = Math.max(res, h * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }

85.最大矩形

//84
    public int largestRectangleArea(int[] heights) {
        int[] nums = new int[heights.length + 2];
        System.arraycopy(heights, 0, nums, 1, heights.length);
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty()&& nums[i] < nums[stack.peek()]){
                int h = nums[stack.pop()];
                res = Math.max(res, h * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }
    //85
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null|| matrix.length == 0)
            return 0;
        int[] heights = new int[matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == '1')
                    heights[j] += 1;
                else 
                    heights[j] = 0;
            }
            res = Math.max(res, largestRectangleArea(heights));
        }
        return res;
    }

94.二叉树中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs94(res, root);
        return res;
    }

    private void dfs94(List<Integer> res, TreeNode root) {
        if(root == null)
            return;
        dfs94(res, root.left);
        res.add(root.val);
        dfs94(res, root.right);
    }

96.不同的二叉搜索树

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

98.验证二叉搜索树

public boolean isValidBST(TreeNode root) {
        return isValidBST98(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    private boolean isValidBST98(TreeNode root, long big, long small) {
        if(root == null)
            return true;
        if(root.val >= big)
            return false;
        if(root.val <= small)
            return false;
        if(!isValidBST98(root.left, root.val, small))
            return false;
        if(!isValidBST98(root.right, big, root.val))
            return false;
        return true;
    }

101对称二叉树

public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return helper101(root.left, root.right);
    }

    private boolean helper101(TreeNode left, TreeNode right) {
        if(left == null&& right == null)
            return true;
        if(left == null|| right == null)
            return false;
        if(right.val != left.val)
            return false;
        return helper101(left.left, right.right)&&helper101(left.right, right.left);
    }

102.二叉树层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int curSize = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < curSize; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }

104.二叉树的最大深度

public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

105.前序中序构造二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {
        List<Integer> preList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        for (int i = 0; i < preorder.length; i++) {
            preList.add(preorder[i]);
            inList.add(inorder[i]);
        }
        return helper105(preList, inList);
    }

    private TreeNode helper105(List<Integer> preList, List<Integer> inList) {
        if(inList.size() == 0|| inList == null)
            return null;
        int rootVal = preList.remove(0);
        TreeNode root = new TreeNode(rootVal);
        int mid = inList.indexOf(rootVal);
        root.left = helper105(preList, inList.subList(0, mid));
        root.right = helper105(preList, inList.subList(mid + 1, inList.size()));
        return root;
    }

114.二叉树转为链表

public void flatten(TreeNode root) {
        if (root == null)
            return;
        List<Integer> list = new ArrayList<>();
        helper114(list, root);
        if(list.size() == 0)
            return;
        TreeNode parent = root;
        for (int i = 1; i < list.size(); i++) {
            parent.right = new TreeNode(list.get(i));
            parent.left = null;
            parent = parent.right;
        }
    }

    private void helper114(List<Integer> list, TreeNode root) {
        if(root == null)
            return;
        list.add(root.val);
        helper114(list, root.left);
        helper114(list, root.right);
    }

121.买卖股票的最佳时机

public int maxProfit(int[] prices) {
        int res = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        if(prices == null|| prices.length == 0)
            return 0;
        for (int i = 0; i < prices.length; i++) {
            if(prices[i] < min)
                min = prices[i];
            res = Math.max(res, prices[i] - min);
        }
        return res;
    }

124.二叉树最大路径和

public int maxPathSum(TreeNode root) {
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        helper124(root, max);
        return max[0];
    }

    private int helper124(TreeNode root, int[] max) {
        if (root == null)
            return 0;
        int leftMax = Math.max(0, helper124(root.left, max));
        int rightMax = Math.max(0, helper124(root.right, max));
        int curSum = root.val + leftMax + rightMax;
        max[0] = Math.max(max[0], curSum);
        return root.val + Math.max(leftMax, rightMax);
    }

128.最长连续序列

public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num: nums)
            set.add(num);
        int max = 0;
        for(int num: nums){
            if(!set.contains(num - 1)){
                int curNum = num;
                int curMax = 1;
                while(set.contains(curNum + 1)){
                    curMax += 1;
                    curNum += 1;
                }
                max = Math.max(max, curMax);
            }
        }
        return max;
    }

136.只出现一次的数字

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

139.单词拆分

 public boolean wordBreak(String s, List<String> 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++) {
                dp[i] = dp[j]&& wordDict.contains(s.substring(j,i));
                if(dp[i])
                    break;
            }
        }
        return dp[s.length()];
    }

142.环形链表

public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null&& fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                while (head != slow){
                    slow = slow.next;
                    head = head.next;
                }
                return slow;
            }
        }
        return null;
    }

146.LRU缓存

class LRUCache {
        Map<Integer, ListNodeLRU> map;
        int capacity;
        ListNodeLRU dummyHead;
        ListNodeLRU dummyTail;
        class ListNodeLRU{
            int key;
            int value;
            ListNodeLRU pre;
            ListNodeLRU next;
            public ListNodeLRU(){}
            public ListNodeLRU(int key, int value){
                this.key = key;
                this.value = value;
            }
        }
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity);
            dummyHead = new ListNodeLRU(-1, -1);
            dummyTail = new ListNodeLRU(-1, -1);
            dummyTail.pre = dummyHead;
            dummyHead.next = dummyTail;
        }

        public int get(int key) {
            if(map.containsKey(key)){
                ListNodeLRU node = map.get(key);
                int val = node.value;
                move2Head(key);
                return val;
            }else
                return -1;
        }

        private void move2Head(int key) {
            ListNodeLRU node = map.get(key);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            add2Head(node);
        }

        private void add2Head(ListNodeLRU node) {
            ListNodeLRU oldNode = dummyHead.next;
            oldNode.pre = node;
            node.next = oldNode;
            node.pre = dummyHead;
            dummyHead.next = node;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){
                map.get(key).value = value;
                move2Head(key);
                return;
            }
            if(map.size() == capacity){
                ListNodeLRU oldTail = removeTail();
                map.remove(oldTail.key);
            }
            ListNodeLRU node = new ListNodeLRU(key, value);
            map.put(key, node);
            add2Head(node);
        }

        private ListNodeLRU removeTail() {
            ListNodeLRU oldTail = dummyTail.pre;
            ListNodeLRU newTai = oldTail.pre;
            newTai.next = dummyTail;
            dummyTail.pre = newTai;
            oldTail.next = null;
            oldTail.pre = null;
            return oldTail;
        }
    }

148.排序链表

public ListNode sortList(ListNode head) {
        if(head == null|| head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null&& fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tempNode = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tempNode);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (left != null&& right != null){
            if(left.val < right.val){
                cur.next = left;
                left = left.next;
                cur = cur.next;
            }else {
                cur.next = right;
                right = right.next;
                cur = cur.next;
            }
            cur.next = left == null? right: left;
        }
        return dummy.next;
    }

152.乘积最大子数组

public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int num: nums){
            if(num < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(num, num * imax);
            imin = Math.min(num, num * imin);
            max = Math.max(max, imax);
        }
        return max;
    }

155.最小栈

class MinStack {
        Deque<Integer> stack;
        Deque<Integer> minStack;
        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        public void push(int val) {
            stack.push(val);
            if(minStack.isEmpty()|| val <= minStack.peek())
                minStack.push(val);
        }

        public void pop() {
            if(stack.pop().equals(minStack.peek()))
                minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

160.相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ha = headA, hb = headB;
        //需要变成null返回，所以判断用ha == null而不是ha.next == null
        while (ha != hb){
            ha = ha == null? headB: ha.next;
            hb = hb == null? headA: hb.next;
        }
        return ha;
    }

169.多数元素

public int majorityElement(int[] nums) {
        int vote = 0, cnt = 0, res = 0;
        for (int num: nums){
            if(vote == 0)
                res = num;
            vote += num == res? 1: -1;
        }
        for(int num: nums){
            if(num == res)
                cnt++;
        }
        return res;
    }

198.打家劫舍

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

200.岛屿数量

public int numIslands(char[][] grid) {
        if(grid.length == 0|| grid[0].length == 0)
            return 0;
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    res++;
                    dfs200(grid, i, j);
                }
            }
        }
        return res;
    }

    private void dfs200(char[][] grid, int i, int j) {
        if(i < 0|| i >= grid.length|| j < 0|| j >= grid[0].length|| grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        dfs200(grid, i + 1, j);
        dfs200(grid, i - 1, j);
        dfs200(grid, i, j + 1);
        dfs200(grid, i, j - 1);
    }

206.反转链表

public ListNode reverseList(ListNode head) {
        if(head == null|| head.next == null)
            return head;
        ListNode pre = null;
        ListNode temp = null;
        ListNode cur = head;
        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

207.课程表

public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        int[] flags = new int[numCourses];
        for(int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);
        for(int i = 0; i < numCourses; i++)
            if(!dfs(adjacency, flags, i)) return false;
        return true;
    }
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if(flags[i] == 1) return false;
        if(flags[i] == -1) return true;
        flags[i] = 1;
        for(Integer j : adjacency.get(i))
            if(!dfs(adjacency, flags, j)) return false;
        flags[i] = -1;
        return true;
    }

208.前缀树

class Trie {
        class TrieNode{
            boolean isEnd;
            TrieNode[] next = new TrieNode[26];
            public void setIsEnd(boolean isEnd){
                this.isEnd = isEnd;
            }
        }
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            char[] chs = word.toCharArray();
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                int u = chs[i] - 'a';
                if(node.next[u] == null){
                    node.next[u] = new TrieNode();
                }
                node = node.next[u];
            }
            node.setIsEnd(true);
        }

        public boolean search(String word) {
            char[] chs = word.toCharArray();
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                int u = chs[i] - 'a';
                if(node.next[u] == null){
                    return false;
                }
                node = node.next[u];
            }
            return node.isEnd;
        }

        public boolean startsWith(String prefix) {
            char[] chs = prefix.toCharArray();
            TrieNode node = root;
            for (int i = 0; i < prefix.length(); i++) {
                int u = chs[i] - 'a';
                if(node.next[u] == null){
                    return false;
                }
                node = node.next[u];
            }
            return true;
        }
    }

215.数组第K大的元素

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num: nums){
            queue.add(num);
        }
        for (int i = 0; i < nums.length - k; i++) {
            queue.poll();
        }
        return queue.peek();
    }

221.最大正方形

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

234.回文链表

public boolean isPalindrome(ListNode head) {
        if(head == null|| head.next == null)
            return true;
        ListNode halfPos = findHalf234(head);
        ListNode reverseHead = reverse234(halfPos);
        while (reverseHead != null){
            if(head.val != reverseHead.val)
                return false;
            head = head.next;
            reverseHead = reverseHead.next;
        }
        return true;
    }

    private ListNode reverse234(ListNode halfPos) {
        ListNode pre = null;
        ListNode temp = null;
        ListNode cur = halfPos;
        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    private ListNode findHalf234(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null&& fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

236.最近公共祖先

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;
        if (left == null&& right == null)
            return null;
        return root;
    }

238.除自身以外的乘积

public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0] = 1;
        right[right.length - 1] = 1;
        for (int i = 1; i < left.length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        for (int i = right.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }

239.滑动窗口最大值

public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty()&& nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            queue.addLast(i);
            if(queue.peekFirst() <= i - k)
                queue.pollFirst();
            if(i + 1 >= k)
                res[i + 1 - k] = nums[queue.peekFirst()];
        }
        return res;
    }

240.搜索二维矩阵

public boolean searchMatrix(int[][] matrix, int target) {
        int r = matrix.length - 1, c = 0;
        while (r >= 0&& c <= matrix[0].length - 1){
            if(matrix[r][c] == target)
                return true;
            else if(matrix[r][c] < target){
                c++;
            }else if(matrix[r][c] > target)
                r--;
        }
        return false;
    }

279.完全平方数

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; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

283.移动0

public void moveZeroes(int[] nums) {
        int l = 0, r = 0;
        while (r < nums.length){
            if(nums[r] == 0)
                r++;
            else {
                int temp = nums[r];
                nums[r] = nums[l];
                nums[l] = temp;
                l++;
                r++;
            }
        }
        return;
    }

287.寻找重复数

public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right){
            int mid = (left + right) >>> 1;
            int cnt = 0;
            for (int num: nums){
                if(num <= mid)
                    cnt++;
            }
            if(cnt > mid)
                right = mid;
            else 
                left = mid + 1;
        }
        return left;
    }

297.二叉树的序列化与反序列化

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder res = new StringBuilder();
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                res.append(node.val + ",");
                queue.offer(node.left);
                queue.offer(node.right);
            }else {
                res.append("null,");
            }
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "")
            return null;
        String[] strings = data.substring(0, data.length() - 1).split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!strings[index].equals("null")){
                node.left = new TreeNode(Integer.parseInt(strings[index]));
                queue.offer(node.left);
            }
            index++;
            if(!strings[index].equals("null")){
                node.right = new TreeNode(Integer.parseInt(strings[index]));
                queue.offer(node.right);
            }
            index++;
        }
        return root;
    }

300.最长递增子序列

public int lengthOfLIS(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num: nums){
            if(list.size() == 0|| list.get(list.size() - 1) < num)
                list.add(num);
            else {
                int i = Collections.binarySearch(list, num);
                //return -(low + 1);  // key not found
                list.set((i < 0)? - i - 1: i, num);
            }
        }
        return list.size();
    }

309.股票最佳时机含冷冻期

public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][3];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
    }

312.戳气球

public int maxCoins(int[] nums) {
        int[] temp = new int[nums.length + 2];
        for (int i = 0; i < nums.length; i++) {
            temp[i + 1] = nums[i];
        }
        temp[0] = temp[temp.length - 1] = 1;
        int[][] dp = new int[temp.length][temp.length];
        for (int i = temp.length - 3; i >= 0; i--) {
            for (int j = i + 2; j < temp.length; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = temp[i] * temp[j] * temp[k] + dp[i][k] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], sum);
                }
            }
        }
        return dp[0][temp.length - 1];
    }

322.零钱兑换

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount? -1: dp[amount];
    }

337.打家劫舍

 public int rob(TreeNode root) {
        int[] res = rob337(root);
        return Math.max(res[0], res[1]);
    }

    private int[] rob337(TreeNode root) {
        if(root == null)
            return new int[2];
        int[] left = rob337(root.left);
        int[] right = rob337(root.right);
        int[] res = new int[2];
        res[0] = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }

338.比特计数

public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            //res[i] = Integer.bitCount(i);
            res[i] = count338(i);
        }
        return res;
    }

    private int count338(int i) {
        int ans = 0;
        while (i > 0){
            i &= i - 1;
            ans++;
        }
        return ans;
    }

347.前k个高频元素

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v[1]));
        for (Map.Entry<Integer, Integer> entry: map.entrySet()){
            int num = entry.getKey(), val = entry.getValue();
            if(queue.size() == k){
                if(queue.peek()[1] < val){
                    queue.poll();
                    queue.add(new int[]{num, val});
                }
            }else
                queue.add(new int[]{num, val});
        }
        int[] res = new int[k];
        int i = 0;
        for (int[] num: queue){
            res[i++] = num[0];
        }
        return res;
    }

394.字符串解码

public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int m = 0;
        Deque<Integer> stack1 = new LinkedList<>();
        Deque<String> stack2 = new LinkedList<>();
        for (char c: s.toCharArray()){
            if(c == '['){
                stack1.push(m);
                m = 0;
                stack2.push(res.toString());
                res = new StringBuilder();
            }else if(c == ']'){
                StringBuilder temp = new StringBuilder();
                int curM = stack1.poll();
                for (int i = 0; i < curM; i++) {
                    temp.append(res);
                }
                res = new StringBuilder(stack2.poll() + temp);
            }else if(c >= '0'&& c <= '9')
                m = m * 10 + c - '0';
            else
                res.append(c);
        }
        return res.toString();
    }

406.根据身高重建队列

public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0]? o1[1] - o2[1]: o2[0] - o1[0]);
        List<int[]> list = new ArrayList<>();
        for (int[] i: people){
            list.add(i[1], i);
        }
        return list.toArray(new int[list.size()][2]);
    }

416.分割等和子集

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

437.路径总和

public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return helper437(root, targetSum, map, 0);
    }

    private int helper437(TreeNode root, int targetSum, Map<Integer, Integer> map, int curSum) {
        if(root == null)
            return 0;
        int res = 0;
        curSum += root.val;

        res += map.getOrDefault(curSum - targetSum, 0);
        map.put(curSum, map.getOrDefault(curSum,0) + 1);

        res += helper437(root.left, targetSum, map, curSum);
        res += helper437(root.right, targetSum, map, curSum);

        map.put(curSum, map.get(curSum) - 1);
        return res;
    }

438.字符串所有字母异位词索引

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int valid = p.length();
        for (char c: p.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        while (right < s.length()&& left < s.length()){
            if(need.containsKey(s.charAt(right))){
                window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
                if(window.get(s.charAt(right)) <= need.get(s.charAt(right)))
                    valid--;
            }
            while (valid == 0){
                if(right - left + 1 == p.length()) list.add(left);
                if(need.containsKey(s.charAt(left))){
                    window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                    if(window.get(s.charAt(left)) < need.get(s.charAt(left)))
                        valid++;
                }
                left++;
            }
            right++;
        }
        return list;
    }

448.找到缺失的数字

public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for(int num: nums){
            nums[(num - 1) % nums.length] += nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= nums.length){
                res.add(i + 1);
            }
        }
        return res;
    }

461.汉明距离

public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

494.目标和

public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num: nums){
            sum += num;
        }
        if(sum < target|| (sum - target) % 2 == 1)
            return 0;
        int n = (sum - target) / 2;
        int[][] dp = new int[nums.length + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= n; j++) {
                if(j >= nums[i - 1])
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[nums.length][n];
    }

538.二叉树到累加树

public TreeNode convertBST(TreeNode root) {
        int[] sum = new int[1];
        return helper538(root, sum);
    }

    private TreeNode helper538(TreeNode root, int[] sum) {
        if(root == null)
            return null;
        helper538(root.right, sum);
        sum[0] += root.val;
        root.val = sum[0];
        helper538(root.left, sum);
        return root;
    }

543.二叉树直径

public int diameterOfBinaryTree(TreeNode root) {
        int[] res = new int[1];
        dfs543(root, res);
        return res[0];
    }

    private int dfs543(TreeNode root, int[] res) {
        if(root == null)
            return 0;
        int left = dfs543(root.left, res);
        int right = dfs543(root.right, res);
        res[0] = Math.max(right + left, res[0]);
        return Math.max(left, right) + 1;
    }

560.和为K的子数组

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

581.最短无序子数组

public int findUnsortedSubarray(int[] nums) {
        int max = nums[0];
        int min = nums[nums.length - 1];
        int l = 0, r = -1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < max)
                r = i;
            else
                max = nums[i];
            if(nums[nums.length - i - 1] > min)
                l = nums.length - i - 1;
            else
                min = nums[nums.length - i - 1];
        }
        return r - l + 1;
    }

617.合并二叉树

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null|| root2 == null)
            return root1 == null? root2: root1;
        return dfs617(root1, root2);
    }

    private TreeNode dfs617(TreeNode root1, TreeNode root2) {
        if(root1 == null|| root2 == null)
            return root1 == null? root2: root1;
        root1.val += root2.val;
        root1.left = dfs617(root1.left, root2.left);
        root1.right = dfs617(root1.right, root2.right);
        return root1;
    }

621.任务调度器

public int leastInterval(char[] tasks, int n) {
        int[] nums = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            nums[tasks[i] - 'A']++;
        }
        Arrays.sort(nums);
        int maxCount = 1;
        int maxTime = nums[nums.length - 1];
        for (int i = nums.length - 1; i >= 1; i--) {
            if(nums[i] == nums[i - 1]){
                maxCount++;
            }else 
                break;
        }
        int res = (maxTime - 1) * (n + 1) + maxCount;
        return Math.max(res, tasks.length);
    }

647.回文子串

public int countSubstrings(String s) {
        int res = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                if(s.charAt(i) != s.charAt(j))
                    continue;
                dp[i][j] = j - i <= 2|| dp[i+1][j - 1];
                if(dp[i][j])
                    res++;
            }
        }
        return res;
    }

739.每日温度

public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty()&& temperatures[stack.peek()] < temperatures[i]){
                int cur = stack.pop();
                res[cur] = i - cur;
            }
            stack.push(i);
        }
        return res;
    }