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

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

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

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //以nums[i]结尾的最大递增子序列长度
        int[][] dp = new int[n][n];
        Arrays.fill(dp,1);
        int max = 1;
        for(int i = 1; i < n;i++){
            for(int j = 0; j < i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
                max = Math.max(dp[i],max);
            }
        }
        return max;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        //以nums[i]结尾的最大乘积子数组
        int n = nums.length;
        int[] maxF = new int[n];
        int[] minF = new int[n];
        maxF[0] = minF[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < n;i++){
            maxF[i] = Math.max(Math.max(maxF[i-1] * nums[i],minF[i - 1] * nums[i]),nums[i]);
            minF[i] = Math.min(Math.min(maxF[i-1] * nums[i],minF[i - 1] * nums[i]),nums[i]);
            max = Math.max(maxF[i],max);
        }
        return max;
    }
}

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

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String s : strs){
            char[] chs = s.toCharArray();
            Arrays.sort(chs);
            String key = new String(chs);
            map.putIfAbsent(key,new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

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

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

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

class Solution {
    public void moveZeroes(int[] nums) {
        int l = 0, r = 1;
        int n = nums.length;
        while (r < n) {
            if (nums[l] == 0) {
                int t = nums[r];
                nums[r] = nums[l];
                nums[l] = t;
            }
            if (nums[l] != 0) {
                l++;
            }
            r++;
        }
    }
}

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int n = height.length;
        int l = 0, r = 1;
        for (l = 0; l < n;l++) {
            for(r = l + 1;r < n;r++){
                int h = Math.min(height[l], height[r]);
                int len = r - l;
                res = Math.max(res, h * len);
            }
        }
        return res;
    }
}

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int n = height.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int h = Math.min(height[l], height[r]);
            int len = r - l;
            res = Math.max(res, h * len);
            if(height[l] >= height[r]){
                r--;
            }else{
                l++;
            }
        }
        return res;
    }
}

