class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res=new int[2];
        for(int i=0,j=numbers.length-1;i<j;)
        {
            int temp=numbers[i]+numbers[j];
            if(temp==target)
            {
                res[0]=i+1;
                res[1]=j+1;
                break;
            }
            else
                if(temp<target)
                    i++;
            else
                j--;
        }
        return res;
    }
}

class Solution {
    public boolean judgeSquareSum(int c) {
        int left=0;
        int right=(int)Math.sqrt(c);
        for(;left<=right;)
        {
            int temp=left*left+right*right;
            if(temp==c)
                return true;
            else
                if(temp>c)
                    right--;
             
            else
                left++;
        }
        return false;
    }
}

class Solution {
    public String reverseVowels(String s) {
        if (s!=null && s.length()!=0)
        {
            char[] ch=new char[s.length()];
            String letter="aieouAIEOU";
            for(int i=0,j=s.length()-1;i<=j;)
            {
                char left=s.charAt(i);
                char right=s.charAt(j);
                int flagleft=0;
                int flagright=0;
                if(i==j)
                {
                    ch[i]=left;
                    i++;
                    j--;
                    continue;
                }
                if(letter.indexOf(left)==-1)
                {
                    ch[i]=left;
                    i++;
                }
                else
                    flagleft=1;
                if((letter.indexOf(right)==-1)&&(i<j))
                {
                    ch[j]=right;
                    j--;
                }
                else
                    flagright=1;
                if(flagleft==1&&flagright==1)
                {
                    ch[i]=right;
                    ch[j]=left;
                    i++;
                    j--;
                }
            }
            s=String.valueOf(ch);
        }
        return s;
    }
}

class Solution {
    public boolean validPalindrome(String s) {
        char[] chars = s.toCharArray();
        int i = 0, j = chars.length - 1;
        while (i < j) {
            if (chars[i] != chars[j]) {
                return validPalindrome(chars, i, j - 1) || validPalindrome(chars, i + 1, j);
            }
            i++;
            j--;
        }
        return true;
    }

    private boolean validPalindrome(char[] chars, int l, int r) {
        while (l < r) {
            if (chars[l] != chars[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
    }
}

//快慢指针版
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)
                return true;
        }
        return false;
    }
}
//别人写的骚套路，复制过来记一下
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode>node = new HashSet<>();
        while(head!=null)
        {
            if(node.contains(head))
                return true;
            else
                node.add(head);
            head = head.next;
        }
        return false;
    }
}

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String res="";
        for(int i=0;i<d.size();i++)
        {
            String temp=d.get(i);
            if(issubstring(s,temp))
            {
                if(res.length()<temp.length())
                    res=temp;
                else
                    if((temp.length()==res.length())&&(temp.compareTo(res)<0))
                        res=temp;
            }
        }
        return res;
    }
    public boolean issubstring(String s,String target)
    {
        int i=0,j=0;
        for(;i<s.length()&&j<target.length();)
        {
            if(s.charAt(i)==target.charAt(j))
            {
                i++;
                j++;
            }
            else
            {
                i++;
            }
        }
        if(j==target.length())
            return true;
        return false;
    }
}

//时间复杂度 O(NlogK)，空间复杂度 O(K)。
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<nums.length;i++)
        {
            pq.add(nums[i]);
            if (pq.size() > k)
                pq.poll();
        }
        return pq.peek();
    }
}

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        
        Map<Integer, Integer> m = new HashMap<>();
        for (int num : nums) {
            m.put(num, m.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b)
            {
                return m.get(a)-m.get(b);
            }
        });
        for (int key : m.keySet()) {
            pq.add(key);
            if(pq.size()>k)
                pq.poll();
        }
        List<Integer> res=new ArrayList<Integer>();
        while(!pq.isEmpty())
        {
            res.add(pq.remove());
        }
        Collections.reverse(res);
        return res;
    }
}

