烧鸡100二刷

public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer>hash=new HashMap<Integer,Integer>();
    for(int i=0;i<nums.length;i++)
    {
        if(hash.containsKey(target-nums[i]))
        {
            return new int[]{hash.get(target-nums[i]),i};
        }
        hash.put(nums[i],i);//必须后put，不然会哦重复
    }
    return new int[0];
}

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String,List<String>>map=new HashMap<>();
    for(String str:strs)
    {
        char[]arr=str.toCharArray();//变成数组好排序
        Arrays.sort(arr);//排序
        String key=new String(arr);//排序后的作为key
        List<String>list=map.getOrDefault(key,new ArrayList<String>());//看有没有之前存过的
        list.add(str);
        map.put(key,list);//更新
    }
    return new ArrayList<List<String>>(map.values());
}

public void moveZeroes(int[] nums) {
    int i=0;
    int j=0;//这里j=1就会出错，令人不解
    while(j<nums.length)
    {
        if(nums[j]!=0)
        {
            nums[i]=nums[j];
            i++;
        }
        j++;
    }
    while(i<nums.length)
    {
        nums[i]=0;
        i++;
    }
}

public int maxArea(int[] height) {
    int left=0,right=height.length-1;
    int Maxsize=Integer.MIN_VALUE;
    while(left<right)
    {
        int size=(right-left)*Math.min(height[left],height[right]);
        Maxsize=Math.max(Maxsize,size);
        if(height[left]<height[right])
        {
            left++;
        }else
        {
            right--;
        }
    }
    return Maxsize;
}

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>>res=new ArrayList<>();
    Arrays.sort(nums);
    //如果要找二元组等于0，怎么找，先排序，然后双指针，如果大于0就右边--，小于0就左边++
    //那么现在相当于对每一个数都这么来一遍
    //对每个数，取他后面的第一个和最后一个，去重很简单
    int len=nums.length;
    if(nums.length<3||nums==null)return res;
    for(int i=0;i<len;i++)
    {
        if(nums[i]>0)break;//这里都大于0了和肯定大于0
        if(i>0&&nums[i]==nums[i-1])continue;//去重
        int l=i+1,r=len-1;//i后面的第一个和最后一个
        while(l<r)
        {
            int sum=nums[i]+nums[l]+nums[r];
            if(sum==0)
            {
                 res.add(Arrays.asList(nums[i],nums[l],nums[r]));//一行
                 while(l<r&&nums[l]==nums[l+1])l++;
                 while(l<r&&nums[r]==nums[r-1])r--;//去重
                 l++;
                 r--;
            }else if(sum>0)
            {
                r--;//大了，右边缩小
            }else
            {
                l++;//小了，左边大
            }
        }
    }
    return res;
}

public int trap(int[] height) {
    int n=height.length,l=0,r=n-1;
    int lmax=height[l],rmax=height[r];//左侧最大高度，右侧最大高度
    int ans=0;

    while(l<=r)
    {
        if(lmax<rmax)
        {
            ans+=lmax-height[l];//乘1省略
            if(++l<=r)lmax=Math.max(height[l],lmax);//更新lmax
        }else
        {
            ans+=rmax-height[r];
            if(l<=--r)rmax=Math.max(rmax,height[r]);
        }
    }
    return ans;
}

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

public List<Integer> findAnagrams(String s, String p) {
    int slen=s.length(),plen=p.length();

    if(slen<plen)return new ArrayList<Integer>();
    List<Integer>ans=new ArrayList<>();
    int []pcount=new int[26];//统计p中每个字母出线的个数
    int []scount=new int[26];//统计窗口里的
    for(int i=0;i<plen;i++)//刚开始
    {
        pcount[p.charAt(i)-'a']++;
        scount[s.charAt(i)-'a']++;
    }

    if(Arrays.equals(scount,pcount))
    {
        ans.add(0);
    }//比较初试状态

    for(int i=0;i<slen-plen;i++)//窗口滑动
    {
        --scount[s.charAt(i)-'a'];
        ++scount[s.charAt(i+plen)-'a'];

        if(Arrays.equals(scount,pcount))
        {
            ans.add(i+1);//i是从0开始，所以要加1
        }
    }
    return ans;
}

public int subarraySum(int[] nums, int k) {
    //这题吧，有点动态规划的味道
    //思路：前缀和方法，pre[i]是[0,i]里所有数的和
    //所以[j,i]的和就是pre[i]-pre[j-1]=k
    //所以我们只要对每一个i，找有没有值为pre[i]-k的pre[j]即可

    int count=0;//结果
    int pre=0;//前面数字相加的和
    HashMap<Integer,Integer>map=new HashMap<>();//记录每一个pre出现的次数
   map.put(0,1);//为什么要定义(0,1)，因为考虑[1,2]然后k=3,1+2=pre=3，需要能找到3-0=3的，你不初始化就没有这个了
    for(int i=0;i<nums.length;i++)
    {   
        pre+=nums[i];
        if(map.containsKey(pre-k))//如果有前缀和等于pre-k，那么正好pre-(pre-k)=k，这一段就是我们要的
        {
            count+=map.get(pre-k);//加上出现过pre-k的次数，可能出现过不止一次，
        }
        map.put(pre,map.getOrDefault(pre,0)+1);//不管找没找到，都得更新当前pre
    }
    return count;
}

public int[] maxSlidingWindow(int[] nums, int k) {
    //思路：直接用最大堆不就行了
    PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    ArrayList<Integer>list=new ArrayList<>();
    for(int num:nums)//先把前k个写进去
    {
        if(pq.size()<k)
        {
            pq.offer(num);
        }
    }
    for(int i=0;i<nums.length-k;i++)
    {
        list.add(pq.peek());
        pq.remove(nums[i]);
        pq.offer(nums[i+k]);
    }
    list.add(pq.peek());
    int len=list.size();
    int[]res=new int[len];
    for(int i=0;i<len;i++)
    {
        res[i]=list.get(i);
    }
    return res;
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //思路：维护存有下标的一个双向队列，如果队首的下标还在，那就说明最大值还是他
        if(nums==null||nums.length<2)return nums;
        LinkedList<Integer>queue=new LinkedList<>();//注意queue里存的是下标
        int[]res=new int[nums.length-k+1];

        for(int i=0;i<nums.length;i++)
        {
            while(!queue.isEmpty()&&nums[queue.peekLast()]<=nums[i])//比nums[i]的小的都出来
            {
                queue.pollLast();
                //因为存的是下标，所以不需要把弹出的再存回来，只需要判断这个下表是不是还在窗口内即可
            }
            queue.addLast(i);
            if(queue.peek()<=i-k)//下标在现在的窗口外面了
            {
                queue.poll();
            }
            if(i+1>=k)//已经有一个窗口的大小了
            {
                res[i+1-k]=nums[queue.peek()];
            }
        }
        return res;
    }

public String minWindow(String s, String t) {
    //思路：滑动窗口，维护start和end，然后找到一个包含所有字母的，那就记录len并且尝试更新
    //找字母的过程：start不懂，end一个一个和t[i]比较，一样了i++,否则end++
    //找打哦所以字母了，start=end+1
    int start=0,end=0;
    int i=0;
    int minlen=Integer.MAX_VALUE;
    int minstart=0;
    while(end<s.length())//还没到最末尾
    {
        if(s.charAt(end)==t.charAt(i))
        {
            if(i==t.length()-1)
            {                  
                if(end-start+1<minlen)//如果这是更小的长度
                {
                    minstart=start;
                    minlen=end-start+1;
                }
                i=0;//从头开始
                start=end+1;
                end=start;
            }else
            {
                end++;
                i++;
            }
        }else
        {
            end++;//否则找下一个
        }
    }
    return s.substring(minstart,minstart+minlen);
}

class Solution {
    public String minWindow(String s, String t) {
        int[] cnt = new int[128];
        for (int i = 0; i < t.length(); i++) cnt[t.charAt(i)]++;
        int l = 0, r = 0, ansL = 0, ansR = 0, ans = Integer.MAX_VALUE, cntT = t.length();
        while (r < s.length()) {
            if (cnt[s.charAt(r++)]-- > 0) cntT--;
            while (cntT == 0) {
                if (r - l < ans) {
                    ans = r - l;
                    ansL = l;
                    ansR = r;
                }
                if (cnt[s.charAt(l++)]++ == 0) cntT++;
            }
        }
        return ans == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR);
    }
}