import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); // 1. 先排序
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            // 2. 跳过重复的第一个数
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    // 3. 跳过重复的第二个和第三个数
                    while (j < k && nums[j] == nums[j - 1]) j++;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                } else if (sum < 0) {
                    j++; // 总和小了 -> 增大左指针
                } else {
                    k--; // 总和大了 -> 减小右指针
                }
            }
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            List<List<Integer>> list = threeSum(nums, i + 1, target - nums[i]);
            for (List<Integer> t : list) {
                List<Integer> l = new ArrayList<>(t);
                l.add(nums[i]);
                res.add(l);
            }
        }
        return res;
    }
    List<List<Integer>> threeSum(int[] nums, int start, long target) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = start; i < n - 2; i++) {
            if (i > start && nums[i] == nums[i - 1])
            continue;
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                long sum = (long)nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    ans.add(List.of(nums[i],nums[left],nums[right]));
                    while (left < right && nums[left] == nums[left + 1])
                    left++;
                    while (left < right && nums[right] == nums[right - 1])
                    right--;
                    left++;
                    right--;
                }else if(sum > target){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, 0, 4, (long) target);
    }
    List<List<Integer>> kSum(int[] nums, int start, int k, long target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (n < k || k < 2) return res;
        if (k == 2) {
            return twoSum(nums, start, target);
        }
        for (int i = start; i < n; i++) {
            // 去重：同层不能重复
            if (i > start && nums[i] == nums[i - 1])
            continue;
            long newTarget = target - nums[i];
            List<List<Integer>> next = kSum(nums, i + 1, k - 1, newTarget);
            for (List<Integer> row : next) {
                row.add(nums[i]);
                res.add(row);
            }
        }
        return res;
    }
    List<List<Integer>> twoSum(int[] nums, int start, long target) {
        List<List<Integer>> res = new ArrayList<>();
        int left = start, right = nums.length - 1;
        while (left < right) {
            long sum = (long) nums[left] + nums[right];
            if (sum == target) {
                res.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                int lv = nums[left], rv = nums[right];
                while (left < right && nums[left] == lv) left++;
                while (left < right && nums[right] == rv) right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] cnt = new int[26];
        for(char c : p.toCharArray()){
            cnt[c - 'a']++;
        }
        int l = 0;
        int[] windows = new int[26];
        for(int r = 0; r < s.length();r++){
            windows[s.charAt(r) - 'a']++;
            while(r - l + 1 >= p.length()){
                if(Arrays.equals(windows,cnt)){
                    res.add(l);
                }
                windows[s.charAt(l) - 'a']--;
                l++;
            }
        }
        return res;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int res = 0;
        int l = 0,r = 0;
        for(r = 0; r < s.length(); r++){
            char c = s.charAt(r);
            while(set.contains(c)){
                char ch = s.charAt(l);
                set.remove(ch);
                l++;
            }
            set.add(c);
            res = Math.max(res,r - l + 1);
        }
        return res;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        if(nums.length == 1){
            return nums[0] == k ? 1 : 0;
        }
        int cnt = 0;
        int l = 0;
        int total = 0;
        for(int r = 0; r < nums.length;r++){
            total += nums[r];
            while(total >= k){
                if(total == k){
                    cnt++;
                }
                total -= nums[l];
                l++;
            }
        }
        return cnt;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        int[] preSum = new int[n + 1];
        for(int i = 1; i <= n;i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for(int i = 0; i < n;i++){
            for(int j = i + 1; j <= n;j++){
                if(preSum[j] - preSum[i] == k){
                    res++;
                }
            }
        }
        return res;
    }
}

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->(b - a));
        List<Integer> memo = new ArrayList<>();
        int right = 0;
        int left = 0;
        int n = nums.length;
        while(right < n){
            pq.add(nums[right]);
            while(right - left + 1 == k){
                memo.add(pq.peek());
                pq.remove(nums[left]);
                left++;
            }
            right++;
        }
        int size = memo.size();
        int[] res = new int[size];
        for(int i = 0; i < size;i++){
            res[i] = memo.get(i);
        }
        return res;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        int n = nums.length;
        for(int i = 0; i < n;i++){
            if(!deque.isEmpty() && deque.peekFirst() <= i - k ){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
            if(i >= k - 1){
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int m = (int)(Math.log(n)/Math.log(2)) + 1;//区间长度的上界
        int[][] st = new int[n][m + 1];
        //st[i][j] 表示从i，i + 2 ^ j -1区间的最值，区间长度为2^j
        int[] log2 = new int[n + 1];
        log2[1] = 0;
        for(int i = 2; i <= n;i++){
            log2[i] = log2[i >> 1] + 1;
        }
        for(int i = 0; i < n;i++){
            st[i][0] = nums[i];
        }
        //i + 2 ^j的区间最值
        //st[i][j-1]是将st[i][j]分成大小相等的两半
        for(int j = 1; j < m;j++){
            int len = 1 << j;
            int half = len >> 1;
            for(int i = 0; i + len <= n;i++){
                st[i][j] = Math.max(st[i][j-1],st[i+half][j-1]);
            }
        }
        //结果的大小为n - k + 1
        //i<=size - 1即i <= n - k + 1 - 1 即i + k<= n
        int[] res = new int[n - k + 1];
        for(int i = 0; i + k <= n;i++){
            int len = k;
            int j = log2[len];
            int left = st[i][j];
            int right = st[i + len - (1 << j)][j];
            //查询公式ans = max(st[L][j], st[R - (1 << j) + 1][j])
            res[i] = Math.max(left,right);
        }
        return res;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int valid = 0;
        int left = 0, right = 0;
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char cr = s.charAt(right);
            right++;
            if (need.containsKey(cr)) {
                window.put(cr, window.getOrDefault(cr, 0) + 1);
                if (window.get(cr).equals(need.get(cr))) {
                    valid++;
                }
            }
            while (valid == need.size()) {
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char cl = s.charAt(left);
                left++;
                if (window.containsKey(cl)) {
                    if (window.get(cl).equals(need.get(cl))) {
                        valid--;
                    }
                    window.put(cl, window.get(cl) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int max = Integer.MIN_VALUE;
        int n = nums.length;
        int[] preSum = new int[n + 1];
        for(int i = 1; i <= n;i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <= n;i++){
            max = Math.max(max,preSum[i] - min);
            min = Math.min(min,preSum[i]);
        }
        return max;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int preSum = 0;
        int res = Integer.MIN_VALUE;
        int preMin = 0;
        for (int num : nums) {
            preSum += num;
            res = Math.max(res,preSum - preMin);
            preMin = Math.min(preMin,preSum);
        }
        return res;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length;i++){
            curSum = Math.max(nums[i],curSum + nums[i]);
            maxSum = Math.max(maxSum,curSum);
        }
        return maxSum;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        int n = intervals.length;
        for(int i = 0; i < n;i++){
            int left = i,right = i + 1;
            while(right < n && intervals[left][1] >= intervals[right][0]){
                intervals[left][1] = Math.max(intervals[left][1], intervals[right][1]);
                right++;
            }
            res.add(new int[]{intervals[left][0],intervals[left][1]});
            i = right - 1;
        }
        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> res = new ArrayList<>();
        int n = intervals.length;
        int i = 0;
        while (i < n) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            // 吸收所有与当前区间重叠的区间，并更新右端
            while (i + 1 < n && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            res.add(new int[]{left, right});
            i++; // 继续处理下一个未合并的区间
        }
        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return new int[0][];
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> res = new ArrayList<>();
        int[] cur = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= cur[1]) {
                cur[1] = Math.max(cur[1], intervals[i][1]);
            } else {
                res.add(cur);
                cur = intervals[i];
            }
        }
        res.add(cur);
        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for(int i = 0; i < n - k;i++){
            list1.add(nums[i]);
        }
        for(int i = n - k; i < n;i++){
            list2.add(nums[i]);
        }
        list2.addAll(list1);
        for (int i = 0; i < n; i++) {
            nums[i] = list2.get(i);
        }
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k , n - 1);
    }
    public void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int t = nums[right];
            nums[right] = nums[left];
            nums[left] = t;
            left++;
            right--;
        }
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] res = new int[n];
        pre[0] = 1;
        for(int i = 1; i <= n;i++){
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        int[] suf = new int[n];
        suf[n - 1] = 1;
        for(int i = n - 2; i >= 0;i--){
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        for(int i = 0; i < n;i++){
            res[i] = pre[i] * suf[i];
        }
        return res;
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        int m = matrix.length, n = matrix[0].length;
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(matrix[i][j] == 0){
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        for(int row : rows){
            for(int i = 0; i < n;i++){
                matrix[row][i] = 0;
            }
        }
        for(int col : cols){
            for(int i = 0; i < m;i++){
                matrix[i][col] = 0;
            }
        }
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int clos = matrix[0].length;
        boolean[] row = new boolean[rows];
        boolean[] clo = new boolean[clos];
        for(int i = 0; i < rows;i++){
            for(int j = 0; j < clos; j++){
                if(matrix[i][j] == 0){
                    row[i] = true;
                    clo[j] = true;
                }
            }
        }
        for(int i = 0; i < rows;i++){
            for(int j = 0; j < clos; j++){
                if(row[i] || clo[j]){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;
        for(int i = 0; i < n;i++){
            if(matrix[i][0] == 0){
                firstCol = true;
                break;
            }
        }
        for(int i = 0;i < m;i++){
            if(matrix[0][i] == 0){
                firstRow = true;
                break;
            }
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j < m;j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j < m;j++){
                if(matrix[i][0] == 0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
        }
        if(firstRow){
            for(int j = 0; j < m;j++){
                matrix[0][j] = 0;
            }
        }
        if(firstCol){
            for(int i = 0; i < n;i++){
                matrix[i][0] = 0;
            }
        }
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int top = 0, bottom = m - 1,left = 0, right = n-1;
        int size = m * n;
        while(res.size() < size){
            for(int i = left; i <= right && res.size() < size;i++){
                res.add(matrix[top][i]);
            }
            top++;
            for(int i = top; i <= bottom && res.size() < size;i++){
                res.add(matrix[i][right]);
            }
            right--;
            for(int i = right;i >= left && res.size() < size; i--){
                res.add(matrix[bottom][i]);
            }
            bottom--;
            for(int i = bottom; i >= top && res.size() < size;i--){
                res.add(matrix[i][left]);
            }
            left++;
        }
        return res;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length;i++){
            set.add(nums[i]);
        }
        for(int i = 1; i <= nums.length;i++ ){
            if(!set.contains(i)){
                return i;
            }
        }
        return nums.length + 1;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n;i++){
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                swap(nums,nums[i] - 1,i);
            }
        }
        for(int i = 0; i < n;i++){
            if(nums[i] != i + 1){
                return i+1;
            }
        }
        return n + 1;
    }
    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean flag = false;
        for(int[] nums : matrix){
            int res = binarySerach(nums,target);
            if(res != -1){
                flag = true;
            }
        }
        return flag;
    }
    public int binarySerach(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

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

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0; i < m;i++){
            for(int j = i + 1; j < n;j++){
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
        for(int[] row : matrix){
            swap(row);
        }
    }
    public void swap(int[] row){
        int i = 0, j = row.length - 1;
        while(i < j){
            int t = row[i];
            row[i] = row[j];
            row[j] = t;
            i++;
            j--;
        }
    }
}

最先想到的是记录遍历两个链表的节点
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != null){
            set.add(p1);
            p1 = p1.next;
        }
        while(p2 != null){
            if(set.contains(p2)){
                break;
            }
            p2 = p2.next;
        }
        return p2;
    }
}

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode cur1 = headA;
    ListNode cur2 = headB;
    while(cur1 != cur2){
        cur1 = cur1 == null ? headB : cur1.next;
        cur2 = cur2 == null ? headA : cur2.next;
    }
    return cur1;
}
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode cur = head;
        List<Integer> list = new ArrayList();
        while(cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int left = 0, right = list.size() - 1;
        while(left < right){
            if(list.get(left) != list.get(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = mid(head);
        ListNode head2 = reverse(mid);
        while(head2 != null){
            if(head.val != head2.val){
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    ListNode mid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    ListNode reverse(ListNode mid){
        ListNode cur = mid;
        ListNode next = mid.next;
        cur.next = null;
        while(next != null){
            ListNode t = next.next;
            next.next = cur;
            cur = next;
            next = t;
        }
        return cur;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        int cnt = 0;
        ListNode cur = head;
        while(cur != null){
            cur = cur.next;
            cnt++;
        }
        cur = head;
        cnt /= 2;
        while(cnt > 1){
            cur = cur.next;
            cnt--;
        }
        ListNode head2 = reverse(cur.next);
        ListNode head1 = head;
        while(head2!=null){
            if(head1.val != head2.val){
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        if(head == null){
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head, fast = head.next;
        while(slow != fast && fast != null&&fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow == fast;
    }
}

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

class Solution {
    int[] visited;
    List<List<Integer>> edges;
    boolean flag = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        edges = new ArrayList<>();
        for(int i = 0; i < numCourses;i++){
            edges.add(new ArrayList<>());
        }
        for(int[] edge : prerequisites){
            edges.get(edge[1]).add(edge[0]);
        }
        for(int i = 0; i < numCourses;i++){
            if(visited[i] == 0){
                dfs(i);
            }
        }
        return flag;
    }
    void dfs(int i){
        visited[i] = 1;
        for(int v : edges.get(i)){
            if(visited[v] == 0){
                dfs(v);
                if(!flag){
                    return;
                }
            }else if(visited[v] == 1){
                flag = false;
                return;
            }
        }
        visited[i] = 2;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int size = 0;
        ListNode cur = dummy;
        while (cur.next != null) {
            size++;
            cur = cur.next;
        }
        int steps = size - n;
        ListNode prev = dummy;
        for (int i = 0; i < steps; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;
        return second;
    }
}

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

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode t = root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(t);
        return root;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode right = invertTree(root.left);
        TreeNode left = invertTree(root.right);
        root.left = left;
        root.right = right;
        return root;
    }
}

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

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        res.add(root.val);
        dfs(root.right);
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        return dfs(left,right);
    }
    boolean dfs(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        boolean l = dfs(left.left,right.right);
        boolean r = dfs(left.right,right.left);
        return l && r;
    }
}

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root);
        return max;
    }
    int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        max = Math.max(max,l + r);
        return Math.max(l,r) + 1;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if(root == null){
            return res;
        }
        q.offer(root);
        while(!q.isEmpty()){
            int n = q.size();
            List<Integer> list = new ArrayList<>();
            while(n-- > 0){
                TreeNode cur = q.poll();
                list.add(cur.val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root,0);
        return res;
    }
    void dfs(TreeNode root,int index){
        if(root == null){
            return;
        }
        if(index == res.size()){
            res.add(new ArrayList<>());
        }
        res.get(index).add(root.val);
        dfs(root.left,index + 1);
        dfs(root.right,index + 1);
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        return dfs(nums,0,n - 1);
    }
    TreeNode dfs(int[] nums,int left,int right){
        if(left > right){
            return null;
        }
        int mid = (left + right) >>> 1;
        TreeNode root = new TreeNode(nums[mid]);
        //左区域的重点就是左子树的根节点
        root.left = dfs(nums,left,mid-1);
        //右区域的重点就是右子树的根节点
        root.right = dfs(nums,mid + 1, right);
        return root;
    }
}

class Solution {
    List<Integer> res = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        dfs(root);
        for(int i = 1; i < res.size();i++){
            if(res.get(i - 1) >= res.get(i)){
                return false;
            }
        }
        return true;
    }
    void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        res.add(root.val);
        dfs(root.right);
    }
}

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean l = isValidBST(root.left);
        if(pre >= root.val){
            return false;
        }
        pre = root.val;
        boolean r = isValidBST(root.right);
        return l && r;
    }
}

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        dfs(root);
        return list.get(k - 1);
    }
    void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