class Solution {
    public String frequencySort(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            map.put(c,map.getOrDefault(c,0)+1);
        }
        PriorityQueue<Character> pq=new PriorityQueue<Character>(new Comparator<Character>(){
            public int compare(Character a,Character b)
            {
                return map.get(b)-map.get(a);
            }
        });
        for(Character key : map.keySet())
        {
            pq.add(key);
        }
        char[] res=new char[s.length()];
        int j=0;
        while(!pq.isEmpty())
        {
            char ch=pq.remove();
            int times=map.get(ch);
            for(int i=0;i<times;i++)
            {
                res[j++]=ch;
            }
        }
        return String.valueOf(res);
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int left=-1,mid=0,right=nums.length;
        while(mid<right)
        {
            if(nums[mid]==0)
            {
                swap(nums,++left,mid++);
            }
            else
                if(nums[mid]==2)
                {
                    swap(nums,mid,--right);
                }
            else
                mid++;
        }
    }
    public void swap(int[] nums,int i,int j)
    {
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count=0;
        for(int gi=0,si=0;gi<g.length&&si<s.length;)
        {
            if(s[si]>=g[gi])
            {
                count++;
                si++;
                gi++;
            }
            else
            {
                si++;
            }
            
        }
        return count;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0)
            return 0;
        Arrays.sort(intervals,Comparator.comparingInt(o->o[1]));
        int total=1;
        int right=intervals[0][1];
        for(int i=1;i<intervals.length;i++)
        {
            if(intervals[i][0]<right)
                continue;
            right=intervals[i][1];
            total++;
        }
        return intervals.length-total;
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
         if(points.length==0)
            return 0;
        Arrays.sort(points,Comparator.comparingInt(o->o[1]));
        int total=1;
        int right=points[0][1];
        for(int i=1;i<points.length;i++)
        {
            if(points[i][0]<=right)
                continue;
            right=points[i][1];
            total++;
        }
        return total;
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if(people==null||people.length==0||people[0].length==0)
            return new int[0][0];
        Arrays.sort(people,(a,b)->(a[0]==b[0]?a[1]-b[1]:b[0]-a[0]));
        List<int[]> res=new ArrayList<int[]>();
        for(int i=0;i<people.length;i++)
        {
            res.add(people[i][1],people[i]);
        }
        return res.toArray(new int[people.length][1]);
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0)
            return 0;
        int max=0;
        int curmin=prices[0];
        for(int i=1;i<prices.length;i++)
        {
            if(curmin>prices[i])
                curmin=prices[i];
            if(prices[i]-curmin>max)
                max=prices[i]-curmin;
        }
        return max;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0)
            return 0;
        int res=0;
        for(int i=1;i<prices.length;i++)
        {
            if(prices[i]-prices[i-1]>0)
                res+=prices[i]-prices[i-1];
        }
        return res;
    }
}

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count=0;
        if(flowerbed==null||flowerbed.length==0)
            return n==0?true:false;
        for(int i=0;i<flowerbed.length;i++)
        {
            if(flowerbed[i]==1)
                continue;
            int pre=i==0?0:flowerbed[i-1];
            int next=i==flowerbed.length-1?0:flowerbed[i+1];
            if(pre==0&&next==0)
            {
                count++;
                i++;
                //flowerbed[i] = 1;往后移一位或者改为1
            }
        }
        if(count>=n)
            return true;
        return false;
    }
}

//手动实现的慢版本
class Solution {
    public boolean isSubsequence(String s, String t) {
        int si=0,ti=0;
        for(;si<s.length()&&ti<t.length();)
        {
            if(s.charAt(si)==t.charAt(ti))
            {
                si++;
                ti++;
            }
            else
            {
                ti++;
            }
        }
        if(si!=s.length())
            return false;
        return true;
    }
}
//借助indexOf实现的快版本
class Solution {
    public boolean isSubsequence(String s, String t) {
        int index=-1;
        for(int i=0;i<s.length();i++)
        {
            char ch=s.charAt(i);
            index=t.indexOf(ch,index+1);
            if(index==-1)
                return false;
        }
        return true;
    }
}

class Solution {
    public boolean checkPossibility(int[] nums) {
        int flag=0;
        if(nums.length<3)
            return true;
        if(nums[0]>nums[1])
        {
            nums[0]=nums[1];
            flag=1;
        }
        for(int i=1;i<nums.length-1;i++)
        {
            if(nums[i]>nums[i+1])
            {
                if(flag==1)
                {
                    return false;
                }
                if(nums[i-1]<nums[i+1])
                {
                    nums[i]=nums[i+1];
                    flag=1;
                }
                else
                {
                    nums[i+1]=nums[i];
                    flag=1;
                }
            }
        }
        return true;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        int cursum=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            if(cursum<=0)
                cursum=nums[i];
            else
                cursum+=nums[i];
            if(cursum>max)
                max=cursum;
        }
        return max;
    }
}

class Solution {
    public List<Integer> partitionLabels(String S) {
                if (S == null || S.length() == 0) {
            return null;
        }
        int start=0;
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<S.length();)
        {
            char ch=S.charAt(i);
            int lastindex=S.lastIndexOf(ch);
            if(lastindex!=-1)
            {
                for(i++;i<=lastindex;i++)
                {
                    char ch2=S.charAt(i);
                    int lastindex2=S.lastIndexOf(ch2);
                    if(lastindex2>lastindex)
                        lastindex=lastindex2;
                }
                res.add(i-start);
                start=i;
            }
            else
                i++;
        }
        return res;
    }
}