public int maxSubArray(int[] nums) {
    int len=nums.length;
    int[]dp=new int[len];
    dp[0]=nums[0];

    for(int i=1;i<len;i++)
    {
        if(dp[i-1]>0)
        {
            dp[i]=dp[i-1]+nums[i];
        }else
        {
            dp[i]=nums[i];
        }
    }
    int res=dp[0];
    for(int i=1;i<len;i++)
    {
        res=Math.max(res,dp[i]);
    }
    return res;
}

public int[][] merge(int[][] intervals) {
    if(intervals.length==0)
    {
        return new int[0][2];
    }
    Arrays.sort(intervals,new Comparator<int[]>(){
        public int compare (int[]interval1,int[]interval2){
            return interval1[0]-interval2[0];
        }
    });//先把他排序了
    //两个区间可以合并的条件：a的右端点大于其左端点或者右端点
    //但是如果a的左端点大于其左端点也可以
    //所以剩下一种情况：a的左端点大于其右端点，那就不行
    //不能合并怎么办，直接添加，因为是有序的，所以不能合并的后面所有的，对于当前的都不能合并

    //如何合并？因为已经按照左端点排序了，那么只需要更新右端点即可，右端点取最大的
    //如何遍历?
    List<int[]>merged=new ArrayList<>();
    for(int i=0;i<intervals.length;i++)
    {
        int L=intervals[i][0],R=intervals[i][1];//L:当前的左，R：当前的右
        if(merged.size()==0||merged.get(merged.size()-1)[1]<L)//如果merged为空或者其右端点小于目前比较的左端点
        {
            merged.add(new int[]{L,R});//直接添加
        }else
        {
            merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1],R);
            //否则，可以更新
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

public void rotate(int[] nums, int k) {
    if(nums.length==0)return;
    if(nums.length==1)return;
    k%=nums.length;//这一步非常重要，不然后面数组越界了
   reverse(nums,0,nums.length-1);
   reverse(nums,0,k-1);
    reverse(nums,k,nums.length-1);

}
public void reverse(int[]a,int l ,int r)
{
    while(l<r){
        int t=a[l];
        a[l]=a[r];
        a[r]=t;
        l++;
        r--;
    }
}

public int[] productExceptSelf(int[] nums) {
    //思路，什么勾八对角矩阵方法反正爷没记住
    int []res=new int[nums.length];
    int []L=new int[nums.length];
    int []R=new int[nums.length];
    L[0]=1;//第一个数的左积视为1
    R[nums.length-1]=1;//最后一额数的右积视为1
    for(int i=1;i<nums.length;i++)//求左边积
    {
        L[i]=nums[i-1]*L[i-1];
    }
    for(int i=nums.length-2;i>=0;i-- )//求右边积，其实这里nums.length-2可能越界，但是幸运的是测试用例没有
    {
        R[i]=nums[i+1]*R[i+1];
    }
    for(int i=0;i<nums.length;i++)//左乘右
    {
        res[i]=L[i]*R[i];
    }
    return res;
}

public int firstMissingPositive(int[] nums) {
    //思路：原地哈希
    //对于长度为N的数组，最小未出现正整数，要么是N+1，要么在1-N中
    //如果是有序的，那么对于1-n的i数值,i就应该出现在nums[i-1]上，所以我们可以对nums[i-1]设置标记，表示对应的i出现过
    //但是如何处理数组中的0和负数呢，我们把他先修改为N+1为什么，修改为别的会影响原来的1-N的个数
    //如何设置对nums[i-1]的标记
    //改成N+1侯，数组里全是证书了，所以我们设置为负号
    //如何规避遍历到已经被打标记的数呢
    //他的原来的数就是绝对值       
    int n=nums.length;
    for(int i=0;i<n;i++)
    {
        if(nums[i]<=0)
        {
            nums[i]=n+1;//小于等于0的全 设为n+1
        }
    }
    for(int i=0;i<n;i++)
    {
        int num=Math.abs(nums[i]);//变成原来值
        if(num<=n)
        {
            nums[num-1]=-Math.abs(nums[num-1]);//设置标记
        }
    }
    for(int i=0;i<n;i++)
    {
        if(nums[i]>0)
        {
            return i+1;//没被标记到的，那他就是没出现的最小的
        }
    }
    return n+1;
}

public void setZeroes(int[][] matrix) {
    //思路：设置两个个标识数组，表示这一行这一列有无0出线
    int m=matrix.length;//几个行
    int n=matrix[0].length;//几个列
    boolean[]ismzero=new boolean[m];//这一行有没有0
    boolean[]isnzero=new boolean[n];//这一列有没有0
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(matrix[i][j]==0)
            {
                ismzero[i]=true;//这一行有0
                isnzero[j]=true;//这一列有0
            }
        }
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(ismzero[i]||isnzero[j])
            {
                matrix[i][j]=0;
            }
        }
    }
}

public List<Integer> spiralOrder(int[][] matrix) {
    //思路，直接改变边界即可
    //遍历顺序：右，下，左，上,如果超过任何一个边界了，则break
    int l=0;//左边
    int r=matrix[0].length-1;//右边界
    int t=0;//上
    int b=matrix.length-1;//下边界
    ArrayList<Integer>res=new ArrayList<>();
    //注意一定要是++t,--r，得先做加减再比较
    while(true)
    {
        for(int i=l;i<=r;i++) res.add(matrix[t][i]);//向右
        if(++t>b)break;
        for(int i=t;i<=b;i++)res.add(matrix[i][r]);//向下
        if(--r<l)break;
        for(int i=r;i>=l;i--)res.add(matrix[b][i]);//向左
        if(--b<t)break;
        for(int i=b;i>=t;i--)res.add(matrix[i][l]);
        if(++l>r)break;
    }
    return res;
}

public boolean searchMatrix(int[][] matrix, int target) {
    //从右上角开始
    //x比target小，那么x这一列向上的所有 都比他小，所以往下走一行
    //x比target大，那么x这一行右边都比target大，往左走
    int i=0,j=matrix[0].length-1;
    while(i<matrix.length&&j>=0)
    {
        if(matrix[i][j]<target)
        {
            i++;
        }else if(matrix[i][j]>target)
        {
            j--;
        }
        else{
            return true;
        }
    }
    return false;
}

public void rotate(int[][] matrix) {
    //思路：利用tmp暂存实现原地旋转
    //知识点：i行j列->倒数第i列的第j行，n-1-i,j
    //同理i行j列，被n-1-j行，i覆盖，以此类推，分别推出每一个是被谁覆盖了
    //倒数第i列：n-i-1,n=matrix.length

    //每次先暂存i,j，然后依次覆盖
    int n=matrix.length;
    for(int i=0;i<n/2;i++)//只需要旋转一半就行了
    {
        for(int j=0;j<(n+1)/2;j++)
        {
            int t =matrix[i][j];
            matrix[i][j]=matrix[n-1-j][i];
            matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
            matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
            matrix[j][n-1-i]=t;
        }
    }
}

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

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

public boolean isPalindrome(ListNode head) {
    //思路：翻转前半部分，然后顺序比较
    //这样可以将找到中间节点和翻转，一起进行

    if(head==null||head.next==null)
    {
        return true;
    }
    ListNode slow=head,fast=head;
    ListNode pre=head,prepre=null;
    //pre相当于cur，slow相当于afer，prepre相当于pre
    while(fast!=null&&fast.next!=null)
    {
        pre=slow;
        slow=slow.next;
        fast=fast.next.next;
        pre.next=prepre;
        prepre=pre;
    }
    //处理是奇数的情况，当链表长度为奇数，此时slow会走到最中间的，不用比较的节点,而fast会走到最后一个节点
    if(fast!=null)
    {
        slow=slow.next;
    }
    while(pre!=null&&slow!=null)//比较前后是否一样
    {
        if(pre.val!=slow.val)
        {
            return false;
        }
        pre=pre.next;
        slow=slow.next;
    }
    return true;
}