class Solution {
    int res = 0;
    int cnt = 1;
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        dfs(root,k);
        return res;
    }
    void dfs(TreeNode root,int k){
        if(root == null){
            return;
        }
        dfs(root.left,k);
        if(cnt == k){
            res = root.val;
        }
        cnt++;
        dfs(root.right,k);
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        ArrayDeque<TreeNode> q= new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()){
            int n = q.size();
            int first = q.peekLast().val;
            while(n-- > 0){
                TreeNode cur = q.poll();
                int val = cur.val;
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            res.add(first);
        }
        return res;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q= new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()){
            int n = q.size();
            int first = q.peek().val;
            while(n-- > 0){
                TreeNode cur = q.poll();
                int val = cur.val;
                if(cur.right != null){
                    q.offer(cur.right);
                }
                if(cur.left != null){
                    q.offer(cur.left);
                }
            }
            res.add(first);
        }
        return res;
    }
}

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root,0);
        for(List<Integer> l : list){
            res.add(l.get(0));
        }
        return res;
    }
    void dfs(TreeNode root,int index){
        if(root == null){
            return;
        }
        if(index == list.size() ){
            list.add(new ArrayList<>());
        }
        list.get(index).add(root.val);
        dfs(root.right,index + 1);
        dfs(root.left,index + 1);
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root,0,res);
        return res;
    }
    void dfs(TreeNode root,int index,List<Integer> res){
        if(root == null){
            return;
        }
        if(index == res.size() ){
            res.add(root.val);
        }
        dfs(root.right,index + 1,res);
        dfs(root.left,index + 1,res);
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.right = left;
        root.left = null;
        TreeNode cur = root;
        while(cur.right != null){
            cur = cur.right;
        }
        cur.right = right;
    }
}

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < preorder.length;i++){
            map.put(inorder[i],i);
        }
        return build(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
    }
    TreeNode build(int[] preorder,int preL,int preR,int[] inorder,int inL,int inR){
        if(preL > preR){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preL]);
        int index = map.get(root.val);
        int size = index - inL;
        root.left = build(preorder,preL + 1,preL + size,inorder,inL,index - 1);
        root.right = build(preorder,preL + size + 1,preR,inorder,index + 1,inR);
        return root;
    }
}