class Solution {
    public int mySqrt(int x) {
        if(x<=1)
            return x;
        int left=1,right=x;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(x/mid==mid)
                return mid;
            else
                if(x/mid>mid)
                    left=mid+1;
            else
                right=mid-1;
        }
        if(x/left<left)
            return left-1;
        else
            return left;
    }
}

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
         int n = letters.length;
        int l = 0, h = n - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                h = m - 1;
            }
        }
        return l < n ? letters[l] : letters[0];
    }
}

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left=0,right=nums.length-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]==nums[mid-1])
            {
                if((mid-left)%2==0)
                    right=mid-2;
                else
                    left=mid+1;
            }
            else
                if(nums[mid]==nums[mid+1])
                {
                    if((right-mid)%2==0)
                        left=mid+2;
                    else
                        right=mid-1;
                }
            else
                return nums[mid];
        }
        return nums[right];
    }
}

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=0,right=n;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(isBadVersion(mid))
            {
                right=mid;
            }
            else
                left=mid+1;
        }
        return right;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] <= nums[h]) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = binarySearch(nums, target);
        int last = binarySearch(nums, target + 1) - 1;
        if (first == nums.length || nums[first] != target) {
            return new int[]{-1, -1};
        } else {
            return new int[]{first, Math.max(first, last)};
        }
    }
    public int binarySearch(int[] nums, int target) {
        int l = 0, h = nums.length;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] >= target) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<input.length();i++)
        {
            char ch=input.charAt(i);
            if(ch=='+'||ch=='-'||ch=='*')
            {
                List<Integer> left=diffWaysToCompute(input.substring(0,i));
                List<Integer> right=diffWaysToCompute(input.substring(i+1));
                for(int li=0;li<left.size();li++)
                    for(int ri=0;ri<right.size();ri++)
                    {
                        if(ch=='+')
                            res.add(left.get(li)+right.get(ri));
                        if(ch=='-')
                            res.add(left.get(li)-right.get(ri));
                        if(ch=='*')
                            res.add(left.get(li)*right.get(ri));
                    }
            }
        }
        if(res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res=new LinkedList<TreeNode>();
        if(n<1)
            return res;
        return generateSubtrees(1,n);
    }
    public List<TreeNode> generateSubtrees(int s, int e) {
        List<TreeNode> res = new LinkedList<TreeNode>();
        if (s > e) {
            res.add(null);
            return res;
        }
        for (int i = s; i <= e; i++) {
            List<TreeNode> left = generateSubtrees(s, i - 1);
            List<TreeNode> right = generateSubtrees(i + 1, e);
            for(int li=0;li<left.size();li++)
                for(int ri=0;ri<right.size();ri++)
                {
                    TreeNode root=new TreeNode(i);
                    root.left=left.get(li);
                    root.right=right.get(ri);
                    res.add(root);
                }
        }
        return res;
    }
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    // Since all words are of same length.
    int L = beginWord.length();
    // Dictionary to hold combination of words that can be formed,
    // from any given word. By changing one letter at a time.
    HashMap<String, ArrayList<String>> allComboDict = new HashMap<String, ArrayList<String>>();

    wordList.forEach(
        word -> {
          for (int i = 0; i < L; i++) {
            // Key is the generic word
            // Value is a list of words which have the same intermediate generic word.
            String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
            ArrayList<String> transformations =
                allComboDict.getOrDefault(newWord, new ArrayList<String>());
            transformations.add(word);
            allComboDict.put(newWord, transformations);
          }
        });

    // Queue for BFS
    Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();
    Q.add(new Pair(beginWord, 1));

    // Visited to make sure we don't repeat processing same word.
    HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
    visited.put(beginWord, true);

    while (!Q.isEmpty()) {
      Pair<String, Integer> node = Q.remove();
      String word = node.getKey();
      int level = node.getValue();
      for (int i = 0; i < L; i++) {

        // Intermediate words for current word
        String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

        // Next states are all the words which share the same intermediate state.
        for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<String>())) {
          // If at any point if we find what we are looking for
          // i.e. the end word - we can return with the answer.
          if (adjacentWord.equals(endWord)) {
            return level + 1;
          }
          // Otherwise, add it to the BFS Queue. Also mark it visited
          if (!visited.containsKey(adjacentWord)) {
            visited.put(adjacentWord, true);
            Q.add(new Pair(adjacentWord, level + 1));
          }
        }
      }
    }

    return 0;
  }
}

class Solution {
    private int m, n;
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0;
        int area = 1;
        for (int[] d : direction) {
            area += dfs(grid, r + d[0], c + d[1]);
        }
        return area;
    }
}

class Solution {
    private int m, n;
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int islandsNum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') {
                    dfs(grid, i, j);
                    islandsNum++;
                }
            }
        }
        return islandsNum;
    }
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        for (int[] d : direction) {
            dfs(grid, i + d[0], j + d[1]);
        }
    }
}