public boolean hasCycle(ListNode head) {
    ListNode slow=head,fast=head;
    while(fast!=null&&fast.next!=null)//在while里判断，而不是while（1）然后if
    {
        slow=slow.next;
        fast=fast.next.next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

public ListNode detectCycle(ListNode head) {
    if(head==null||head.next==null)return null;
    ListNode fast=head;
    ListNode slow=head;
    while(true)
    {   
        if(fast==null||fast.next==null)
        {
            return null;
        }
        fast=fast.next.next;
        slow=slow.next;
        if(fast==slow)
        {
            break;
        }
    }
    ListNode p=head;
    while(slow!=p)
    {
        slow=slow.next;
        p=p.next;
    }
    return p;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //思路，设置一个进位值，进位值等于l1.val+l2.val+上一个的进位)/10
    //保留下来的是%10
    //然后while循环不断遍历，如果最后还有进位值，那就newlistNode (1)
    ListNode pre=new ListNode(0);
    ListNode cur=pre;
    int carry=0;//进位
    while(l1!=null||l2!=null)//只需要一个不为null就可以
    {
        int x=l1==null?0:l1.val;
        int y=l2==null?0:l2.val;
        int sum=x+y+carry;
        carry=sum/10;
        sum=sum%10;
        cur.next=new ListNode(sum);
        cur=cur.next;
        if(l1!=null)
        {
            l1=l1.next;
        }
        if(l2!=null)
        {
            l2=l2.next;
        }
    }
    if(carry==1)
    {
        cur.next=new ListNode(1);
    }
    return pre.next;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy=new ListNode(0,head);
    ListNode fast=head;
    ListNode slow=dummy;//让slow先在fast后面一个，这样slow会走到要被删除节点的前一个节点
    while(n>0)
    {
        fast=fast.next;
        n--;
    }
    while(fast!=null)
    {
        fast=fast.next;
        slow=slow.next;
    }
    slow.next=slow.next.next;//这样就不用返回来再找倒数第n个节点的前一个节点了
    ListNode ans=dummy.next;
    return ans;
}

public ListNode swapPairs(ListNode head) {
    if(head==null||head.next==null)return  head;
    ListNode pre=new ListNode(0);
    pre.next=head;
    ListNode tmp=pre;
    while(tmp.next!=null&&tmp.next.next!=null)
    {
        ListNode l=tmp.next;
        ListNode r=tmp.next.next;
        tmp.next=r;
        l.next=r.next;
        r.next=l;
        tmp=l;
    }
    return pre.next;
}

public ListNode reverseKGroup(ListNode head, int k) {
    //思路，大小为k的栈即可，然后多出来的直接连就行了
    ListNode dummy=new ListNode(0);
    Deque<ListNode> stk=new ArrayDeque<>();
    ListNode p=dummy;
    while(true)
    {
        int count=0;
        ListNode tmp=head;
        while(tmp!=null&&count<k)//把k个push进去
        {
            count++;
            stk.add(tmp);
            tmp=tmp.next;
        }
        if(count!=k)//如果不足k个，那么直接连接，不需要弹出了，按本来的顺序就行了
        {
            p.next=head;
            break;
        }
        while(!stk.isEmpty())
        {
            p.next=stk.pollLast();//弹出，实现翻转
            p=p.next;
        }
        //最后要注意把head更新一下
        head=tmp;
    }
    return dummy.next;
}

public Node copyRandomList(Node head) {
    //思路：设置哈希表，key是元节点，value是对饮的复制过的节点
    //先遍历一遍，赋值一下
    //第二次遍历连起来
    if(head==null)
    {
        return null;
    }
    Map<Node,Node> map=new HashMap<Node,Node>();
    Node p=head;
    //先复制，不忙设置random和next
    while(p!=null)
    {
        Node newNode=new Node(p.val);
        map.put(p,newNode);
        p=p.next;
    }
    p=head;
    //第二次，设置next和random
    while(p!=null)
    {
        Node newNode=map.get(p);//或者原节点对应复制的节点
        if(p.next!=null)
        {
        newNode.next=map.get(p.next);//复制的节点的next的原来的next的复制的
        }
        
        if(p.random!=null)
        {
            newNode.random=map.get(p.random);//同理
        }
        p=p.next;
    }
    return map.get(head);
}

public ListNode sortList(ListNode head) {
    if(head==null||head.next==null)
        return head;
    ListNode fast=head.next,slow=head;//有时我们可能会让快指针从头节点的下一个节点开始，这主要是为了处理链表长度为偶数的情况。如果链表长度为偶数，那么中点有两个。如果快指针从头节点开始，慢指针会停在中间两个节点的第2个；如果快指针从头节点的下一个节点开始，慢指针会停在中间两个节点的第1个。所以，是否让快指针从头节点的下一个节点开始，主要取决于你在链表长度为偶数时，希望慢指针停在哪个中点上。
    while(fast!=null&&fast.next!=null)
    {
        fast=fast.next.next;
        slow=slow.next;
    }
    ListNode tmp=slow.next;//slow是中间节点的第一个，所以slow.next是第二半
    slow.next=null;//断掉
    ListNode left=sortList(head);//递归求left
    ListNode right=sortList(tmp);//递归求right
    ListNode h=new ListNode(0);
    ListNode res=h;
    while(left!=null&&right!=null)
    {
        if(left.val<right.val)
        {
            h.next=left;
            left=left.next;
        }else
        {
            h.next=right;
            right=right.next;
        }
        h=h.next;
    }
    h.next=left!=null?left:right;//剩下的
    return res.next;
}

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans=null;
    for(int i=0;i<lists.length;i++)
    {
        ans=mergeTwo(ans,lists[i]);
    }
    return ans;
}
//因为已经是有序的，所以直接归并就行了
public ListNode mergeTwo(ListNode a,ListNode b)
{
    if(a==null||b==null)
        return a!=null?a:b;
    ListNode head =new ListNode(0);
    ListNode tail=head,aptr=a,bptr=b;
    while(aptr!=null&&bptr!=null)
    {
        if(aptr.val<bptr.val)
        {
            tail.next=aptr;
            aptr=aptr.next;
        }else
        {
            tail.next=bptr;
            bptr=bptr.next;
        }
        tail=tail.next;
    }
    tail.next=(aptr!=null?aptr:bptr);//把多的连起来
    return head.next;
}

public ListNode mergeKLists(ListNode[] lists) {
    if(lists==null||lists.length==0)
        return null;
    PriorityQueue<ListNode> queue=new PriorityQueue<>(lists.length,new Comparator<ListNode>(){
        public int compare(ListNode o1,ListNode o2 )
        {
            if(o1.val<o2.val)return -1;//
            else if(o1.val==o2.val)return 0;//
            else return 1;//1就是你需要的顺序和原来的顺序相反
        }
    });
        ListNode dummy=new ListNode(0);
        ListNode p=dummy;
        for(ListNode node:lists)
        {
            if(node!=null)
            {
                queue.add(node);//先把每个链表的第一个插进来
            }
        }
        while(!queue.isEmpty())
        {
            p.next=queue.poll();//从队列中取出
            p=p.next;//这个时候p就是被取出的那个元素
            if(p.next!=null)
            {
                queue.add(p.next);//加入被取出p对应的的那个链表的后面一个
            }
        }
        return dummy.next;
}

class LRUCache {
    //这里我们把最进用的的放在队尾，这里put和get都算使用
    //然后借助LinkedHashHap这个强无敌的哈希链表
    LinkedHashMap<Integer,Integer>cache=new LinkedHashMap<>();
    int cap;
    public LRUCache(int capacity) {
        this.cap=capacity;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key))
            return -1;
        makeRecent(key);
        return cache.get(key);

    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key))//有则改变值
        {
            cache.put(key,value);
            makeRecent(key);
            return ;
        }

        if(cache.size()>=this.cap)//容量不足了，把头拿出去
        {
            int oldkey=cache.keySet().iterator().next();//迭代器一开始再头的前面一个，所以后一个就是第一个
            cache.remove(oldkey);
        }
        cache.put(key,value);
    }


    public void makeRecent(int key)//就是把他删了再放到后面
    {
        int val=cache.get(key);
        cache.remove(key);
        cache.put(key,val);
    }
}

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

public int maxDepth(TreeNode root) {
    if(root==null)return 0;//什么时候不满足，空点
    int left=maxDepth(root.left);
    int right=maxDepth(root.right);
    return Math.max(left,right)+1;
}

public TreeNode invertTree(TreeNode root) {
    //有一说一这题取巧了，他其实进行的是值的交换
    //什么时候不满足
    if(root==null)
        return null;
    //你可能会想，如果没有左右孩子呢？那就是null和null交换呗，一样的
    TreeNode t=root.left;
    root.left=root.right;
    root.right=t;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

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

class Solution {
    //因为直径是用边数表示，所以等于左深度+右深度+自己-1，正好就是左深度加右深度
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans=0;
        maxDepth(root);
        return ans;
    }
     public int maxDepth(TreeNode root) {
        if(root==null)return 0;//什么时候不满足，空点
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        ans=Math.max(ans,left+right);//还得加上自己
        return Math.max(left,right)+1;
    }
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
    Queue<TreeNode> queue=new LinkedList<TreeNode>();
    if(root==null)
        return res;
    queue.offer(root);
    while(!queue.isEmpty())
    {
        List<Integer>level=new ArrayList<>();
        int size=queue.size();
        for(int i=0;i<size;i++)//因为要分层存入，所以记录size
        {
            TreeNode node=queue.poll();
            level.add(node.val);
            if(node.left!=null)
            {
                queue.offer(node.left);
            }
            if(node.right!=null)
            {
                queue.offer(node.right);
            }
        }
        res.add(level);
    }
    return res;
}