class Solution {
    int preP;
    int inP;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return recursion(preorder,inorder,Integer.MAX_VALUE);
    }
    TreeNode recursion(int[] preorder, int[] inorder,int stop) {
        // 前序遍历到头了,整体结束
        if (preP == preorder.length) return null;
        // 当前子树的中序范围已经结束了
        if (inorder[inP] == stop) {
            inP++;
            return null;
        }
        // 从前序取出根节点
        TreeNode root = new TreeNode(preorder[preP++]);
        // 构建左子树时,中序遍历是左-根-右,左子树的边界就是当前节点
        root.left = recursion(preorder,inorder,root.val);
        // 构建右子树,中序遍历是左-根-右,右子树没有边界
        root.right = recursion(preorder,inorder,stop);
        return root;
    }
}

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        //负数就不选
        int l = Math.max(dfs(root.left),0);
        int r = Math.max(dfs(root.right),0);
        //全局最大的路径
        max = Math.max(max,l + r + root.val);
        return root.val + Math.max(l,r);
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return root;
        }
        if(p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null){
            return root;
        }
        return left != null ? left : right;
    }
}

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        long res = dfs(root,(long)targetSum);
        res += pathSum(root.left,targetSum);
        res += pathSum(root.right,targetSum);
        return (int)res;
    }
    long dfs(TreeNode root,long targetSum){
        long res = 0;
        if(root == null){
            return 0;
        }
        if(root.val == targetSum){
            res++;
        }
        res += dfs(root.left,targetSum - root.val);
        res += dfs(root.right,targetSum - root.val);
        return res;
    }
}