class Solution {
    public int findCircleNum(int[][] M) {
        boolean[] visited = new boolean[M.length];
        int ret = 0;
        for(int i = 0; i < M.length; ++i) {
            if(!visited[i]) {
                dfs(M, visited, i);
                ret++;
            }
        }
        return ret;
    }
    private void dfs(int[][] m, boolean[] visited, int i) {
        for(int j = 0; j < m.length; ++j) {
            if(m[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(m, visited, j);
            }
        }
    }
}

class Solution {
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int m, n;
    public void solve(char[][] board) {
         if (board == null || board.length == 0) {
            return ;
        }
        m = board.length;
        n = board[0].length;
        for(int i=0;i<m;i++)
        {
            dfs(board,i,0);
            dfs(board,i,n-1);
        }
        for(int i=0;i<n;i++)
        {
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        for (int i = 0; i < m; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                if (board[i][j] == 'N') 
                {
                    board[i][j] = 'O';
                }
                else
                {
                    if (board[i][j] == 'O') 
                    {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'N';
        for (int[] d : direction) {
            dfs(board, i + d[0], j + d[1]);
        }
    }
}

class Solution {
    private int m, n;
    private int[][] matrix;
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res=new ArrayList<>();
        List<int[]> ret = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return res;
        }
        m = matrix.length;
        n = matrix[0].length;
        this.matrix = matrix;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(i, 0, canReachP);
            dfs(i, n - 1, canReachA);
        }
        for (int i = 0; i < n; i++) {
            dfs(0, i, canReachP);
            dfs(m - 1, i, canReachA);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachP[i][j] && canReachA[i][j]) {
                    List<Integer> temp=new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }

        return res;
    }
    private void dfs(int r, int c, boolean[][] canReach) {
        if (canReach[r][c]) {
            return;
        }
        canReach[r][c] = true;
        for (int[] d : direction) {
            int nextR = d[0] + r;
            int nextC = d[1] + c;
            if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                    || matrix[r][c] > matrix[nextR][nextC]) {

                continue;
            }
            dfs(nextR, nextC, canReach);
        }
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int pre2 = 1, pre1 = 2;
        for (int i = 2; i < n; i++) {
            int cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

class Solution {
    public int rob(int[] nums) {
        int pre2 = 0, pre1 = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

class Solution {
    public int rob(int[] nums) {
         if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(rob(nums,0,nums.length-1),rob(nums,1,nums.length));
    }
    public int rob(int[] nums,int start,int end) {
        int pre2 = 0, pre1 = 0;
        for (int i = start; i < end; i++) {
            int cur = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

//普通版本
class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(i==0&&j==0)
                    continue;
                if(j==0)
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                else
                    if(i==0)
                        dp[i][j]=dp[i][j-1]+grid[i][j];
                    else
                        dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}
//空间优化版本，一维dp数组
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[j] = dp[j];        // 只能从上侧走到该位置
                } else if (i == 0) {
                    dp[j] = dp[j - 1];    // 只能从左侧走到该位置
                } else {
                    dp[j] = Math.min(dp[j - 1], dp[j]);
                }
                dp[j] += grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

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];
    }
}

class NumArray {

    private int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        int[] dp = new int[n];
        for (int i = 2; i < n; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int total = 0;
        for (int cnt : dp) {
            total += cnt;
        }
        return total;
    }
}

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i - 1; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }
}

//DP版本
class Solution {
     public int numSquares(int n) {
        int [] res = new int[n+1];
        for (int i = 1; i <= n; i++){
            int min = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++){
                min = Math.min(min, res[i-j*j]);
            }
            res[i] = min + 1;
        }
        return res[n];
    }
}
//数学定理版
// 由定理可知，结果只有 “1、2、3、4” 四种可能。依次判断下列情况：
// （1）ans = 4 ，判断是否满足推论；（在此过程中，以 4 的倍数缩小 n ，并不影响最后结果）
// （2）ans = 1 ，判断缩小后的 n 是否为平方数；
// （3）ans = 2 ，判断缩小后的 n 是否可以由两个平方数构成；
// （4）ans = 3， 以上都不满足，则结果为 3。
class Solution {
     public int numSquares(int n) {
        while(n%4==0)
            n/=4;
         if(n%8==7)
             return 4;
         for(int i=0;i*i<n;i++)
         {
             int j=(int)Math.sqrt(n-i*i);
             if(j*j+i*i==n)
                 if(i!=0&&j!=0)
                     return 2;
                else
                    return 1;
         }
         return 3;
    }
}

class Solution {
    public int numDecodings(String s) {
        if(s.length()==0||(s.length()==1&&s.charAt(0)=='0'))
            return 0;
        if(s.length()==1)
            return 1;
        int[] dp=new int[s.length()+1];
        dp[0]=1;
        dp[1]=s.charAt(0) == '0' ? 0 : 1;
        for(int i=2;i<=s.length();i++)
        {
            int onestep=s.charAt(i-1)=='0'?0:dp[i-1];
            int twostep=Integer.valueOf(s.substring(i - 2, i));
            if(s.charAt(i-2)=='0')
                twostep=0;
            else
                twostep=twostep>26?0:dp[i-2];
            dp[i]=onestep+twostep;
        }
        return dp[s.length()];
    }
}

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

class Solution {
    public int findLongestChain(int[][] pairs) {
        if(pairs==null||pairs.length==0)
            return 0;
        Arrays.sort(pairs,(a,b)->(a[0]-b[0]));
        int[] dp=new int[pairs.length];
        dp[0]=1;
        int max=1;
        for(int i=1;i<pairs.length;i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(pairs[j][1]<pairs[i][0])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
            if(max<dp[i])
                max=dp[i];
        }
        return max;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++)
            sum+=nums[i];
        if(sum%2!=0)
            return false;
        sum/=2;
        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 findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int i=0;i<nums.length;i++)
            sum+=nums[i];
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        int W = (sum + S) / 2;
        int[] dp = new int[W + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = W; i >= num; i--) {
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[W];
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs.length == 0) {
return 0;
}
int[][] dp =new int[m+1][n+1];
for(String s :strs) {
int zeros  = 0,ones = 0;
for(char c:s.toCharArray()) {
if (c == '0') {
zeros++;
}else {
ones++;
}
}
for (int i = m; i >=zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeros][j-ones]);
}
}
}
return dp[m][n];
    }
}

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

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++)
        {
            int coin=coins[i];
            for(int j=coin;j<=amount;j++)
            {
                dp[j]+=dp[j-coin];
            }
        }
        return dp[amount];
    }
}

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 (len <= i && word.equals(s.substring(i - len, i))) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }
}