class Solution {
    //知识点:二叉搜索树的中序遍历就是一个升序序列
    //所以该问题就是，根据中序遍历建立二叉搜索树
    //思路:中间节点就是root，然后递归建立左右子树
    
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int []nums,int l,int r)
    {
        if(l>r)return null;
        int mid=(l+r)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=helper(nums,l,mid-1);
        root.right=helper(nums,mid+1,r);
        return root;
    }
}

//方法一：中序遍历放入数组里
class Solution {
    ArrayList<Integer>list=new ArrayList<Integer>();
    public int kthSmallest(TreeNode root, int k) {
        zxbl(root);
        return list.get(k-1);
    }
    public void  zxbl(TreeNode root)
    {     
        if(root==null)return;
        zxbl(root.left);
        list.add(root.val);
        zxbl(root.right);
    }
}

public List<Integer> rightSideView(TreeNode root) {
    Queue<TreeNode>q=new LinkedList<TreeNode>();
    List<Integer>res=new ArrayList<>();
    if(root==null)
        return res;
    q.offer(root);
    while(!q.isEmpty())
    {
        int size=q.size();//先记录这一层有多少个
        while(size-->0)//size次之后，也就遍历完这一层的了
        {
            TreeNode node=q.poll();
            if(node.left!=null)q.offer(node.left);
            if(node.right!=null)q.offer(node.right);
            if(size==0)res.add(node.val);
        }
    }
    return res;
}

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

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return Helper(preorder,0,preorder.length,inorder,0,inorder.length);//不能减1，因为是右开
    }
    public TreeNode Helper(int[]preorder,int pstart,int pend,int []inorder,int istart,int iend)//左闭右开
    {
        if(pstart==pend)
            return null;
        int root_val=preorder[pstart];//根节点就是前序遍历的第一个节点
        int iroot_index=0;//这个根节点在中序遍历里的位置
        for(int i=istart;i<iend;i++)//左闭右开，找到这个根在中序遍历里的位置，拆分左子树和右子树
        {
            if(root_val==inorder[i])
            {
                iroot_index=i;
                break;
            }
        }
        TreeNode root=new TreeNode(root_val);//新建根节点
        int leftlength=iroot_index-istart;//左子树的长度，用于在前序遍历中也找到左子树的部分
        root.left=Helper(preorder,pstart+1,pstart+leftlength+1,inorder,istart,iroot_index);//左比有开
        root.right=Helper(preorder,pstart+leftlength+1,pend,inorder,iroot_index+1,iend);//跳过iroot_index，因为他就是更节点
        return root;
    }
}

class Solution {
    //思路：前缀和思想，将前缀和放到map里，然后去找map里有没有curr-targetsum的
    //前缀和方法的核心：就是那个map
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> prefix=new HashMap<Long,Integer>();
        prefix.put(0L,1);//和其他前缀和方法一样，你要保证能当比如：1,2 然后你要的和就是3，那你是不是得找前缀和为0的，所以你得先放进去
        return dfs(root,prefix,0,targetSum);
    }

    public int dfs(TreeNode root,Map<Long,Integer> prefix,long curr,int targetSum)
    {
        if(root==null)
        {
            return 0;
        }
        int ret=0;
        curr+=root.val;//当前和
        ret=prefix.getOrDefault(curr-targetSum,0);//前缀和等于curr-targetsum的个数
        prefix.put(curr,prefix.getOrDefault(curr,0)+1);//把当前前缀和放进去，之前没有过就变成1，否则在基础上+1
        ret+=dfs(root.left,prefix,curr,targetSum);
        ret+=dfs(root.right,prefix,curr,targetSum);
        prefix.put(curr,prefix.getOrDefault(curr,0)-1);//回溯
        return ret;
    }
}

class Solution {
    //本题说是找pq的公共祖先，其实是找pq的位置
    //要么p是q祖先，要么q是p祖先，要么分散在一个root的左右子树里
    //如果先找到p,那么p是祖先， 如果先找到q，那么q是祖先
    //如果这次都没找到，那就递归左右字数
    //如果左或者右为空，说明不在这个里面，只返回不空的那一个的结果就行
    //如果两个结果都不为空，那么说明分散在左右子树，root就是结果
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p||root==q)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 {
    //思路，得到根节点到这两个节点的路径，然后找出路径中最后一个相同的元素即可
    //怎么找路径？dfs啊
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> a=new ArrayList<>(),b=new ArrayList<>();
        dfs(root,p,a);
        dfs(root,q,b);
        TreeNode ans=null;
        for(int i=0;i<Math.min(a.size(),b.size())&&a.get(i)==b.get(i);i++)
        {
            ans=a.get(i);
        }
        return ans;
    }

    boolean dfs(TreeNode cur,TreeNode t,List<TreeNode>path){
        if(cur==null)
            return false;
        path.add(cur);
        if(cur==t||dfs(cur.left,t,path)||dfs(cur.right,t,path))
        {   
            return true;
        }else
        {
            path.remove(path.size()-1);
            return false;
        }
    }
}

class Solution {
    int max=Integer.MIN_VALUE;
    //思路：其实也就是求每个节点的左右子树的最大 顺下去的和然后相加
    public int maxPathSum(TreeNode root) {
        getmaxdeepsum(root);
        return max;
    }
    public int getmaxdeepsum(TreeNode root)
    {
        if(root==null)
            return 0;
        int leftsum=Math.max(getmaxdeepsum(root.left),0);//大于0才选取这一段
        int rightsum=Math.max(getmaxdeepsum(root.right),0);

        int price=root.val+leftsum+rightsum;//进过这一点的最大路径和
        max=Math.max(max,price);
        return root.val+Math.max(leftsum,rightsum);//返回这个结点的最大一条路径，因为如果这一个节点不是最后的中间那个节点，那么他被选取的时候只能作为左或者右路径的一部分
    }
}

class Solution {
    //思路：dfs，碰到一个岛屿，就把这个岛屿所有的陆地全变成'0'，
    public int numIslands(char[][] grid) {
            int res=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]=='1')
                {
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

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

class Solution {
    boolean[][]visited;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//为了遍历的时候上下左右移动
    public int numIslands(char[][] grid) {
        int res=0;
        visited = new boolean[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(!visited[i][j]&&grid[i][j]=='1')
                {
                    bfs(grid,i ,j);
                    res++;
                }
            }
        }
        return res;
    }

    public void bfs(char[][]grid,int y,int x)
    {
        //dfs因为是递归，所以需要把判断条件先写，但是bfs不是，所以不需要
        Deque<int[]>queue=new ArrayDeque<>();
        queue.offer(new int[]{y,x});//存储下标
        visited[y][x]=true;
        while(!queue.isEmpty())
        {
            int[]cur=queue.poll();
            int m=cur[0];
            int n=cur[1];
            //遍历他的上下左右
            for(int i=0;i<4;i++)
            {
                int nexty=m+move[i][0];
                int nextx=n+move[i][1];
                if(nextx < 0 || nexty == grid.length || nexty < 0 || nextx == grid[0].length) continue;
                if(!visited[nexty][nextx] && grid[nexty][nextx] == '1') {
                    queue.offer(new int[]{nexty, nextx}); 
                    visited[nexty][nextx] = true; //只要加入队列就标记为访问
                }
            }
        }
    }
}