class Solution {
    Map<Long,Integer> map = new HashMap<>();
    int targetSum;
    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        map.put(0L,1);
        return dfs(root,0L);
    }
    int dfs(TreeNode root,Long curSum){
        if(root == null){
            return 0;
        }
        curSum += root.val;
        int cnt = map.getOrDefault(curSum - targetSum,0);
        map.put(curSum,map.getOrDefault(curSum,0) + 1);
        cnt += dfs(root.left,curSum);
        cnt += dfs(root.right,curSum);
        map.put(curSum,map.getOrDefault(curSum,0) - 1);
        if(map.get(curSum) == 0){
            map.remove(curSum);
        }
        return cnt;
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root,0);
        return res;
    }
    void dfs(TreeNode root,int depth){
        if(root == null){
            return;
        }
        if(res.size() == depth){
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        dfs(root.left,depth + 1);
        dfs(root.right,depth + 1);
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> list = new ArrayList<>();
            while(size-- > 0){
                TreeNode cur = q.poll();
                int val = cur.val;
                list.add(val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

class Solution {
    List<List<Integer>> edges = new ArrayList<>();
    int[] visited;
    boolean flag = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] edge : prerequisites) {
            edges.get(edge[1]).add(edge[0]);
        }
        /*构建邻接表 [[1,0]]
        0:[]
        1:[0]
        */
        // 遍历所有节点（防止图不连通）
        for (int i = 0; i < numCourses; i++) {
            // 如果某个节点未被访问，则对其执行 DFS
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return flag;
    }
    void dfs(int i) {
        visited[i] = 1;
        //遍历当前节点的所有出度节点
        for (int v : edges.get(i)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!flag) {
                    return;
                }
            }else if(visited[v] == 1){
                flag = false;
                return;
            }
        }
        visited[i] = 2;
    }
}

class Solution {
    boolean[][] visited;
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        visited = new boolean[m][n];
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(!visited[i][j] && grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    void dfs(char[][] grid,int i,int j){
        if(i < 0 || j < 0 || i >= grid.length|| j >= grid[0].length||grid[i][j] == '0' || visited[i][j]){
            return;
        }
        visited[i][j] = true;
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

class Solution {
    int count;
    int[] parent;
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = {{1,0},{0,1}};
        count = 0;
        parent = new int[m * n];
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                int index = i * n + j;
                if(grid[i][j] == '1'){
                    parent[index] = index;
                    count++;
                }else{
                    parent[index] = -1;
                }
            }
        }
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(grid[i][j] == '1'){
                    int index1 = i * n + j;
                    for(int[] dir : dirs){
                        int ni = dir[0] + i;
                        int nj = dir[1] + j;
                        int index2 = ni * n +nj;
                        union(index1,index2);
                    }
                }
            }
        }
    }
    return getCount();
}
void union(int p,int q){
    int rootP = find(p);
    int rootQ = find(q);
    if(rootP == rootQ){
        return;
    }
    parent[rootQ]= rootP;
    count--;
}
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
int getCount() {
    return count;
}
}

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