class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int n=nums.length;
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++)
        {
            for(int j=0;j<nums.length&&i>=nums[j];j++)
            {
                dp[i]+=dp[i-nums[j]];
            }
        }
        return dp[target];
    }
}

for(int i=0;i<nums.length;i++)
    for(int j=target;j>=V[i];j--)

for(int i=0;i<nums.length;i++)
    for(int j=V[i];j<=target;j++)

for(int i=1;i<=target;i++)
    for(int j=0;j<V.length&&j>=V[i];j++)

class Solution {
    public int maxProfit(int[] prices) {
        int[] sell=new int[prices.length];
        int[] buy=new int[prices.length];
        int[] cool=new int[prices.length];
        if(prices==null||prices.length<2)
            return 0;
        buy[0]=-prices[0];
        for(int i=1;i<prices.length;i++)
        {
            sell[i]=Math.max(buy[i-1]+prices[i],sell[i-1]);
            buy[i]=Math.max(cool[i-1]-prices[i],buy[i-1]);
            cool[i]=Math.max(sell[i-1], cool[i-1]);
        }
        return sell[prices.length-1];
    }
}

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[] sell=new int[prices.length];
        int[] buy=new int[prices.length];
        if(prices==null||prices.length<2)
            return 0;
        buy[0]=-prices[0];
        for(int i=1;i<prices.length;i++)
        {
            sell[i]=Math.max(buy[i-1]+prices[i]-fee,sell[i-1]);
            buy[i]=Math.max(sell[i-1]-prices[i],buy[i-1]);
        }
        return sell[prices.length-1];
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int i=0;i<prices.length;i++)
        {
            int p=prices[i];
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy + p); 
        }
        return secSell;
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k < 1) return 0;
        if(k >= prices.length/2) return greedy(prices);
        int[][] t = new int[k][2];
        for(int i = 0; i < k; i++)
            t[i][0] = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++)
        {
            int p=prices[i];
            t[0][0] = Math.max(t[0][0], -p);
            t[0][1] = Math.max(t[0][1], t[0][0] + p);
            for(int j=1;j<k;j++)
            {
                t[j][0]=Math.max(t[j][0],t[j-1][1]-p);
                t[j][1]=Math.max(t[j][1],t[j][0]+p);
            }
        }
        return t[k-1][1];
    }
    private int greedy(int[] prices) {
        int max = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i-1])
                max += prices[i] - prices[i-1];
        }
        return max;
    }
}

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

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

//DP版本
class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        int h = (int) Math.sqrt(n);
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j <= h; j++) {
                if (i % j == 0) {
                    dp[i] = dp[j] + dp[i / j];
                    break;
                }
            }
        }
        return dp[n];
    }
}
//递归版本
class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return i + minSteps(n / i);
        }
        return n;
    }
}

class Solution {
    public int countPrimes(int n) {
         boolean[] notPrimes = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrimes[i]) {
                continue;
            }
            count++;
            for (long j = (long) (i) * i; j < n; j += i) {
                notPrimes[(int) j] = true;
            }
        }
        return count;
    }
}