class Solution {
    int cnt;//新鲜橘子的数量，用来最后判断能不能全部腐烂
    public int orangesRotting(int[][] grid) {
        Queue<int[]>queue=new LinkedList<>();
        //先找到所有腐烂的橘子，全部加入
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]==2)
                {
                    queue.add(new int[]{i,j});
                }else if(grid[i][j]==1)
                {
                    cnt++;
                }
            }
        }
        int round=0;//表示分钟数
        while(cnt>0&&!queue.isEmpty())
        {
            round++;
            int n=queue.size();//相当于层序遍历这一层的节点
            for(int i=0;i<n;i++)
            {
                int[]orange=queue.poll();
                int r=orange[0];//行
                int c=orange[1];//列
                //腐烂他的上下左右
                if(r-1>=0&&grid[r-1][c]==1)
                {
                    grid[r-1][c]=2;
                    cnt--;
                    queue.add(new int[]{r-1,c});
                }
                if(r+1<grid.length&&grid[r+1][c]==1)
                {
                    grid[r+1][c]=2;
                    cnt--;
                    queue.add(new int[]{r+1,c});
                }
                if(c-1>=0&&grid[r][c-1]==1)
                {
                    grid[r][c-1]=2;
                    cnt--;
                    queue.add(new int[]{r,c-1});
                }
                if(c+1<grid[0].length&&grid[r][c+1]==1)
                {
                    grid[r][c+1]=2;
                    cnt--;
                    queue.add(new int[]{r,c+1});
                }
            }
        }
        if(cnt>0)
        {
            return -1;//还有没腐烂的，说明不能全烂掉
        }else
        {
            return round;//返回轮数
        }
    }
}

class Solution {
    //思路：这是进店拓扑排序问题，我们只需要判断有没有环即可
    //如何判断有没有环？dfs，然后看有没有遍历到之前遍历过的节点
    //如何dfs呢，也就是说如何从给的prerequisites，得到一个图，这是难点
    //所以我们考虑bfs的思想，每次只能选入度为0的课，然后让相关课的入度-1，以此类推
    //如果最后还有入度不为0的，那么说明失败
    //所以我们需要两个数据结构：入度值和玲姐表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer,Integer>inDegree=new HashMap<>();
        for(int i=0;i<num;i++)
        {
            inDegree.put(i,0);//先吧所有的课程加入
        }

        Map<Integer,List<Integer>> adj=new HashMap<>();//玲姐表，表示x指向哪几个元素

        //初始化入度
        for(int[]relate:prerequisites)
        {
            int cur=relate[1];//当前节点
            int next=relate[0];//指向的节点

            //更新入度
            inDegree.put(next,inDegree.get(next)+1);

            //更新玲姐表
            if(!adj.containsKey(cur))
            {
                adj.put(cur,new ArrayList<>());
            }
            adj.get(cur).add(next);
        }
        //队列，用于bfs
        Queue<Integer>q=new LinkedList<>();
        //先把为0的加入
        for(int key:inDegree.keySet())
        {
            if(inDegree.get(key)==0)
            {
                q.offer(key);
            }
        }

        while(!q.isEmpty())
        {
            int cur=q.poll();//取出
            if(!adj.containsKey(cur))
            {
                continue;
            }
            List<Integer> list=adj.get(cur);//获取玲姐表
            for(int k:list)//把入度-1
            {
                inDegree.put(k,inDegree.get(k)-1);
                if(inDegree.get(k)==0)//别忘了在这里把为0的放进去
                {
                    q.offer(k);
                }
            }
        }
        //检查是否还有入度不为0的
        for(int key:inDegree.keySet())
        {
            if(inDegree.get(key)!=0)
            {
                return false;
            }
        }
        return true;
    }
}

class Trie {
    private Trie[] children;//孩子节点，我们用26个位置对应26个字母
    private boolean isEnd;//是否结束了

    public Trie() {
        children=new Trie[26];//26个字母
        isEnd=false;
    }
    
    public void insert(String word) {
        Trie node=this;//标记走到的节点
        for(int i=0;i<word.length();i++)
        {
            char s=word.charAt(i);
            if(node.children[s-'a']==null)
            {
                node.children[s-'a']=new Trie();
            }
            node=node.children[s-'a'];
        }
        node.isEnd=true;
    }
    
    public boolean search(String word) {
        Trie node=searchprefix(word);//找到对应的节点
        return node!=null&&node.isEnd;//判断是不是end，才能知道只是前缀相同，还是是同一个单词
    }
    
    public boolean startsWith(String prefix) {
        return searchprefix(prefix)!=null;
    }

    public Trie searchprefix(String prefix)//寻找作为前缀的最后一个节点
    {
                //和insert一样啊，就是找到为Null为止
        Trie node=this;
        for(int i=0;i<prefix.length();i++)
        {
            char ch=prefix.charAt(i);
            int idx=ch-'a';
            if(node.children[idx]==null)
            {
                return null;//没找到
            }
            node=node.children[idx];
        }
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

class Solution {
    //排列问题，也就是都可以从头开始
     List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length==0)
        return result;
        bactracking(nums);
        return result;
    }
     void bactracking(int []nums)
     {
         if(path.size()==nums.length)
         {  
             result.add(path);
             return ;
         }
         for(int i=0;i<nums.length;i++)
         {
             if(path.contains(nums[i]))//判断是否加入过了
             {
                 continue;
             }
             path.add(nums[i]);
             bactracking(nums);
             path.removeLast();
         }
     }
}

result.add(new LinkedList<>(path));

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>(); // 用来存放符合条件结果

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0)
            return result;
        backtrack(nums);
        return result;
    }

    void backtrack(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            backtrack(nums);
            path.removeLast();
        }
    }
}

class Solution {
     List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets(int[] nums) {
        if(nums.length==0)
            return result;
        back(nums,0);
        return result;
    }
    void back(int[]nums,int staridx)
    {
        result.add(new ArrayList<>(path));
        if(staridx>=nums.length)
        {
            return;
        }
        for(int i=staridx;i<nums.length;i++)
        {
            path.add(nums[i]);
            back(nums,i+1);//这里不能再是staridx了，因为staridx就是本次遍历的
            path.removeLast();
        }
    }
}

class Solution {
     List<String> list = new ArrayList<>();
     StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
         String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
         back(digits,numString,0);
         return list;
    }
    void back(String digits,String[]numString,int num)
    {
        if(num==digits.length())
        {
            list.add(temp.toString());
            return;
        }
        String str=numString[digits.charAt(num)-'0'];//获取对应的字符串
        for(int i=0;i<str.length();i++)
        {
            temp.append(str.charAt(i));
            back(digits,numString,num+1);//取遍历下一个数字
            temp.deleteCharAt(temp.length()-1);//删除刚刚加进去的，然后加后面一个继续,比如刚刚加了b，现在加c
        }
    }
}

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

    void back(int[]candidates,int target,int starindex)
    {
        if(starindex>=candidates.length|| candidates[starindex]==target)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=starindex;i<candidates.length;i++)
        {
            if(candidates[i]>target)break;
            path.add(candidates[i]);
            back(candidates,target-candidates[i],i+1);
            path.remove(path.size()-1);
        }
    }
}

if(starindex>=candidates.length|| candidates[starindex]==target)

back(candidates,target-candidates[i],i+1);

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

    void back(int[]candidates,int target,int starindex)
    {
        if(starindex>=candidates.length||target==0)//你递归的时候减去candidates[i],判断条件应该是target==0
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=starindex;i<candidates.length;i++)
        {
            if(candidates[i]>target)break;
            path.add(candidates[i]);
            back(candidates,target-candidates[i],i);//可以使用相同元素，所以应该是i，而不是i+1
            path.remove(path.size()-1);
        }
    }
}

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

    void dfs(String cur,int left,int right,List<String>res)
    {
        if(left==0&&right==0)
        {
            res.add(cur);
            return;
        }
        if(left>right)
            return;
        
         if (left > 0) {
            dfs(cur + "(", left - 1, right, res);
        }
        if (right > 0) {
            dfs(cur + ")", left, right - 1, res);
        }
    }
}

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                boolean flag=check(board,visited,i,j,word,0);
                if(flag)
                {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean check(char[][]board,boolean[][]visited,int i ,int j,String s,int k)
    {
        if(board[i][j]!=s.charAt(k))
        {
            return false;
        }else if(k==s.length()-1)//长度一样了
        {
            return true;
        }
        visited[i][j]=true;
        boolean result=false;
        int[][]dirs={{0,1},{0,-1},{1,0},{-1,0}};
        for(int[]dir:dirs)
        {
            int newi=i+dir[0],newj=j+dir[1];
            if(newi>=0&&newi<board.length&&newj>=0&&newj<board[0].length)
            {   
                if(!visited[newi][newj])
                {
                boolean flag=check(board,visited,newi,newj,s,k+1);//递归查询他周边的
                if(flag)
                {
                    result=true;//说明这条路径可以找到
                    break;//不用再找了
                }
                }
            }
        }
        visited[i][j]=false;//回溯
        return result;
    }
    
}

class Solution {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();
    public List<List<String>> partition(String s) {
        back(s,0);
        return lists;
    }