class Solution {
    static final String[] menu = new String[] {
        " ", //0
        "", //1
        "abc", //2
        "def", //3
        "ghi", //4
        "jkl", //5
        "mno", //6
        "pqrs", //7
        "tuv", //8
        "wxyz" //9
    };
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        dfs(digits,0);
        return res;
    }
    void dfs(String digits,int idx){
        if(path.length() == digits.length()){
            res.add(path.toString());
            return;
        }
        int index = digits.charAt(idx) - '0';
        String s = menu[index];
        for(char c : s.toCharArray()){
            path.append(c);
            dfs(digits,idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        visited = new boolean[n];
        dfs(nums);
        return res;
    }
    void dfs(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length ; i++) {
            if (visited[i]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            dfs(nums);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

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

class Solution {
    StringBuilder path = new StringBuilder();
    boolean[][] visited;
    boolean found = false;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length;i++){
            for(int j = 0; j < board[0].length;j++){
                dfs(board,i,j,word);
                if(found){
                    return true;
                }
            }
        }
        return false;
    }
    void dfs(char[][] board,int i, int j,String word){
        if(path.length() == word.length()){
            found = true;
            return;
        }
        if(found){
            return;
        }
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j]){
            return;
        }
        int idx = path.length();
        if(board[i][j] != word.charAt(idx)){
            return;
        }
        path.append(board[i][j]);
        visited[i][j] = true;
        dfs(board,i - 1,j,word);
        dfs(board,i + 1,j,word);
        dfs(board,i,j - 1,word);
        dfs(board,i,j + 1,word);
        visited[i][j] = false;
        path.deleteCharAt(path.length() - 1);
    }
}

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        len = 2 * n;
        dfs(n,n);
        return res;
    }
    void dfs(int left,int right){
        if(right < left){
            return;
        }
        if(left < 0 || right < 0){
            return;
        }
        if(left == 0 && right == 0){
            res.add(path.toString());
            return;
        }
        path.append('(');
        dfs(left - 1,right);
        path.deleteCharAt(path.length() - 1);
        path.append(')');
        dfs(left,right - 1);
        path.deleteCharAt(path.length() - 1);
    }
}

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        dfs(s,0);
        return res;
    }
    void dfs(String s,int start){
        if(start == s.length()){
            res.add(new ArrayList<String>(path));
        }
        for(int i = start; i < s.length();i++){
            String str = s.substring(start,i + 1);
            if(!f(str)){
                continue;
            }
            path.add(str);
            dfs(s,i + 1);
            path.remove(path.size() - 1);
        }
    }
    boolean f(String s){
        if(s.length() == 1){
            return true;
        }
        int l = 0,r = s.length() - 1;
        while(l < r){
            if(s.charAt(l) != s.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

class Solution {
    List<List<String>> res = new ArrayList<>();
    char[][] board;
    public List<List<String>> solveNQueens(int n) {
        board = new char[n][n];
        for(char[] row : board){
            Arrays.fill(row,'.');
        }
        dfs(n,0);
        return res;
    }
    void dfs(int n,int row){
        if(row == n){
            res.add(build(board));
            return;
        }
        for(int i = 0; i < n;i++){
            if(valid(board,row,i)){
                board[row][i] = 'Q';
                dfs(n,row + 1);
                board[row][i] = '.';
            }
        }
    }
    boolean valid(char[][] board,int row,int col){
        int n = board[0].length;
        //同列
        for(int i = 0; i < row;i++){
            if(board[i][col] == 'Q') return false;
        }
        //左上
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0;i--,j--){
            if(board[i][j] == 'Q') return false;
        }
        //右上
        for(int i = row - 1, j = col + 1; i >= 0 && j < n;i--,j++){
            if(board[i][j] == 'Q') return false;
        }
        return true;
    }
    List<String> build(char[][] board){
        List<String> list = new ArrayList<>();
        for(int i = 0; i < board.length;i++){
            String s = new String(board[i]);
            list.add(s);
        }
        return list;
    }
}

class Solution {
    List<List<String>> res = new ArrayList<>();
    int n;
    int[] queen;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        queen = new int[n];
        Arrays.fill(queen,-1);
        dfs(0);
        return res;
    }
    void dfs(int row){
        if(row == n){
            res.add(build());
            return;
        }
        for(int i = 0; i < n;i++){
            if(valid(row,i)){
                queen[row] = i;
                dfs(row + 1);
                queen[row] = -1;
            }
        }
    }
    boolean valid(int row, int col){
        for(int r = 0; r < row;r++){
            int c = queen[r];
            //同列，同对角线
            if(c == col || Math.abs(r - row) == Math.abs(c - col)){
                return false;
            }
        }
        return true;
    }
    List<String> build(){
        List<String> board = new ArrayList<>();
        for(int i = 0; i < n;i++){
            char[] chs = new char[n];
            Arrays.fill(chs,'.');
            chs[queen[i]] = 'Q';
            board.add(new String(chs));
        }
        return board;
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0,r = nums.length - 1;
        while(l <= r){
            int mid = (l + r) >>> 1;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int t = Arrays.binarySearch(matrix[i], target);
            if(t >= 0 ){
                return true;
            }
        }
        return false;
    }
}

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int t = -1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] == target) {
                t = mid;
                break;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (t == -1) {
            return new int[] { -1, -1 };
        }
        l = t;
        r = t;
        while (r < nums.length - 1 && nums[r + 1] == nums[t])
        r++;
        while (l > 0 && nums[l - 1] == nums[t])
        l--;
        return new int[] { l, r };
    }
}

class Solution {
    public int search(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] t = Arrays.copyOfRange(nums,0,nums.length);
        Arrays.sort(t);
        for(int i = 0; i < nums.length;i++){
            map.put(nums[i],i);
        }
        int k = map.get(t[0]);
        int l = 0, r = t.length - 1,m = -1;
        while(l <= r){
            int mid = (l + r) >>> 1;
            if(t[mid] == target){
                m = mid;
                break;
            }else if(t[mid] > target){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        if(m == -1){
            return - 1;
        }
        return (m + k) % nums.length;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = (l + r) >>> 1;
            if(nums[mid] == target){
                return mid;
            }
            //右边有序
            if(nums[mid] < nums[r]){
                //target在有序侧
                if(target > nums[mid] && target <= nums[r]){
                    //向有序侧靠近
                    l = mid + 1;
                }else{
                    //target在无序侧，
                    r = mid - 1;
                }
            }else{
                //左部分有序
                if(target < nums[mid] && target >= nums[l]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] > nums[right]){
                // 最小值在右半部分
                left = mid + 1;
            } else {
                // 最小值在左半部分，包括 mid
                right = mid;
            }
        }
        return nums[left];
    }
}

class Solution {
    public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;
        int left = 0,right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] < min){
                min = nums[mid];
            }else if(nums[mid] < nums[right]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return min;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        if(a.length > b.length){
            int[] temp = a;
            a = b;
            b = temp;
        }
        int m = a.length;
        int n = b.length;
        int left = -1;
        int right = m;
        while(left + 1 < right){
            int i = (left + right) >>> 1;
            int j = (m + n + 1) / 2 - i - 2;
            if(a[i] <= b[j + 1]){
                left = i;
            }else{
                right = i;
            }
        }
        int i = left;
        int j = (m + n + 1) /2 - i - 2;
        int ai = i >= 0 ? a[i] : Integer.MIN_VALUE;
        int bj = j >= 0 ? b[j] : Integer.MIN_VALUE;
        int ai1 = i + 1 < m ? a[i + 1] : Integer.MAX_VALUE;
        int bj1 = j + 1 < n ? b[j + 1] : Integer.MAX_VALUE;
        int max1 = Math.max(ai, bj);
        int min2 = Math.min(ai1, bj1);
        return (m + n) % 2 > 0 ? max1 : (max1 + min2) / 2.0;
    }
}

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

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                    stack.push(c);
                } else if (!stack.isEmpty() && c == get(stack.peek())) {
                    stack.pop();
                } else {
                    return false; // 遇到右括号不匹配
                }
            }
            return stack.isEmpty();
        }
        char get(char c) {
            if (c == '(') return ')';
            if (c == '{') return '}';
            if (c == '[') return ']';
            return '?'; // 永远不会用到
        }
    }

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