class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        boolean isNegative = num < 0;
        if (isNegative) {
            num = -num;
        }
        while (num > 0) {
            sb.append(num % 7);
            num /= 7;
        }
        String ret = sb.reverse().toString();
        return isNegative ? "-" + ret : ret;
    }
}
//Java 中 static String toString(int num, int radix) 可以将一个整数转换为 radix 进制表示的字符串。

public String convertToBase7(int num) {
    return Integer.toString(num, 7);
}

class Solution {
    public String toHex(int num) {
        char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(map[num & 0b1111]);
            num >>>= 4;
        }
        return sb.reverse().toString();
    }
}

class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;
            sb.append((char) (n % 26 + 'A'));
            n =n / 26;
        }
        return sb.reverse().toString();
    }
}

class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        StringBuilder str = new StringBuilder();
        while (carry == 1 || i >= 0 || j >= 0) {
            if (i >= 0 && a.charAt(i--) == '1') {
                carry++;
            }
            if (j >= 0 && b.charAt(j--) == '1') {
                carry++;
            }
            str.append(carry % 2);
            carry /= 2;
        }
        return str.reverse().toString();
    }
}

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder str = new StringBuilder();
        int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
        while (carry == 1 || i >= 0 || j >= 0) {
            int x = i < 0 ? 0 : num1.charAt(i--) - '0';
            int y = j < 0 ? 0 : num2.charAt(j--) - '0';
            str.append((x + y + carry) % 10);
            carry = (x + y + carry) / 10;
        }
        return str.reverse().toString();
    }
}

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int i=0,j=nums.length-1;
        int res=0;
        while(i<j)
        {
            res+=nums[j--]-nums[i++];
        } 
        return res;
    }
}

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

class Solution {
    public boolean isPerfectSquare(int num) {
        for(int i=1;num>=0;i+=2)
        {
            if(num==0)
                return true;
            num-=i;
        }
        return false;
    }
}

//通用方法
class Solution {
    public boolean isPowerOfThree(int n) {
        if(n<=0)
            return false;
        if(n==1)
            return true;
        while(n%3==0)
        {
            if(n/3==1)
                return true;
            n/=3;
        }
        return false;
    }
}
//数学思想
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && (1162261467 % n == 0);
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums==null||nums.length==0)
            return null;
        int[] output=new int[nums.length];
        int left=1,right=1;
        for(int i=0;i<nums.length;i++)
        {
            output[i]=1;
        }
        for(int i=0;i<nums.length;i++)
        {
            output[i]=left;
            left*=nums[i];
        }
        for(int i=nums.length-1;i>=0;i--)
        {
            output[i]*=right;
            right*=nums[i];
        }
        return output;
    }
}

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        return Math.max(nums[n-1]*nums[n-2]*nums[n-3],nums[0]*nums[1]*nums[n-1]);
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int Alength=0;
        int Blength=0;
        ListNode temp=null;
        temp=headA;
        while(temp!=null)
        {
            Alength++;
            temp=temp.next;
        }
        temp=headB;
        while(temp!=null)
        {
            Blength++;
            temp=temp.next;
        }
        int diff=Alength-Blength;
        while(diff>0)
        {
            headA=headA.next;
            diff--;
        }
        while(diff<0)
        {
            headB=headB.next;
            diff++;
        }
        while(headA!=headB)
        {
            headA=headA.next;
            headB=headB.next;
        }
        return headA;
    }
    
}
//CYC
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
        l1 = (l1 == null) ? headB : l1.next;
        l2 = (l2 == null) ? headA : l2.next;
    }
    return l1;
}

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

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(0);
        ListNode newlink=head;
        while(l1!=null||l2!=null)
        {
            if(l1==null)
            {
                newlink.next=l2;
                return head.next; 
            }
            else
                if(l2==null)
                {
                    newlink.next=l1;
                    return head.next;
                }
            else
            {
                if(l1.val>l2.val)
                {
                    newlink.next=l2;
                    newlink=newlink.next;
                    l2=l2.next;
                }
                else
                {
                    newlink.next=l1;
                    newlink=newlink.next;
                    l1=l1.next;
                }
            }
        }
        return head.next;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode res=head;
        while(res!=null&&res.next!=null)
        {
            if(res.val==res.next.val)
                res.next=res.next.next;
            else
                res=res.next;
        }
        return head;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null||head.next==null)
            return null;
        ListNode fast=head;
        for(int i=0;i<n;i++)
        {
            fast=fast.next;
        }
        ListNode slow=head;
        if(fast==null)
            return head.next;
        while(fast.next!=null)
        {
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return head;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode beforehead=new ListNode(0);
        beforehead.next=head;
        ListNode temp=null;
        int count=0;
        ListNode p=beforehead;
        while(p.next!=null&&p.next.next!=null)
        {
            if(count==1)
            {
                count=0;
                p=p.next.next;
            }
            else
            {
                count++;
                temp=p.next.next;
                p.next.next=p.next.next.next;
                temp.next=p.next;
                p.next=temp;
            }
        }
        return beforehead.next;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1Stack = buildStack(l1);
        Stack<Integer> l2Stack = buildStack(l2);
        ListNode head = new ListNode(-1);
        int carry = 0;
        while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
            int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
            int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
            int sum = x + y + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = head.next;
            head.next = node;
            carry = sum / 10;
        }
        return head.next;
    }

    private Stack<Integer> buildStack(ListNode l) {
        Stack<Integer> stack = new Stack<>();
        while (l != null) {
            stack.push(l.val);
            l = l.next;
        }
        return stack;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
         if (head == null || head.next == null) {
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
        }
        slow=reverse(slow.next);
        while(slow!=null)
        {
            if(head.val!=slow.val)
                return false;
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode nextNode = head.next;
            head.next = newHead;
            newHead = head;
            head = nextNode;
        }
        return newHead;
    }
}

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int N = 0;
        ListNode cur = root;
        while (cur != null) {
            N++;
            cur = cur.next;
        }
        int mod = N % k;
        int size = N / k;
        ListNode[] ret = new ListNode[k];
        cur = root;
        for (int i = 0; cur != null && i < k; i++) {
            ret[i] = cur;
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        }
        return ret;
    }
}

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null)
            return head;
        ListNode singlehead=head;
        ListNode midhead=head.next;
        ListNode doublehead=head.next;
        while (singlehead.next != null && doublehead.next != null) {
            singlehead.next = doublehead.next;
            singlehead =singlehead.next;
            doublehead.next = singlehead.next;
            doublehead = doublehead.next;
        }
        singlehead.next=midhead;
        return head;
    }
}

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