    void back(String s,int startIndex)
    {
        if(startIndex>=s.length())
        {
            lists.add(new ArrayList<>(deque));
            return;
        }
        for(int i=startIndex;i<s.length();i++)
        {
            if(isPalindrome(s,startIndex,i))//如果是回文
            {
                deque.addLast(s.substring(startIndex,i+1));
            }else{
                continue;//不是就继续往后找
            }
            back(s,i+1);//不能重复，所以i+1
            deque.removeLast();
        }
    }



     private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    List<List<String>>res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][]chessboard=new char[n][n];
        for(char[]c :chessboard)
        {
            Arrays.fill(c,'.');//初始化，一个皇后都没有
        }
        back(n,0,chessboard);
        return res;
    }

   public void back(int n,int row,char[][]chessboard )
    {
        if(row==n)//已经遍历到第n行了
        {
            res.add(Array2List(chessboard));
            return ;
        }
        //行内遍历
        for(int i=0;i<n;i++)
        {
            if(isValid(row,i,n,chessboard))
            {
                chessboard[row][i]='Q';//放皇后
                back(n,row+1,chessboard);//选下一行的
                chessboard[row][i]='.';//回溯
            }
        }
    }

    //把二维数组chessboard转换为
   public List<String> Array2List(char[][]chessboard)
    {
        ArrayList<String> list=new ArrayList<>();
        for(char[] c:chessboard)
        {
            list.add(String.copyValueOf(c));
        }
        return list;
    }


    public boolean isValid(int row,int col,int n,char[][]chessboard)
    {
        //检查列
        for(int i=0;i<row;i++)
        {
            if(chessboard[i][col]=='Q')
            {
                return false;
            }
        }
        //检查左上角
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
        {
            if(chessboard[i][j]=='Q')
            {
                return false;
            }
        }
        //检查右上角
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)
        {
            if(chessboard[i][j]=='Q')
            {
                return false;
            }
        }
        return true;
    }
}

public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1;
        int ans=nums.length;//记录位置
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]>=target)
            {
                ans=mid;
                right=mid-1;//因为你是闭区间，所以要-1
            }else
            {
                left=mid+1;
            }
        }
        return ans;
}

class Solution {
    //直接从右上角开始
    //因为行递增，列递增
    //所以如果ij<target，那么ij,左边的全小于target,下面的全小于target
    public boolean searchMatrix(int[][] matrix, int target) {
        int i=0,j=matrix[0].length-1;
        while(i<matrix.length&&j>=0)
        {
            if(matrix[i][j]==target)
            {
                return true;
            }else if(matrix[i][j]>target)
            {
                j--;
            }else if(matrix[i][j]<target)
            {
                i++;
            }
        }
        return false;
    }
}

class Solution {
    //其实就是二分找左边界问题
    //那么我们这边都用闭区间看看
    public int[] searchRange(int[] nums, int target) {
        boolean has=false;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]==target)
            {
                has=true;
            }
        }
        if(has==false)
        {
            return new int[]{-1,-1};
        }
        int l=getLeft(nums,target);
        int r=getRight(nums,target);
        return new int[]{l,r};
    }

    public int getLeft(int []nums,int target)
    {
        int left=0;
        int right=nums.length-1;
        while(left<=right)//也是因为是闭区间，所以有=号
        {
            int mid=(left+right)/2;
            if(nums[mid]>=target)//因为要寻找边界，所以>=的时候要更新right
            {
                right=mid-1;//闭区间，-1
            }else
            {
                left=mid+1;
            }
        }
        return right+1;
    }
    public int getRight(int[]nums,int target)
    {
        int left=0,right=nums.length-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]<=target)
            {
                left=mid+1;
            }else
            {
                right=mid-1;
            }
        }
        return left-1;
    }
}

class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}

class Solution {
    public int search(int[] nums, int target) {
       int div= findMin(nums);//找到分割点
        int a=bs(nums,0,div,target);
        int b=bs(nums,div-1,nums.length-1,target);
        return Math.max(a,b);
    }
    public int findMin(int[] nums) {
        int left=0,right=nums.length-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]>=nums[0])
            {
                left=mid+1;
            }else
            {
                right=mid-1;
            }
        }
        return left<nums.length?left:0;
    }

    int bs(int[]nums,int left,int right,int target)
    {   
        int ans=-1;
        int mid=(left+right)/2;
        while(left<=right)
        {
            if(nums[mid]==target)
            {
                return mid;
            }else if(nums[mid]>target)
            {
                right=mid-1;
            }else
            {
                left=mid+1;
            }
        }
        return ans;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right)
        {   
            int mid=(left+right)/2;
            if(nums[mid]==target)
            {
                return mid;
            }
            if(nums[mid]>=nums[0])//说明在nums[mid]第一段升序里面
            {
                if(nums[0]<=target&&target<nums[mid])//target在0和mid之间，也就是说target也在这个升序里
                {
                    right=mid-1;//更新右边，因为你是在第一个升序里面
                }else
                {
                    left=mid+1;//target不在0和mid之间，但是有1.可能在第一个升序，但是在mid的右边 2.在第二个升序里，此时无论什么情况，都是更新left
                }
            }else//mid在第二段升序里面
            {
                if(nums[nums.length-1]>=target&&target>nums[mid])//target在mid和nums.length之间，也就是说target也在这个升序里
                {
                    left=mid+1;//更新左边界
                }else
                {
                    right=mid-1;//同理
                }
            }
        }
        return -1;
    }
}

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