class MinStack {
    Stack<Integer> stack;
    List<Integer> list;
    public MinStack() {
        stack = new Stack<>();
        list = new ArrayList();
    }
    public void push(int val) {
        stack.push(val);
        list.add(val);
        Collections.sort(list);
    }
    public void pop() {
        int t = stack.pop();
        int idx = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == t) {
                idx = i;
                break;
            }
        }
        list.remove(idx);
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return list.get(0);
    }
}

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;
    public MinStack() {
        stack = new ArrayDeque();
        minStack = new ArrayDeque();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

class Solution {
    public String decodeString(String s) {
        return decode(s.toCharArray());
    }
    int i = 0;
    String decode(char[] s){
        StringBuilder res = new StringBuilder();
        int k = 0;
        while(i < s.length){
            char c = s[i];
            i++;
            if(Character.isLetter(c)){
                res.append(c);
            }else if(Character.isDigit(c)){
                k = k * 10 + (c - '0');
            }else if(c == '['){
                String t = decode(s);
                res.repeat(t,k);
                k = 0;
            }else{
                break;
            }
        }
        return res.toString();
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0, n = heights.length;
        for (int i = 0; i <= n; i++) {
            int h = (i == n ? 0 : heights[i]); // 在末尾加一个0，保证栈清空
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;
    }
}

class Solution {
    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[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            pq.offer(new int[]{entry.getKey(),entry.getValue()});
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll()[0];
        }
        return res;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < nums.length;i++){
            pq.offer(nums[i]);
            if(pq.size() > k){
                pq.poll();
            }
        }
        return pq.peek();
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);
        for(int i = 0; i < nums.length;i++){
            pq.offer(nums[i]);
        }
        for(int i = 0; i < k-1;i++){
            pq.poll();
        }
        return pq.peek();
    }
}

class MedianFinder {
    List<Integer> list;
    public MedianFinder() {
        list = new ArrayList<>();
    }
    public void addNum(int num) {
        int index = Collections.binarySearch(list, num);
        if (index < 0) index = -index - 1; // 二分插入点
        list.add(index, num); // 保持升序
    }
    public double findMedian() {
        int n = list.size();
        if ((n & 1) != 0) {
            return list.get(n / 2);
        } else {
            return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
        }
    }
}

class MedianFinder {
    PriorityQueue<Integer> small; // 大顶堆，存较小的一半
    PriorityQueue<Integer> large; // 小顶堆，存较大的一半
    public MedianFinder() {
        small = new PriorityQueue<>((a, b) -> b - a);
        large = new PriorityQueue<>();
    }
    public void addNum(int num) {
        if(small.size() >= large.size()){
            small.offer(num);
            large.offer(small.poll());
        }else{
            large.offer(num);
            small.offer(large.poll());
        }
    }
    public double findMedian() {
        if(small.size() > large.size()){
            return small.peek();
        }else if(small.size() < large.size()){
            return large.peek();
        }
        return (small.peek() + large.peek()) / 2.0;
    }
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/

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

class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0;
        for(int i = 0; i < nums.length - 1;i++){
            farthest = Math.max(farthest,i + nums[i]);
            //nums[i]是0，被卡住脚
            if(farthest <= i){
                return false;
            }
        }
        return true;
    }
}

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

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for(int i = 0; i < s.length();i++){
            char c = s.charAt(i);
            last[c - 'a'] = i;
        }
        int start = 0, end = 0;
        for(int i = 0; i < s.length();i++){
            end = Math.max(end,last[s.charAt(i) - 'a']);
            if(end == i){
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}

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

class Solution {
    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];
    }
}

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(row);
        }
        return res;
    }
}

class Solution {
    int[] memo;
    public int numSquares(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo,-666);
        return dp(n);
    }
    int dp(int n) {
        if (n == 0) {
            return 0;
        }
        if( n < 0){
            return -1;
        }
        if(memo[n] != -666){
            return memo[n];
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i * i<= n; i++) {
            int t = dp(n - i * i);
            if(t == -1){
                continue;
            }
            res = Math.min(res,t + 1);
            if(res == 1) break;
        }
        memo[n] = (res == Integer.MAX_VALUE) ? 0 : res;
        return memo[n];
    }
}

输入：coins = [1, 2, 5], amount = 11输出：3
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3输出：-1