class Solution {
    public boolean balance=true;
    public boolean isBalanced(TreeNode root) {
        maxdepth(root);
        return balance;
    }
    int maxdepth(TreeNode root)
    {
        if(root==null)
            return 0;
        int left=maxdepth(root.left);
        int right=maxdepth(root.right);
        if((left-right)>1||(left-right)<-1)
            balance=false;
        return Math.max(left,right)+1;
    }
}

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

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) 
            return null;
        // 后面的操作会改变 left 指针，因此先保存下来
        TreeNode left = root.left;  
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null)
            return t2;
        if(t2==null)
            return t1;
        t1.val=t1.val+t2.val;
        t1.left=mergeTrees(t1.left,t2.left);
        t1.right=mergeTrees(t1.right,t2.right);
        return t1;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) 
           return false;
        if (root.left == null && root.right == null && root.val == sum) 
            return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root==null)
            return 0;
        return find(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
    }
    public int find(TreeNode root,int sum)
    {
        if(root==null)
            return 0;
        sum-=root.val;
        int count=0;
        if(sum==0)
            count++;
        count+=find(root.left,sum)+find(root.right,sum);
        return count;
    }
}

class Solution {
    public boolean issame=false;
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s==null&&t==null)
            return true;
        if(s==null&&t!=null)
            return false;
        if(s!=null&&t==null)
            return true;
        return compare(s,t)||isSubtree(s.left,t)||isSubtree(s.right,t);
    }
    public boolean compare(TreeNode s,TreeNode t)
    {
        if(s==null&&t==null)
            return true;
        if(s==null||t==null)
            return false;
        if(s.val!=t.val)
            return false;
        return compare(s.left,t.left)&&compare(s.right,t.right);
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        return issame(root.left,root.right);
    }
    public boolean issame(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;
        return issame(left.left,right.right)&&issame(left.right,right.left);
    }
}

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) 
            return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) 
            return left + right + 1;
        return Math.min(left, right) + 1;
    }
}

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) 
            return 0;
        if (isLeaf(root.left)) 
            return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    private boolean isLeaf(TreeNode node){
        if (node == null) 
            return false;
        return node.left == null && node.right == null;
    }
}

class Solution {
    public int res=0;
    public int longestUnivaluePath(TreeNode root) {
        findmax(root);
        return res;
    }
    public int findmax(TreeNode root)
    {
        if(root==null)
            return 0;
        int leftlength=findmax(root.left)+1;
        int rightlength=findmax(root.right)+1;
        if(root.left==null||root.left.val!=root.val)
            leftlength=0;
        if(root.right==null||root.right.val!=root.val)
            rightlength=0;
        res=Math.max(res,leftlength+rightlength);
        return Math.max(leftlength,rightlength);
    }
}

class Solution {
    public int rob(TreeNode root) {
        if(root==null)
            return 0;
        int option1=root.val;
        if(root.left!=null)
            option1+=rob(root.left.left)+rob(root.left.right);
        if(root.right!=null)
            option1+=rob(root.right.left)+rob(root.right.right);
        int option2=rob(root.left)+rob(root.right);
        return Math.max(option1,option2);
    }
}

