Leetcode Hot100

思路：hashmap的使用，key存储值，value存储数组下标。

class Solution {
    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};
           }
           map.put(nums[i],i);
       }
       return new int[]{};
    }
}

思路：注意进位时，各种特殊条件。

/**
 * 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 dummy = new ListNode(-1);
        ListNode head =dummy;
        dummy.next =null;
        int value =0;
        int flag =0;
        while(l1!=null||l2!=null){
            value=0;
            if(l1!=null) value +=l1.val;
            if(l2!=null) value +=l2.val;
            int sum =value+flag;
            head.next =new ListNode(sum%10);
            flag=0;
            head=head.next;
            if(l1!=null)  l1=l1.next;
            if(l2!=null)  l2=l2.next;
            if(sum>=10) flag=1;
        }
        // head.next=l1!=null?l1:l2;
        if(flag==1) head.next =new ListNode(1);
        return dummy.next;
    }
}

思路：滑动窗口

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

思路：有时间复杂度的要求，只可以遍历一次，

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        //极端情况1，直接返回另外一个数组的值。
        if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        //极端情况2，查找K=1的数字，直接返回最小值
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        //极端情况3，查找K=1的数字，直接返回最小值
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }
}

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

思路：dp数组，存储之前的状态。

import java.util.Arrays;
class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.equals("")){
            return s;
        }
        //建立二维dp数组
        boolean[][] dp = new boolean[s.length()][s.length()];
        //结果记录
        int[] result = new int[2];
        //初始化
        for(int i = 0; i<s.length(); i++) dp[i][i] = true;
        //我们可以按照右下角开始遍历
        for(int i = s.length()-1; i>=0; i--){
            //j跟随遍历
            for(int j = i+1; j<s.length(); j++){
                //如果相等一定是回文
                if(s.charAt(i) == s.charAt(j)) {
                    //i和j相邻的时候
                    if(j-i == 1){
                        dp[i][j] = true;
                    }
                    //否则，根据内部子串判断
                    else{
                        dp[i][j] = dp[i+1][j-1]; 
                    }
                }
                //否则，不相等直接为false
                else{
                    dp[i][j] = false;
                }
                //如果自身符合条件，且为最长，则记录开始与结束
                if(dp[i][j]){
                    if(result[1]-result[0] <= j - i){
                        result[0] = i;
                        result[1] = j;
                    }
                }
            }
        }
        return s.substring(result[0],result[1]+1);
    }
}

思路：动态规划

1. 初始化：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-exLyUcWX-1653288860955)(/Users/mingxiaoxu/Library/Application Support/typora-user-images/image-20220508124138435.png)]

2. 动态转移方程：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rhr97cHc-1653288860956)(/Users/mingxiaoxu/Library/Application Support/typora-user-images/image-20220508124013181.png)]

https://leetcode-cn.com/problems/regular-expression-matching/solution/by-flix-musv/

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=1;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(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.'){
                   dp[i][j]=dp[i-1][j-1];
               }else if(p.charAt(j-1)=='*'){
                   if(s.charAt(i-1)!=p.charAt(j-2)&&p.charAt(j-2)!='.'){
                       dp[i][j]=dp[i][j-2];
                   }else{
                       dp[i][j] = dp[i][j-2] || dp[i-1][j];
                   }
               }
           }
       }
       return dp[m][n];
    }
}

思路：双指针

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

思路：排序加双指针法

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists =new ArrayList<>();
        List<Integer> list =new ArrayList<>();
       for(int i=0;i<nums.length;i++){
           if(i!=0&&nums[i]==nums[i-1]){
               continue;
           }
           //找出和为nums[i]的两个数；
           int left =i+1, right =nums.length-1;
           while(left<right){
             if(left-1>=i+1&&nums[left]==nums[left-1]) {
                left++;
               continue;
             }
             if(right+1<=nums.length-1&&nums[right]==nums[right+1]) {
                right--;
               continue;
             }
             if(nums[left]+nums[right]+nums[i]==0){
                 list.add(nums[i]);
                 list.add(nums[left]);
                 list.add(nums[right]);
                 lists.add(list);
                 list =new ArrayList<>();
                 left++;
                 right--;
             }else if(nums[left]+nums[right]+nums[i]<0){
                 left++;
             }else{
                 right--;
             }
       }
    }
           return lists;
   }
}

思路：回shuo法

class Solution {
    private String[] map = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private StringBuilder sb = new StringBuilder();
    private List<String> res =new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0) return res;
        backtrack(digits,0);
        return res;
    }

    private void backtrack(String digits, int index){
       if(sb.length()==digits.length()){
           res.add(sb.toString());
           return;
       }
       String s = map[digits.charAt(index)-'2'];
       for(int i=0;i<s.length();i++){
           sb.append(s.charAt(i));
            backtrack(digits,index+1);
            sb.deleteCharAt(sb.length()-1);
       }
    }
}

思路：快慢指针和注意边界条件。

/**
 * 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 dummy = new ListNode(0);
         dummy.next=head;
         ListNode pre = dummy, last =dummy;
         while(last.next!=null&&n!=0){
             last=last.next;
             n--;
         }
         while(last.next!=null){
             last=last.next;
             pre=pre.next;
         }

         pre.next=pre.next.next;
         return dummy.next;
    }
}

思路：使用HashMap+栈

class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()==0) return true;
        HashMap<Character,Character> map =new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Stack<Character> stack = new Stack<>();
        for(int i =0;i<s.length();i++){
            if(!stack.isEmpty() && stack.peek() == map.get(s.charAt(i))){
               stack.pop();
           }else{
               stack.push(s.charAt(i));
           }
       }
       return stack.isEmpty();
    }
}

思路：简单链表归并

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode resultList = new ListNode(0);
        ListNode pre = new ListNode(0);
        pre=resultList;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                pre.next = list1;
                list1= list1.next;
            }else{
                pre.next = list2;
                list2= list2.next;
            }
            pre =pre.next;
        }
        pre.next=list1!=null?list1:list2;
        return resultList.next;
    }
}

思路：使用回朔法找到所有符合要求的

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

思路：合并K个升序链表

/**
 * 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 mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

动态规划

https://leetcode.cn/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

class Solution {
    public int longestValidParentheses(String s) {
        int max =0;
        int[] dp =new int[s.length()];
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }else if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+2+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0);
                }
                max=Math.max(max,dp[i]);
            }
        }
        return max;
    }
}

思路：将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target - 1);
        int rightIdx = binarySearch(nums, target) - 1;
        if (leftIdx <= rightIdx && nums[leftIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    // 第一个大于 target 的数的下标
    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>(); //记录答案
    List<Integer> path = new ArrayList<>();  //记录路径

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0, target);
        return res;
    }
    public void dfs(int[] c, int u, int target) {
        if(target < 0) return ;
        if(target == 0)
        {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = u; i < c.length; i++){
            if( c[i] <= target)  
            {
                path.add(c[i]);
                dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是i
                path.remove(path.size()-1); //回溯，恢复现场
            }
        }
    }
}

思路：双指针法，注意到下标 ii 处能接的雨水量由 \textit{leftMax}[i]leftMax[i] 和 \textit{rightMax}[i]rightMax[i] 中的最小值决定。

class Solution {
    public int trap(int[] height) {
        int i= 0,j=height.length-1,sum=0;
        int leftMax=0;
        int rightMax=0;
        while(i<j){
            leftMax=Math.max(leftMax,height[i]);
            rightMax=Math.max(rightMax,height[j]);
            if(leftMax<rightMax){
                sum += leftMax- height[i];
                i++;
            }else{
                sum += rightMax- height[j];
                j--;
            }
        }
        return sum;
    }
}

思路：https://leetcode.cn/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

思路：原地旋转；

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

思路：字符串的题目考虑统计频率；

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

思路：走完这一生 如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻

class Solution {
    public int maxSubArray(int[] nums) {
       int[] dp = new int[nums.length];
       int maxValue =nums[0];
       dp[0] =nums[0];
       for(int i=1;i<nums.length;i++){
           dp[i]= Math.max(nums[i]+dp[i-1],nums[i]);
           maxValue=Math.max(maxValue,dp[i]);
       }
       return maxValue;
    }
}

思路：如果此位置可达，且大于最大距离，则更新最大距离为x+x(i)

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

1.先排序；

2.依次加入新数组；

3.如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾。

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

1. 找出状态转移方程
2. 找出base

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

Dp

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;i<m;i++){
         for(int j =0;j<n;j++){
             if(i==0&&j==0){
                dp[0][0] =grid[0][0];
             }else if(i==0){
                dp[0][j]=dp[0][j-1]+grid[0][j];
             }else if(j==0){
                dp[i][0]=dp[i-1][0]+grid[i][0];
             }else{
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
             }
         }
        }
        return dp[m-1][n-1];
    }
}

Dp

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

Dp

class Solution {
    public int minDistance(String word1, String word2) {
       int m = word1.length();
       int n = word2.length();
       int[][] dp=  new int[m+1][n+1];
       for(int i= 0 ;i< m+1 ;i++){
             for(int j= 0 ;j< n+1 ;j++){
              if(i==0&&j==0){
                  dp[0][0]=0;
              }else if(i==0){
                  dp[0][j]=j;
              }else if(j==0){
                  dp[i][0]=i;
              }else{
                  int temp = dp[i-1][j-1] ;
                  if(word1.charAt(i-1)!=word2.charAt(j-1)){
                      temp++;
                  }
                  dp[i][j] = Math.min(dp[i][j-1]+1,Math.min(dp[i-1][j]+1,temp));
              }
           }
       }
       return dp[m][n];
    }
}

滑动窗口。

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        // 定义一个数字，用来记录字符串 t 中出现字符的频率，也就是窗口内需要匹配的字符和相应的频率。
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c]++;
        }
        int left = 0, right = 0;
        int match = 0;  // 匹配字符的个数
        int minLen = s.length() + 1;   // 最大的子串的长度
        // 子串的起始位置 子串结束的位置(如果不存在这样的子串的话，start，end 都是 0，s.substring 截取就是 “”
        int start = 0, end = 0;
        while (right < s.length()){
            char charRight = s.charAt(right); // 右边界的那个字符
            //此时为不匹配状态,那么下一步操作，一定会匹配一个
            if (map[charRight] > 0){
                match++;
            } 
            //每移入一个字符，都--
            map[charRight]--; 
            right++;  // 右边界右移，这样下面就变成了 [)，方便计算窗口大小
            // 只要窗口内匹配的字符达到了要求，右边界固定，左边界收缩
            while (match == t.length()){
                int size = right - left;
                if (size < minLen){
                    minLen = size;
                    start = left;
                    end = right;
                }
                char charLeft = s.charAt(left);  // 左边的那个字符
                 // 左边的字符要移出窗口
                // 不在 t 中出现的字符，移出窗口，最终能够达到的最大值 map[charLeft] = 0
                // 此时为匹配状态，那么移出一定会造成不匹配，此时 match--
                if (map[charLeft] >=0) match--;
                 map[charLeft]++; 
                left++;  // 左边界收缩
            }
        }
        return s.substring(start, end);
    }
}

class Solution {
    List<Integer> t =new ArrayList<>();
    List<List<Integer>> ans =new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0,nums);
        return ans;
    }

    private void dfs(int cur, int[] nums){
        if(cur==nums.length){
          ans.add(new ArrayList<Integer>(t));
          return;  
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

class Solution {
    List<Integer> t =new ArrayList<>();
    List<List<Integer>> ans =new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0,nums);
        return ans;
    }

    private void dfs(int cur, int[] nums){
        if(cur==nums.length){
          ans.add(new ArrayList<Integer>(t));
          return;  
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

/**
 * 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> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
       dfs(root);
       return list;
    }

    private void dfs(TreeNode root){
       if(root==null) return;
       dfs(root.left);
       list.add(root.val);
       dfs(root.right);
    }
}

/**
 * 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) {
          if(root == null){
            return true;
        }
       return dfs(root.left,root.right);
    }

    private boolean dfs(TreeNode root1,TreeNode root2){
        if(root1 == null &&root2 ==null) return true;
        if(root1==null||root2==null) return false;
       return dfs(root1.right,root2.left)&&dfs(root1.left,root2.right)&&(root1.val==root2.val);

    }
}

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> lists =new ArrayList<>();
       List<TreeNode> queue =new LinkedList<>();
       List<Integer> list =new ArrayList<>();
       if(root==null) return lists;
       queue.add(root);
       int size=1;
       while(queue.size()!=0){
           TreeNode node = queue.remove(0);
           if(node.left!=null) queue.add(node.left);
           if(node.right!=null) queue.add(node.right);
           list.add(node.val);
           size--;
           if(size==0){
              lists.add(list);
              size= queue.size();
              list =new ArrayList<>();
           } 
       }
       return lists;
    }
}

/**
 * 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) {
        if(root==null) return 0;
        int left =maxDepth(root.left);
        int right =maxDepth(root.right);
        return Math.max(left,right)+1;
    } 
}

/**
 * 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 void flatten(TreeNode root) {
       if(root==null) return;
        flatten(root.left);
        flatten(root.right);
        TreeNode temp =root.right;
        root.right=root.left;
        root.left=null;
        while(root.right!=null) root=root.right;
        root.right=temp;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
      int minValue = Integer.MAX_VALUE;
      int maxProfit = 0;
      for(int i=0;i<prices.length;i++){
        if(prices[i]<minValue) minValue=prices[i];
        maxProfit=Math.max(maxProfit,prices[i]-minValue);
      }
      return maxProfit;
    }
}

/**
 * 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 max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
      if(root==null) return 0;
      helper(root);
      return max;
    }
    private int helper(TreeNode root){
       if(root==null) return 0;
       int left =Math.max(0,helper(root.left));
       int right =Math.max(0,helper(root.right));
       max= Math.max(max,left+right+root.val);
       return Math.max(left,right)+root.val;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
       HashSet<Integer> set = new HashSet<>();
       for(int num:nums){
           set.add(num);
       }
       int maxLen =0;
       int length =1;
       for(int i =0;i<nums.length;i++){
           if(!set.contains(nums[i]-1)){
               int value =nums[i];
               length =1;
               while(set.contains(value+1)){
                  value++;
                  length++;
               }
           }
         maxLen=Math.max(maxLen,length);
       }
       return maxLen;
    }
}

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow, fast;
        slow = head;
        fast = head;
        while(fast!=null){
            slow=slow.next;
            //防止空指针异常
            if(fast.next==null){
                return false;
            }
            fast=fast.next.next;
            //有环条件
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

/**
 * 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) {
        ListNode slow, fast;
        slow=head;
        fast=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next==null){
                return null;
            }
            fast=fast.next.next;
            if(slow==fast){
                break;
            }
        }
        if(fast==null) return null;
        slow=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

public ListNode sortList(ListNode head) {
        // 1、递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        ListNode midNode = middleNode(head);
        ListNode rightHead = midNode.next;
        midNode.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 3、当前层业务操作（合并有序链表）
        return mergeTwoLists(left, right);
    }
    
    //  找到链表中间节点（876. 链表的中间结点）
    private ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序链表（21. 合并两个有序链表）
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);
        ListNode curr = sentry;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next = l1 != null ? l1 : l2;
        return sentry.next;
    }

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            
            max = Math.max(max, imax);
        }
        return max;
    }
}

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int value =nums[0];
        int count =1;
       for(int i=1; i<nums.length;i++){
           if(nums[i] ==value){
            count++;   
           } else{
               count--;
               if(count==0){
                   value =nums[i];
                   count++;
               }
           }
       }
       return value;
    }
}

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

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

/**
 * 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 reverseList(ListNode head) {
         if(head==null||head.next==null) return head;
         ListNode dummy = new ListNode(0);
         dummy.next =null;
         while(head!=null){
             ListNode curr =head.next;
            head.next=dummy.next;
            dummy.next=head;
            head=curr;
         }
         return dummy.next;
    }
}

class Solution {
    // 存储有向图
    List<List<Integer>> edges;
    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;
    // 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
    int[] result;
    // 判断有向图中是否有环
    boolean valid = true;
    // 栈下标
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //初始化容器
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        //下标存储下一个节点，
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        // 如果没有环，那么就有拓扑排序
        return result;
    }

    public void dfs(int u) {
        // 将节点标记为「搜索中」
        visited[u] = 1;
        // 搜索其相邻节点
        // 只要发现有环，立刻停止搜索
        for (int v: edges.get(u)) {
            // 如果「未搜索」那么搜索相邻节点
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            // 如果「搜索中」说明找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        // 将节点标记为「已完成」
        visited[u] = 2;
        // 将节点入栈
        result[index--] = u;
    }
}

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

class Solution {

    int value;
    public int findKthLargest(int[] nums, int k) {
        sortArray(nums,0,nums.length-1,nums.length-k);
        return value;
    }
    private void sortArray(int[] nums,int low,int hight,int k){
        int temp =0;
        int i=low,j=hight;
        if(low==hight){
         value =nums[low]; 
         return;
        } 
        if(low<hight){
            temp=nums[low];
            while(i!=j){
                while(j>i&&nums[j]>=temp){
                    j--;
                }
                if(j>i){
                    nums[i]=nums[j];
                    i++;
                }
                while(j>i&&nums[i]<temp){
                    i++;
                }
                if(j>i){
                    nums[j]=nums[i];
                    j--;
                }
            }
        }
        nums[i]=temp;
        if(j==k){
             value= nums[j];
             return;
        }else if(j>k){
              sortArray(nums,low ,j-1,k);
        }else{
             sortArray(nums,j+1 ,hight,k);
        }
    } 
}

public int maximalSquare(char[][] matrix) {
    // base condition
    if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;

    int height = matrix.length;
    int width = matrix[0].length;
    int maxSide = 0;

    // 相当于已经预处理新增第一行、第一列均为0
    int[][] dp = new int[height + 1][width + 1];

    for (int row = 0; row < height; row++) {
        for (int col = 0; col < width; col++) {
            if (matrix[row][col] == '1') {
                dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;
                maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
            }
        }
    }
    return maxSide * maxSide;
}

/**
 * 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) {
       if(root==null) return root;
       invertTree(root.right);
       invertTree(root.left);
       TreeNode temp =root.left;
        root.left= root.right;
        root.right=temp;

        return root;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
          int n = nums.length;
          int[] dpLeft = new int[n];
          int[] dpRight= new int[n];
          int[] dp= new int[n];
          int i = 0;
     
          for(i = 0;i<n;i++){
              if(i==0){
                  dpLeft[i]=nums[i];
              }else{
                  dpLeft[i] = nums[i]*dpLeft[i-1];
              }
          }

         for(i = n-1;i>=0;i--){
              if(i==n-1){
                  dpRight[i]=nums[i];
              }else{
                  dpRight[i] = nums[i]*dpRight[i+1];
              }
          }

          for(i = 0;i<n;i++){
              if(i==0){
                  dp[i]=dpRight[i+1];
              }else if(i==n-1){
                  dp[i]=dpLeft[i-1];
              }else{
                  dp[i]=dpLeft[i-1]*dpRight[i+1];
              }
          }
          
          return dp;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int m= matrix.length;
        int n = matrix[0].length;

        int i =0;
        int j=n-1;

        while(i<m&&j>=0){
            if(target>matrix[i][j]){
                i++;
            }else if(target == matrix[i][j]){
                return true;
            }else{
                j--;
            }
        }
        return false;

    }
}

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int maxLen =1;
        for(int i =0;i<nums.length;i++){
            dp[i]=1;
        }
        for(int i =1;i<nums.length;i++){
                for(int j =0; j<i;j++){
                    if(nums[i]>nums[j]){
                    dp[i]= Math.max(dp[j]+1,dp[i]);
                }
                maxLen =Math.max(maxLen,dp[i]);
                }
        }
        return maxLen;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int[] minDp =new int[prices.length];
        minDp[0]=prices[0];
        int maxValue =minDp[0];
        for(int i=1;i<minDp.length;i++){
            minDp[i]=Math.min(minDp[i-1],prices[i]);
            if(i==1){
            maxValue=Math.max(maxValue,prices[i]-minDp[i-2]);
            }else{
                maxValue=Math.max(maxValue,prices[i]-minDp[i-2]);
            }
        }
        return maxValue;
    }
}

https://leetcode.cn/problems/burst-balloons/solution/dong-tai-gui-hua-tao-lu-jie-jue-chuo-qi-qiu-wen-ti/

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

class Solution {
    public int coinChange(int[] coins, int amount) {
         int[] dp = new int[amount+1];
         for(int i=0;i<amount;i++){
             int(j=0;j<coins.length;j++){
                 if(coins[i]<=j){
                     dp[i]=Math.min(dp[i],dp[])
                 }
             }
         }
    }
}

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        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];
    }
}

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

class Solution {
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }
}

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}

class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

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

class Solution {
    int ans=0;
    //前序遍历每个结点
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return ans;
        //双重递归:以此节点为树的根节点，进行查找
        dfs(root,sum);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return ans;
    }
    //以此节点为起点，查找符合条件的路径
    private void dfs(TreeNode root,int sum){
        if(root==null) return;
        sum=sum-root.val;
        if(sum==0) ans++;
        dfs(root.left,sum);
        dfs(root.right,sum);
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];
            
            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
       List<Integer> list = new ArrayList<>();
       for(int i=0;i<nums.length;i++){
           int target =Math.abs(nums[i])-1;
           if(nums[target]>0){
            nums[target]=-nums[target];
           }
        }
        for(int i=0;i<nums.length;i++){
          if(nums[i]>0){
              list.add(i+1);
          }
        }
        return list;
    }
}

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }
}

https://leetcode.cn/problems/target-sum/solution/dong-tai-gui-hua-si-kao-quan-guo-cheng-by-keepal/

    public static int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 绝对值范围超过了sum的绝对值范围则无法得到
        if (Math.abs(s) > Math.abs(sum)) return 0;

        int len = nums.length;
        // - 0 +
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2;
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < t; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + s];
    }

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

/**
 * 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 diameterOfBinaryTree(TreeNode root) {
         if(root==null) return 0;
         dfs(root);
         return max;
    }
    int max =0;
    private int dfs(TreeNode root){
       if(root==null) return 0;
         int left = dfs(root.left);
         int right = dfs(root.right);
         max = Math.max(max,left+right);
         return Math.max(left,right)+1;
    }
}

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PEQ7ilwh-1653288860957)(/Users/mingxiaoxu/Library/Application Support/typora-user-images/image-20220516103959037.png)]

class Solution {
    public int findUnsortedSubarray(int[] nums) {
       int l=-1,r=-1;
       int max =Integer.MIN_VALUE, min =Integer.MAX_VALUE;
       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==-1?0:r-l+1;
    }
}

/**
 * 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) {
        //关键点：如果某一个为空，则直接返回另外一个，另外一个不管为不为空都可以
        if (root1 == null)
            return root2;
         //关键点：如果某一个为空，则直接返回另外一个，另外一个不管为不为空都可以
        if (root2 == null)
            return root1;
        root1.val += root2.val;//精髓，两个相加，都不为空的话
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

public int leastInterval(char[] tasks, int n) {
        //统计每个任务出现的次数，找到出现次数最多的任务
        int[] hash = new int[26];
        for(int i = 0; i < tasks.length; ++i) {
            hash[tasks[i] - 'A'] += 1;
        }
        Arrays.sort(hash);
        //因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列（X看作预占位置）
        //该序列长度为
        int minLen = (n+1) *  (hash[25] - 1) + 1;

        //此时为了尽量利用X所预占的空间（贪心）使得整个执行序列长度尽量小，将剩余任务往X预占的空间插入
        //剩余的任务次数有两种情况：
        //1.与A出现次数相同，比如B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1
        //2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列
        //直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为n
        for(int i = 24; i >= 0; --i){
            if(hash[i] == hash[25]) ++ minLen;
        }
        //当所有X预占的位置插满了怎么办？
        //在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件
        //因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度
        return Math.max(minLen, tasks.length);
    }

class Solution {
    public int countSubstrings(String s) {
        // 动态规划法
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans = 0;

        for (int j = 0; j < s.length(); j++) {
            for (int i=j; i>=0; i--) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }

        return ans;
    }
}

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