class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo,-666);
        return dp(coins,amount);
    }
    int dp(int[] coins,int amount){
        if(amount == 0){
            return 0;
        }
        if(amount < 0){
            return - 1;
        }
        if(memo[amount] != -666){
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for(int coin : coins){
            int t = dp(coins,amount - coin);
            if(t == -1){
                continue;
            }
            res = Math.min(res,t + 1);
        }
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}

class Solution {
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        Arrays.fill(memo, -666);
        return dfs(s, wordDict, 0);
    }
    boolean dfs(String s, List<String> wordDict, int idx) {
        if (idx == s.length()) {
            return true;
        }
        if (idx > s.length()) {
            return false;
        }
        if (memo[idx] != -666) {
            return memo[idx] == 1;
        }
        for (String word : wordDict) {
            int size = word.length();
            if (idx + size > s.length()) {
                continue;
            }
            String str = s.substring(idx, idx + size);
            if (word.equals(str)) {
                boolean flag = dfs(s, wordDict, idx + size);
                if (flag) {
                    memo[idx] = 1;
                    return true;
                }
            }
        }
        memo[idx] = 0;
        return false;
    }
}

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

for (物品 i)
for (容量 j 从最大到 w[i] 递减)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if((sum & 1) == 1){
            return false;
        }
        sum >>= 1;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for(int i = 0; i < nums.length;i++){
            for(int j = sum; j >= nums[i];j--){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
}

for (String word : wordDict) {
    for (int j = len; j <= n; j++) {
        if (dp[j - len] && s.substring(j - len, j).equals(word)) dp[j] = true;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && dp[i - len] && s.substring(i - len, i).equals(word)) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
}

输入：n = 12输出：3
解释：12 = 4 + 4 + 4

输入：n = 13输出：2
解释：13 = 4 + 9

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

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if((sum & 1) == 1){
            return false;
        }
        sum >>= 1;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for(int i = 0; i < nums.length;i++){
            for(int j = sum; j >= nums[i];j--){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
}

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

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

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxStart = 0;
        int maxEnd = 0;
        int maxLen = 1;
        boolean[][] dp = new boolean[len][len];
        for(int r = 1;r < len;r++){
            for(int l = 0; l < r;l++){
                if(s.charAt(l) == s.charAt(r) && (r - l <=2 || dp[l + 1][r - 1])){
                    dp[l][r] = true;
                    if(r - l + 1 > maxLen){
                        maxEnd = r;
                        maxStart = l;
                        maxLen = r - l + 1;
                    }
                }
            }
        }
        return s.substring(maxStart,maxEnd + 1);
    }
}

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0; i < s.length();i++){
            String s1 = f(s,i,i);
            String s2 = f(s,i,i+1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }
    String f(String s, int l, int r){
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1,r);
    }
}

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

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        cache = new LinkedHashMap<>();
        this.cap = capacity;
    }
    public int get(int key) {
        if(cache.get(key) == null){
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.put(key, value);
            makeRecently(key);
            return;
        }
        if (cache.size() >= cap) {
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        cache.put(key, value);
    }
    private void makeRecently(int key) {
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key, val);
    }
}

class Trie {
    class Node{
        boolean end = false;
        Node[] son = new Node[26];
    }
    Node root;
    public Trie() {
        root = new Node();
    }
    public void insert(String word) {
        Node cur = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(cur.son[index] == null){
                cur.son[index] = new Node();
            }
            cur = cur.son[index];
        }
        cur.end = true;
    }
    public boolean search(String word) {
        return find(word) == 2;
    }
    public boolean startsWith(String prefix) {
        return find(prefix) != 0;
    }
    int find(String word){
        Node cur = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(cur.son[index] == null){
                return 0;
            }
            cur = cur.son[index];
        }
        return cur.end ? 2 : 1;
    }
}

long pow(long a, long b) {
    long res = 1; // 使用long而不是int
    while (b > 0) {
        if ((b & 1) == 1) { // 判断最低位是否为1
            res = res * a; // 正确的乘法方式
        }
        a = a * a; // 平方底数
        b >>= 1; // 右移一位
    }
    return res; // 添加返回语句
}

int a(num){
    num %= 10;
    num/=10;
}

public int reverse(int num){
    int res = 0;
    while(num > 0){
        res = res * 10 + num % 10;
        num /= 10;
    }
    return res;
}

//给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
//子数组 是数组中 连续 的部分。
public static int subarraysDivByK(int[] nums, int k) {
    int ans = 0;
    Map<Integer,Integer> cnt = new HashMap<>();
    int[] s = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        s[i+1] = s[i] + nums[i];
    }
    for(int i = 0; i < s.length;i++){
        ans += cnt.getOrDefault((s[i] % k + k) % k,0);
        cnt.merge((s[i] % k + k) % k,1,Integer::sum);
    }
    return ans;
}
/*
s[i] % k：计算当前前缀和对 k 的模。
如果 s[i] 是正数，结果可能是 [0, k-1]。
如果 s[i] 是负数，结果可能是 [-(k-1), -1]
*/

boolean prime(int num){
    if(num < 2){
        return false;
    }
    for(int i =2; i * i<= num;i++){
        if(num % i == 0){
            return false;
        }
    }
    return true;
}

int gcd(int a,int b){
    return b== 0 ? a : gcd(b,a % b);
}

int lcm(int a, int b){
    return a / gcd(a, b) * b; // 先除后乘，避免溢出
}

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        // 将数组都初始化为 true
        Arrays.fill(isPrime, true);
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                // i 的倍数不可能是素数了
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
}

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i < n; i++)
        if (isPrime[i])
        for (int j = i * i; j < n; j += i)
        isPrime[j] = false;
        int count = 0;
        for (int i = 2; i < n; i++)
        if (isPrime[i]) count++;
        return count;
    }
}

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
}