return left<nums.length?nums[left]:nums[0];

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n=nums1.length;
        int m=nums2.length;
         //因为数组是从索引0开始的，因此我们在这里必须+1，即索引(k+1)的数，才是第k个数。
        int left=(n+m+1)/2;
        int right=(n+m+2)/2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
        return (getK(nums1, 0, n - 1, nums2, 0, m - 1, left) + getK(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private int getK(int []nums1,int start1,int end1,int []nums2,int start2,int end2,int k)//k代表个数
    {
        int len1=end1-start1+1;
        int len2=end2-start2+1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getK(nums2, start2, end2, nums1, start1, end1, k);
        if(len1==0)return nums2[start2+k-1];//返回第k小的
        
        if(k==1)return Math.min(nums1[start1],nums2[start2]);

        int i=start1+Math.min(len1,k/2)-1;//这一步是为了保证数组如果剩余长度小于k/2，那么就会移动到末尾,-1是因为k表示个数，所以作为索引计算，-1
        int j=start2+Math.min(len2,k/2)-1;

        if(nums1[i]>nums2[j])
        {
            //nums1大，那么就把nums2的前面舍去
            return getK(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else
        {
            return getK(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }


    }
}

public boolean isValid(String s) {
    int n=s.length();
    if(n%2==1)
        return false;
    Deque<Character>stk=new LinkedList<>();
    Map<Character,Character>mp=new HashMap<>();
    mp.put(')','(');
    mp.put(']','[');
    mp.put('}','{');
    for(int i=0;i<s.length();i++)
    {
        char ch=s.charAt(i);
        if(mp.containsKey(ch))
        {
            if(stk.isEmpty()||stk.peek()!=mp.get(ch))//遇到右括号判断对不对
            {
                return false;
            }
            stk.pop();
        }else
        {
            stk.push(ch);//只存放左括号
        }
    }
    return stk.isEmpty();//最后还有没有多余的
}

class MinStack {
    Deque<Integer>stk=new LinkedList<>();
    Deque<Integer>min=new LinkedList<>();

    public MinStack() {
        min=new LinkedList<>();
    }
    
    public void push(int val) {
        stk.push(val);
        if(min.isEmpty())
        {
            min.push(val);
        }else
        {
            if(val<min.peek())
            {
                min.push(val);
            }else
            {
                min.push(min.peek());
            }
        }
    }
    
    public void pop() {
        stk.pop();
        min.pop();
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

public String decodeString(String s) {
    s=s.trim();//去除前后的空格什么的

    StringBuilder res=new StringBuilder();//暂存字符串

    Stack<Integer>nums=new Stack<>();
    Stack<String>strs=new Stack<>();
    int num=0;//暂存数字，直到数字读取完整
    for(int i=0;i<s.length();i++)
    {
        if(s.charAt(i)>='0'&&s.charAt(i)<='9')
        {
            num=num*10+s.charAt(i)-'0';//更新数字
        }else if(s.charAt(i)>='a'&&s.charAt(i)<='z')
        {
            res.append(s.charAt(i));
        }else if(s.charAt(i)=='[')//遇到[入栈
        {   
            nums.push(num);
            strs.add(res.toString());
            res=new StringBuilder();//从新开始
            num=0;//num一样
        }else{//遇到]出栈
            int times=nums.pop();//出几次
            String tmp=strs.pop();
            for(int j=0;j<times;j++)
            {
                tmp+=res.toString();//把res加到tmp后面times次
            }
            res=new StringBuilder(tmp);//然后更新res
        }
    }
    return res.toString();
}

public int[] dailyTemperatures(int[] temperatures) {
    int len=temperatures.length;
    int []ans=new int[len];
    Deque<Integer>stk=new LinkedList<>();
    for(int i=0;i<len;i++)
    {
        int t=temperatures[i];
        while(!stk.isEmpty()&&t>temperatures[stk.peek()])//只要栈不为空，并且这个位置的温度比栈头表示的温度大，那么这个温度就是第一个比她大的温度
        {
            int index=stk.pop();//栈头温度的下标，并且把栈头温度pop
            ans[index]=i-index;//几天之后

        }
        stk.push(i);//比他小的全出去了，他又成当前最小的了
    }
    return ans;
}

public int largestRectangleArea(int[] heights) {
    int n=heights.length;
    int []l=new int[n];
    int []r=new int[n];
    Arrays.fill(l,-1);
    Arrays.fill(r,n);//因为下标有0，所以得先设置为-1
    Deque<Integer>stk=new ArrayDeque<>();

    for(int i=0;i<n;i++)//右边第一个比奇小的位置，所以从左边往右边遍历
    {
        while(!stk.isEmpty()&&heights[i]<heights[stk.peekLast()])//同样的这里记录下表
        {
            r[stk.pollLast()]=i;//把比他大的全pop出去，然后自己的位置，就是第一个比Last小的位置
        }
        stk.addLast(i);//找第一个比奇小，那么就是递增站
    }
    stk.clear();//清空
    for(int i=n-1;i>=0;i--)
    {
        while(!stk.isEmpty()&&heights[i]<heights[stk.peekLast()])
        {
            l[stk.pollLast()]=i;
        }
        stk.addLast(i);
    }
    //遍历，找最大的
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t=heights[i],a=l[i],b=r[i];
        ans=Math.max(ans,(b-a-1)*t);
    }
    return ans;
}

public int compare(Integer a, Integer b) {
	    //   以下是对比较器升序、降序的理解.
		//	 (1) 写成return a.compareTo(b) 或者 return a-b表示升序(最小堆)
		//	 (2) 写成return b.compareTo(a) 或者 return b-a表示降序(最大堆)				
			return b.compareTo(a);
		}

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a ,Integer b )
            {
                return b-a;
            }
        });
        for(int num:nums)
        {
            pq.add(num);
        }
        while(k>1)
        {
            pq.remove();
            k--;
        }

        return pq.peek();
}

class Solution {
    Random random=new Random(System.currentTimeMillis());
    //如果Pivotindex<N-K,那么到pivotindex+1~right里找
    public int findKthLargest(int[] nums, int k) {
        int len=nums.length;
        int target=len-k;
        int left=0,right=len-1;
        while(true)
        {
            int pivotIndex=partition(nums, left, right);
            if(pivotIndex<target)
            {
                left=pivotIndex+1;
            }else if(pivotIndex>target)
            {
                right=pivotIndex-1;
            }else
            {
                return nums[pivotIndex];
            }
        }
    }


    public int partition(int []nums,int left,int right)
    {
        int randomIndex=left+random.nextInt(right-left+1);//随机选一个档pivot
        //swappivot和left,把他弄到左边去
        swap(nums, randomIndex,left);
        int pivot=nums[left];
        int le=left+1;
        int ge=right;
        while(le<=ge)
        {
            while(le<=ge&&nums[le]<pivot)
            {
                le++;
            }
            while(le<=ge&&nums[ge]>pivot)
            {
                ge--;
            }
            if(le>ge)break;//这里要再判断一次，防止越界了
            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);//放回去，此时le=ge，也就是你要放的位置了
        return ge;
    }










    public void swap(int[]nums,int index1,int index2)
    {
        int t=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=t;
    }
}

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer,Integer>mp=new HashMap<>();
    for(int num:nums)
    {
        mp.put(num, mp.getOrDefault(num, 0)+1);
    }
    PriorityQueue<Integer>pq=new PriorityQueue<>(new Comparator<Integer>() {
        public int compare(Integer a,Integer b)
        {
            return mp.get(a)-mp.get(b);
        }
    });//小顶堆
    for(int key:mp.keySet())
    {
        if(pq.size()<k)
        {
            pq.add(key);
        }else if(mp.get(key)>mp.get(pq.peek()))//频率比堆顶大，才加入
        {
            pq.remove();
            pq.add(key);
        }
    }
    int []res=new int[k];
    for(int i=0;i<k;i++)
    {
        res[i]=pq.poll();
    }
    return res;
}

class MedianFinder {
    //较小的一半，大堆
    PriorityQueue<Integer> minhalf=new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer a,Integer b)
        {
            return b-a;
        }
    });
    //较大的一半，小堆
    PriorityQueue<Integer>maxhalf=new PriorityQueue<>();
    public MedianFinder() {

    }
    
    public void addNum(int num) {
        minhalf.add(num);
        maxhalf.add(minhalf.poll());
        if(minhalf.size()<maxhalf.size())
        {
            minhalf.add(maxhalf.poll());
        }
    }
    
    public double findMedian() {
        if(minhalf.size()==maxhalf.size())
        {
            return (double)(minhalf.peek()+maxhalf.peek())/2;
        }
        else
        {
            return (double)minhalf.peek();
        }
    }
}

public int maxProfit(int[] prices) {
    int []res=new int[prices.length];
    int min=Integer.MAX_VALUE;
    int max=Integer.MIN_VALUE;
    for(int i=0;i<prices.length;i++)
    {
        res[i]=prices[i]-min>0?prices[i]-min:0;//先更新res[i]，保证不包含当前的
        min=Math.min(min,prices[i]);
        max=Math.max(max,res[i]);
    }
    return max;
}

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

public int jump(int[] nums) {
    int end=0;//当前的maxlen
    int maxPos=0;//下一次的maxPos
    int steps=0;
    for(int i=0;i<nums.length-1;i++)
    {
        maxPos=Math.max(maxPos,nums[i]+i);
        if(i==end)
        {
            end=maxPos;//更新边界，也就相当于跳到了那个位置
            steps++;
        }
    }
    return steps;
}

public List<Integer> partitionLabels(String s) {
    int []last=new int[26];
    int len=s.length();
    for(int i=0;i<s.length();i++)//设置last数组，方便找
    {
        last[s.charAt(i)-'a']=i;
    }
    List<Integer>res=new ArrayList<>();
    int start=0,end=0;
    for(int i=0;i<s.length();i++)
    {
        end=Math.max(end,last[s.charAt(i)-'a']);//更新边界
        if(i==end)
        {
            res.add(end-start+1);
            start=end+1;
        }
    }
    return res;
}

public int climbStairs(int n) {
    int []dp=new int[n+1];//最后要n层，所以定义n+1
    dp[0]=1;
    dp[1]=1;//初始化两个
    for(int i=2;i<n+1;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

public int rob(int[] nums) {
    int n=nums.length;
    int []dp=new int[n];
    if(nums.length==1)return nums[0];
    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],dp[i-2]+nums[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=Math.max(res,dp[i]);
    }
    return res;
}

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

public int numSquares(int n) {
    int max=Integer.MAX_VALUE;
    int[]dp=new int[n+1];
    for(int j =0;j<n+1;j++)
    {
        dp[j]=max;//因为要求最少是几个完全平方的和，所以初始化为最大致
    }
    dp[0]=0;
    for(int i=1;i*i<n+1;i++)
    {
        for(int j=i*i;j<n+1;j++)
        {
            if(dp[j-i*i]!=max)
            {
                dp[j]=Math.min(dp[j],dp[j-i*i]+1);
            }
        }
    }
    return dp[n];
}

public int coinChange(int[] coins, int amount) {
    int []dp=new int[amount+1];
    int max=Integer.MAX_VALUE;
    for(int j=0;j<dp.length;j++)
    {
        dp[j]=max;//因为是要找最少的个数，所以初始化成最大值
    }
    dp[0]=0;
    for(int i=0;i<coins.length;i++)
    {
        for(int j=coins[i];j<amount+1;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];
}

public boolean wordBreak(String s, List<String> wordDict) {

    boolean []dp=new boolean[s.length()+1];
    dp[0]=true;
    for(int i=1;i<s.length()+1;i++)//便利背包
    {
        for(int j=0;j<i&&!dp[i];j++)//严格来说这里不能叫便利物品，不过也能叫，就是不停截取，然后判断是不是物品
        {
            if(wordDict.contains(s.substring(j,i))&&dp[j])
            {
                dp[i]=true;
            }
        }
    }
    return dp[s.length()];
}

public int lengthOfLIS(int[] nums) {
    int n=nums.length;
    int[]dp=new int[n];
    Arrays.fill(dp,1);//注意此处初始化，每一个初始值应该为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[i],dp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=Math.max(res,dp[i]);
    }
    return res;
}

//思录：按规律来,
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<numRows;i++)
    {
        List<Integer>ans=new ArrayList<>();
        for(int j=0;j<=i;j++)
        {
            if(j==0||j==i)
            {
                ans.add(1);
            }else
            {
                ans.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));//相加
            }
        }
        res.add(ans);
    }
    return res;
}