class Solution {
    public int min=-1;
    public int findSecondMinimumValue(TreeNode root) {
        if(root==null)
            return min;
        if(root.left!=null)
        {
            if(root.left.val!=root.val)
            {
                if(min==-1)
                    min=root.left.val;
                else
                    min=Math.min(min,root.left.val);
            }
            else
                findSecondMinimumValue(root.left);
                
        }
        if(root.right!=null)
        {
            if(root.right.val!=root.val)
            {
                if(min==-1)
                    min=root.right.val;
                else
                    min=Math.min(min,root.right.val);
            }
            else
                findSecondMinimumValue(root.right);
        }
        return min;
    }
}

class Solution {
    List<Double> res=new ArrayList<Double>();
    List<Integer> count=new ArrayList<Integer>();
    public List<Double> averageOfLevels(TreeNode root) {
        cal(root,0);
        return res;
    }
    public void cal(TreeNode root,int depth)
    {
        if(root==null)
            return ;
        if(res.size()<=depth)
        {
            res.add((double)root.val);
            count.add(1);
        }
        else
        {
            int curcount=count.get(depth);
            double curvalue=res.get(depth);
            res.set(depth,(curvalue*curcount+root.val)/(curcount+1));
            count.set(depth,curcount+1); 
        }
        cal(root.left,depth+1);
        cal(root.right,depth+1);
    }
}

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

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) 
                continue;
            res.add(node.val);
            stack.push(node.right);
            stack.push(node.left);
        }
        return res;
    }
}
//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) 
                continue;
            res.addFirst(node.val);
            stack.push(node.left);
            stack.push(node.right);
        }
        return res;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root==null)
            return null;
        if(root.val>=L&&root.val<=R)
        {
            root.left=trimBST(root.left,L,R);
            root.right=trimBST(root.right,L,R);
        }
        else
        {
            if(root.val<L)
            {
                root=trimBST(root.right,L,R);
            }
            else
            {
                root=trimBST(root.left,L,R);
            }
        }
        return root;
    }
}

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

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null)
            return null;
        convertBST(root.right);
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);
        return root;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        if(p.val>q.val)
        {
            TreeNode temp=p;
            p=q;
            q=temp;
        }
        if(p.val<=root.val&&q.val>=root.val)
            return root;
        if(q.val<root.val)
            return lowestCommonAncestor(root.left,p,q);
        return lowestCommonAncestor(root.right,p,q);
    
    }
}

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

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null)
            return null;
        return build(nums,0,nums.length-1);
    }
    TreeNode build(int[] nums,int left,int right)
    {
        if(left>right)
            return null;
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=build(nums,left,mid-1);
        root.right=build(nums,mid+1,right);
        return root;
    }
}

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) 
            return null;
        if(head.next == null) 
            return new TreeNode(head.val);
        ListNode slow=head;
        ListNode fast=head;
        ListNode beforeslow=null;
        while(fast!=null&&fast.next!=null)
        {
            beforeslow=slow;
            slow=slow.next;
            fast=fast.next.next;
        }        
        TreeNode root=new TreeNode(slow.val);
        beforeslow.next=null;
        root.left=sortedListToBST(head);
        root.right=sortedListToBST(slow.next);
        return root;
    }
}

class Solution {
    List<Integer> nodes=new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
        Traversal(root);
        for(int i=0,j=nodes.size()-1;i<j;)
        {
            int sum=nodes.get(i)+nodes.get(j);
            if(sum==k)
                return true;
            if(sum<k)
                i++;
            else
                j--;
        }
        return false;
    }
    public void Traversal(TreeNode root)
    {
        if(root==null)
            return ;
        Traversal(root.left);
        nodes.add(root.val);
        Traversal(root.right);
    }
}

//辅助List
class Solution {
    List<Integer> nodes=new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        Traversal(root);
        if(nodes.size()<2)
            return 0;
        int min=Math.abs(nodes.get(0)-nodes.get(1));
        for(int i=1;i<nodes.size();i++)
        {
            min=Math.min(min,Math.abs(nodes.get(i)-nodes.get(i-1)));
        }
        return min;
    }
    public void Traversal(TreeNode root)
    {
        if(root==null)
            return ;
        Traversal(root.left);
        nodes.add(root.val);
        Traversal(root.right);
    }
}
//直接计算
class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private TreeNode preNode = null;
    public int getMinimumDifference(TreeNode root) {
        inOrder(root);
        return minDiff;
    }
    private void inOrder(TreeNode node) {
        if (node == null) 
            return;
        inOrder(node.left);
        if (preNode != null) 
            minDiff = Math.min(minDiff, node.val - preNode.val);
        preNode = node;
        inOrder(node.right);
    }
}