public int maxProduct(int[] nums) {
    int []maxdp=new int[nums.length];
    int[] mindp=new int[nums.length];

    int res=nums[0];
    maxdp[0]=mindp[0]=nums[0];
    for(int i=1;i<nums.length;i++)
    {
        maxdp[i]=Math.max(nums[i],Math.max(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]));
        mindp[i]=Math.min(nums[i],Math.min(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]));
        res=Math.max(res,maxdp[i]);
    }
    return res;
}

public boolean canPartition(int[] nums) {
    if(nums==null||nums.length==0)return false;
    int n=nums.length;
    int sum=0;
    for(int num:nums)
    {
        sum+=num;
    }
    if(sum%2!=0)return false;
    int target=sum/2;
    int[]dp=new int[target+1];//dp[i]为容量为i的背包最多能装多少容量
    for(int i=0;i<n;i++)
    {
        for(int j=target;j>=nums[i];j--)//因为是01背包，就是不能重复用数字，所以得倒序遍历
        {
            dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
        }
    }
    return dp[target]==target;
}

public int longestValidParentheses(String s) {
    if(s.length()==0)return 0;
    Deque<Integer>stk=new LinkedList<>();
    stk.push(-1);//防止一开始就是右括号，没东西可以弹出
    int max=0;
    for(int i=0;i<s.length();i++)
    {
        if(s.charAt(i)=='(')
        {
            stk.push(i);//是左括号，push进区域
        }else
        {
            stk.pop();//是右括号，弹出
            if(stk.isEmpty())
            {
                //如果是空说明没东西可以匹配，这次是不能匹配的
                stk.push(i);//把当前位置入栈，充当之前的-1
            }else
            {
                max=Math.max(max, i-stk.peek());
            }
        }
    }
    return max;
}

public int longestValidParentheses(String s) {
    int n=s.length();
    int []dp=new int[n];
    int max_len=0;
    for(int i=1;i<n;i++)
    {
        if(s.charAt(i)==')')
        {
            if(s.charAt(i-1)=='(')
            {
                if(i<2)
                    dp[i]=2;
                else
                    dp[i]=dp[i-2]+2;
            }
            else
            {
                if(dp[i-1]>0)
                {
                    int pre_left=i-dp[i-1]-1;//上一个括号对应的左括号下标
                    if(pre_left>=0&&s.charAt(pre_left)=='(') //(())这样的
                    {
                        dp[i]=dp[i-1]+2;
                        if(pre_left-1>0)
                        {
                            dp[i]=dp[i]+dp[pre_left-1];//() (())如果他前面还有这种
                        }
                    }
                }
            }
        }
        max_len=Math.max(max_len,dp[i]);
    }
    return max_len;
}

public int singleNumber(int[] nums) {
    int res=nums[0];
    for(int i=1;i<nums.length;i++)
    {
        res^=nums[i];
    }
    return res;
}

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

public void sortColors(int[] nums) {
    int n0=0,n1=0;
    for(int i=0;i<nums.length;i++)
    {
        int num=nums[i];
        nums[i]=2;//先全部设为2
        if(num<2)//有多少个小于2 的，那就在前面变成多少个1
        {
            nums[n1++]=1;
        }
        if(num<1)//有多少个小于1的，那就在把前面的多少个1变成0
        {
            nums[n0++]=0;
        }
    }
}

public void nextPermutation(int[] nums) {
    int i=nums.length-2,j=nums.length-1;//从后往前找到第一个领巾的升序对
    while(i>=0)
    {
        if(nums[i]<nums[j])
            break;
        i--;j--;
    }
    if(i<0){//一直都没找到升序对，说明已经是98764321这种了，按题目要求，返回最小的，也就是直接排序了
        Arrays.sort(nums);
        return;
    }
    //找到升序对了，i就是小数，要和后面的大数交换，那么大数就是后面从后向前找，第一个比i大的
    int k=nums.length-1;//表示大数
    for(k=nums.length-1;k>=j;k--)
    {
        if(nums[i]<nums[k])
            break;
    }

    swap(nums,i,k);//交换i，k
    //让后面变成升序，使得最小
    Arrays.sort(nums,j,nums.length);
}

public void swap(int[] nums, int i, int k){
    int tmp = nums[i];
    nums[i] = nums[k];
    nums[k] = tmp;
}

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

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

public int minPathSum(int[][] grid) {
    if(grid==null||grid.length==0||grid[0].length==0)
        return 0;
    int m=grid.length,n=grid[0].length;
    int[][]dp=new int[m][n];
    dp[0][0]=grid[0][0];
    for(int i=1;i<n;i++)
    {
        dp[0][i]=grid[0][i]+dp[0][i-1];
    }
    for(int j=1;j<m;j++)
    {
        dp[j][0]=grid[j][0]+dp[j-1][0];
    }
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    return dp[m-1][n-1];

}

public String longestPalindrome(String s) {
    //有一说一还是动态规划好理解
    //dp[i][j]:i-j是不是回味淄川
    //递推公式：if(s[i]==s[j],dp[i][j]=dp[i+1][j-1])
    //然后再过程中维护长度和七点
    boolean[][]dp=new boolean[s.length()][s.length()];
    int begin=0;
    int maxlen=1;//至少为1
    for(int i=0;i<dp.length;i++)
    {
        dp[i][i]=true;//单个字符是回文
    }
    for(int j=1;j<s.length();j++)
    {
        for(int i=0;i<j;i++)
        {
            if(s.charAt(i)!=s.charAt(j))
            {
                dp[i][j]=false;
            }else
            {
                if(j-i<3)
                {
                    dp[i][j]=true;//只有两个字母就不能i+1,j-1了
                }
                else
                {
                    dp[i][j]=dp[i+1][j-1];
                }
            }
            if(dp[i][j]&&j-i+1>maxlen)
            {
                maxlen=j-i+1;
                begin=i;
            }
        }
    }
    return s.substring(begin,begin+maxlen);
}

 if(text1.charAt(i-1)==text2.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]);//这个呢
     
                }
比如 abcde ace 
    ab ab 这个时候是1
    那么abc ace maxlen可能是什么呢
    可能是abc 和ac 那就是2
    也有可能是ab 和ace 那就是1
    然后比较发现2更大，所以取更大的

public int longestCommonSubsequence(String text1, String text2) {
    int l1=text1.length();
    int l2=text2.length();
    int[][]dp=new int[l1+1][l2+1];//表示以i-1,j-1为结尾的，他们的公共子序列长度，因为你最后要能取到dpl1l2,表示l1-1，l2-1为结尾的，所以你初始化得到l1+1,l2+1
    for(int i=1;i<=l1;i++)
    {
        for(int j=1;j<=l2;j++)
        {
            if(text1.charAt(i-1)==text2.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 dp[l1][l2];
}

public int minDistance(String word1, String word2) {
    int[][]dp=new int[word1.length()+1][word2.length()+1];
    
    for(int i=0;i<=word1.length();i++)//也是小于等于
    {
        dp[i][0]=i;
    }
    for(int j=0;j<=word2.length();j++)
    {
        dp[0][j]=j;
    }

    for(int i=1;i<=word1.length();i++)
    {
        for(int j=1;j<=word2.length();j++)
        {
            if(word1.charAt(i-1)==word2.charAt(j-1))//因为表示的是i-1,j-1的编辑距离，所以要比较i-1和j-1
            {
                dp[i][j]=dp[i-1][j-1];
            }else
            {
                dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
    }
    return dp[word1.length()][word2.length()];
}