烧鸡100二刷

前言

二刷啦

哈希部分

1. 两数之和 - 力扣（LeetCode）

思路：直接哈希表存入值和下标，然后判断target-nums[i]在不在里面，在就直接返回了

这样避免两次遍历，无敌

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

49. 字母异位词分组 - 力扣（LeetCode）

思路：异味词，排序之后值是相同的，把排序之后的str作为key，有相同key的放进同一个list里

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());
}

双指针

283. 移动零 - 力扣（LeetCode）

思路：把不是0的数全覆盖前面的，留到后面的全变成0

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

11. 盛最多水的容器

思路：从两边开始往内收，然后矮的一边先收即可，因为矮的一边才影响矩形面积

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

15. 三数之和 - 力扣（LeetCode）

思路在注释里面，有一说一二刷自己会写了

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

42. 接雨水 - 力扣（LeetCode）

思路：按列求，维护左边最大高度和右边最大高度，然后两者取小的再减去本身高度，乘1，就是这一列能存多少水

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

无敌思路

滑动窗口

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

最开始的思路：i，j,滑动窗口，但是发现不行，需要一个数据结构来维护i和j之间的

那么想到了hashmap，为什么不用set，因为你要求长度，还得保存下标

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

left = Math.max(left,map.get(s.charAt(i)) + 1);
left是子串的起始位置
遇到重复元素的就把重复元素下标+1作为子串的起始位置left，即 left = map.get(s.charAt(i)) + 1； 但由于有 ‘abba’ 这样的字符，当 ‘b’ 重复时，left 已经记作2，
再次循环，遇到重复元素 ‘a’ 时 , left就会被记作1，这样子串起始位置left就从2倒退回1了 ，乱掉了。

所以为了再次循环到重复元素 ‘a’ 时，防止left 子串起始位置不倒回去，保持之前重复元素 ‘b’的值,
就对比一下老的left 和新的left = map.get(s.charAt(i)) + 1
谁大，就是正确的left , 即left = Math.max(left,map.get(s.charAt(i)) + 1);

438. 找到字符串中所有字母异位词

思路：维护一个和要找的单词的长度一样长的滑动窗口，然后滑动判断是不是异味词

复杂度取决于你如何判断是不是异味

这里选择统计窗口内各字母的个数，这样只用on

注意点：比较两个List是否相同直接Arrays.equal

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

560. 和为 K 的子数组

思路：其实类似于两数之和的哈希方法，只不过这一次变成了数组连续和

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

239. 滑动窗口最大值

二刷第一反应想到优先队列，但是超时了

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

看答案发现是用双向队列，维护一个单调递减，其实我也想过用递减栈

我是先想到递减栈，然后发现优先队列可以不用自己push然后pop排序

非常重要的思路就是：只存放下标，不存放具体的数值，这样就不用把poll的再add回去，简直无敌

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

76. 最小覆盖子串 - 力扣（LeetCode）

看我的思路：

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

知道我的思路错在哪了吗？

比如测试用例”ADOBECODEBANC”，我的结果是”ADOBEC”，为什么，因为当我第一次找到”ADOBEC”后，start到了O， 然后一直找一直找，找到最后的C，才包含了所有字符，但是此时截取的是ODEBANC，判断比ADOBEC长，所以返回了ADOBEC

也就是说，这里无法保证是最小的长度，只对end进行处理是不行的，找到end后，还需要回头处理start

正确的思路：

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

普通数组

53. 最大子数组和 - 力扣（LeetCode）

简单动态规划，秒了

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

56. 合并区间 - 力扣（LeetCode）

这题目听绕道，得讲清楚

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()][]);
}

189. 轮转数组 - 力扣（LeetCode）

思路很清晰，但是注意k要%nums.length

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

238. 除自身以外数组的乘积

这次自己用空间复杂度on的做出来了

思路就是左积乘右积

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

但是还能优化，先鸽了

41. 缺失的第一个正数

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

矩阵

73. 矩阵置零

首先想到用o（m+N)的额外空间

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

是否可以优化，答案是可以的，但我认为这个傻逼优化没有任何意义，所以爷不学了

54. 螺旋矩阵 - 力扣（LeetCode）

这题目现在可以得心应手了，思路就是改变边界

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

240. 搜索二维矩阵 II - 力扣（LeetCode）

这个也是得心应手啦

记住从右上角开始即可

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

48. 旋转图像 - 力扣（LeetCode）

之前是嗯背公式，这一次才懂了怎么地推的

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

链表

160. 相交链表 - 力扣（LeetCode）

常规做法：先求两个的长度，然后较长的先走过长度之差，然后再一直走，直到相遇

但是，非常规做法

思路：

我们设A长度为a，B长度为b,相遇节点往后的长度为c

那么A如果先走完A，再从B的头走到相遇节点，会走过a+b-c的路程

同样，B先走玩B，再从A的头走到相遇节点，会走过b+a-c的路程

所以我们只需要让A先走A再从B头开始走，B先走B再从A头开始走，返回A=B的时候就行了

如果相遇自然是node，如果不相遇那就是null

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

206. 反转链表 - 力扣（LeetCode）

鉴定为模板

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

234. 回文链表 - 力扣（LeetCode）

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

141. 环形链表 - 力扣（LeetCode）

这个的原理其实是个人就懂，但是如何写，如何写while循环，判断的顺序，很有问题

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

142. 环形链表 II - 力扣（LeetCode）

这个直接被结论

1.判断有没有环

2.fast移动到开头每次走一个，slow也每次走一个直到相遇

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

2. 两数相加 - 力扣（LeetCode）

思路在注释里面了

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

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：找倒数第n个节点很简单，但是要删除它，我们应该找倒数第n+1个节点

解决办法在注释

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

24. 两两交换链表中的节点 - 力扣（LeetCode）

这题没啥好说的，多谢几遍记住交换的 代码就行了

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

25. K 个一组翻转链表

思路：用栈

注意事项：当count<k的时候，直接连接就行了，因为本来就是连起来的

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

138. 随机链表的复制 - 力扣（LeetCode）

有一说一题没看懂
有一说一太简单了

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

148. 排序链表 - 力扣（LeetCode）

一眼归并排序，但是归并排序我还不是很熟，我草我是傻逼

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

注意注释中关于fast的位置的讨论

23. 合并 K 个升序链表 - 力扣（LeetCode）

有了归并排序的基础，这个应该有所想法

首先最容易想到的就是，我顺序进行两两归并排序

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

思路二：无敌

不是合并k个链表吗，那么我们用一个优先队列，大小为k，存储这k个链表中，还未被合并的元素，那么堆头就应该是还未被合并的，最小的那个，然后不断合并， 不断add即可，天才！

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

146. LRU 缓存 - 力扣（LeetCode）

有一说一没写过，奶奶的

其实就是知道怎么用LinkedHashMap

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

二叉树部分

94. 二叉树的中序遍历 - 力扣（LeetCode）

直接递归

注意res写全局变量

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

104. 二叉树的最大深度 - 力扣（LeetCode）

依然是递归啊，先写不满足的条件就行了

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

226. 翻转二叉树 - 力扣（LeetCode）

依然是递归

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

101. 对称二叉树 - 力扣（LeetCode）

依然是递归，但是需要辅助函数，以及要注意，辅助函数不能直接else return false

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

543. 二叉树的直径 - 力扣（LeetCode）

我的思路：直径其实就是node的左右深度之和，所以我得先实现一个求深度的代码

然后设置全局变量，在递归的过程中，更新ans的最大值即可

因为你从root开始，每一个节点都会做一次求深度

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

102. 二叉树的层序遍历 - 力扣（LeetCode）

这个就太简单了，当然因为要分层存入，所以得记录size，这个注意一下

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

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

鉴定为易

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

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

//方法一：中序遍历放入数组里
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);
    }
}

199. 二叉树的右视图 - 力扣（LeetCode）

思路：中序遍历，然后，存储每一层的最后一个元素即可

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

114. 二叉树展开为链表 - 力扣（LeetCode）

方法一：就是先序遍历放到数组里面，然后再建立

方法二：

思路：最后的链表与前序遍历相同， 我们可以试着用前序遍历来写

但是写完后会发现，当遍历右子树的时候，你的根的right已经指向根的left部分了，怎么办呢

答案是：逆前序遍历,也可以说是变心的后序遍历,变成右左根，右左根，然后右的上一个就是根了

每遍历一个节点就将当前节点的右指针更新为上一个节点，这样就不会丢失右孩子

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

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

哎哎哎，这题目剑指offer有，烧鸡100有，但是爷还是不能秒

思路是人人都会，就是找到根，然后递归，根就是现需遍历里的第一个

注意：此处我们选择左臂右开区间，以及递归必须先写终止条件

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

437. 路径总和 III - 力扣（LeetCode）

第一时间想到前缀和，前缀和的核心：map

当然深度优先搜索也是回溯，所以你必须不能忘记回溯

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

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

这个题目，作为二刷，我首先想到，自己也是自己的祖先

所以分为三种情况，a和b，

要么a是b的祖先，要么b是a的祖先

要么a和b分在一个祖先的左右子树

然后用金典几行代码

两种都得会，来看看第一种：

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

124. 二叉树中的最大路径和 - 力扣（LeetCode）

有一说一虽然是困难题，但是有了二叉树的直径的基础，还是很好想到的

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);//返回这个结点的最大一条路径，因为如果这一个节点不是最后的中间那个节点，那么他被选取的时候只能作为左或者右路径的一部分
    }
}

图论部分

200. 岛屿数量 - 力扣（LeetCode）

可以用dfs，也可以bfs

但是爷都不会

DFS:

有一说一这挺好想的

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

但是bfs如何写呢，众所周知树的层序遍历也就是bfs

尝试写一写

注意：至于加入过队列就表示被访问了

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; //只要加入队列就标记为访问
                }
            }
        }
    }
}

994. 腐烂的橘子 - 力扣（LeetCode）

注意点，在普通的bfs基础上又增加了记录好橘子个数

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;//返回轮数
        }
    }
}

总的来说bfs不是很难，刷两道就会了，上下左右都是套路

207. 课程表 - 力扣（LeetCode）

经典的拓扑排序问题，这题用bfs更好理解

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

208. 实现 Trie (前缀树) - 力扣（LeetCode）

有一说一这题目一直没咋弄明白，虽然最后实现很简单

宗旨：递归+用26个空格表示26个字母，isEnd表示该单词是否结束

新建searchprefix函数寻找相同前缀的最后一个节点

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(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

46. 全排列 - 力扣（LeetCode）

我一开始怎么写的：

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();
         }
     }
}

我错哪了呢？

在你的代码中，错误在于你将 path 直接添加到 result，而在回溯的过程中，path 是会发生变化的，因此实际上你添加到 result 的是 path 的引用，而不是 path 的一个快照。这导致最终 result 中的所有列表都是相同的。

为了解决这个问题，你应该保存 path 的一个拷贝，而不是直接将它添加到 result。这可以通过创建一个新的 LinkedList 对象来实现。修改 result.add(path); 这行代码如下：

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

正确的，所以我的思路没错，代码随想录还用了used数组来判断是否用过

我还以为是我也得那也判断，原来是因为addpath的时候错了

正解：

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();
        }
    }
}

78. 子集 - 力扣（LeetCode）

注意starindex的取用，以及什么时候add path

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();
        }
    }
}

17. 电话号码的字母组合 - 力扣（LeetCode）

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

我一直没高清一个东西，就是数字对应的字符，abc，如何遍历到a,b,c呢、

就是说如何取到ad,bd,ae,be,af,bf等等

其实这就是最后回溯取到的,我上一轮取到a了，那么，回溯了把a删了，然后i++，取到b，以此类推

这下总算是弄清了

39. 组合总和 - 力扣（LeetCode）

我的想法：不用sum，而是在递归的时候用target-candidates[i]

但是我的代码有一个错误：

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)

这里错了啊，你递归的时候减去candidates[i],判断条件不应该是if (starindex >= candidates.length || target == 0)吗

如果这样写candidates[starindex]==target，那么只会取到candidates[i]这一个数等于target的，其他的情况就全没了

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

这里也错了，因为你是可以用相同元素的，所以应该是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);
        }
    }
}

22. 括号生成 - 力扣（LeetCode）

有一说一这题之前没写过

思路（核心：1. 能生成左括号：左括号剩余数量大于0 2. 能生成右括号：右括号剩余数量大于左括号剩余数量

什么时候返回：当左右括号剩余数量都等于0

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

为什么代码中没有回溯的部分？因为字符串每次变化都是新生成一个对象，所以不用回溯

79. 单词搜索 - 力扣（LeetCode）

有一说一这题放图论里更好，跟回溯除了dfs有回溯，其他没什么关系

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

131. 分割回文串 - 力扣（LeetCode）

我的问题在于，如何取到”aa”这种

答案：设置starindex，作为每次分割后，剩余部分，那么也就是从剩余部分继续做回溯

有一说一理解了以后简单啊

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

51. N 皇后 - 力扣（LeetCode）

大名鼎鼎的n皇后问题，奶奶的

此问题难点是，之前的回溯问题全部都是一维数组，而此问题变成了二维

代码随想录的思路：第一次第一行，第二次第二行这样，一行一行取

然后行内的取，由for循环实现

这样一想其实和电话号码的字母组合逻辑是一样的

其实这题的难点在于

1.把他想成是一维的

2.怎么实现”放置皇后”，”棋盘”等抽象的动作

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

二分

众所周知，二分的边界问题非常重要，所以二刷，我得着重理解边界问题

最终决定出我的二分查找的边界，是闭是开，然后都这么写

35. 搜索插入位置 - 力扣（LeetCode）

这就是最基本的二分查找，直接写就行了

这边取[]，左闭右闭区间

记住原则：就是你要保证能取到所有的数，不能有区间没取到

也不能重复边界

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

74. 搜索二维矩阵 - 力扣（LeetCode）

方法一：每一行去二分

方法二：观察

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

我的思路：先判断有没有这个数，如果没有那就返回-1,-1

如果有，那就二分寻找左右边界

如何寻找左右边界？找到左边界的左边，右边界的右边，然后返回+1，-1即可

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

感觉没我的好懂（

33. 搜索旋转排序数组 - 力扣（LeetCode）

首先我们观察旋转了的数组的特点，我们会发现

旋转之后，旋转点右侧的数组，小于旋转点之前的那个数

旋转点左侧的数组，大于等于之前那个数

要求logn，那么肯定是二分

我的选择是先找到下标，然后对左右进行二分

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

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

这题目，观察发现，

旋转后的数组，前面的部分，大于等于nums[0]，后面的部分小于nums[0]

所以我们二分，然后和nums[0]比较，如果大于等于nums[0]那说明mid在第一段里面

而最小值肯定是第二段的开头，那么 这个时候就更新left

如果小于nums[0] ，那么说明mid在第二段里，更新right

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

因为当这个数组鸭没旋转的时候，left最后会走到数组外面

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

虽然是烧鸡100二刷，但是这一题其实是一刷，草！

这一题的核心问题：找中位数如何与二分查找联系

思路：其实跟二分没勾八关系、

思路：要找中位数，也就是找第:

​ 对于奇数：(l+r)/2向下取整个

​ 对于偶数那就是要求两个

我们每次循环去掉k/2个元素，然后递归

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


    }
}

总结：二分部分比一刷有了提升，很不错

栈

20. 有效的括号 - 力扣（LeetCode）

简单

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();//最后还有没有多余的
}

155. 最小栈 - 力扣（LeetCode）

这个也很简单，就是用两个栈，一个栈存放原来的，就是普通的栈，另一个栈保存最小值

如何达到保存最小智呢，每次push都和栈头比较呗，小了就push新的，不然还是push栈头

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();
    }
}

394. 字符串解码 - 力扣（LeetCode）

这个题目的核心思想

一句话，就是遇到[入栈，遇到]出栈

出栈的时候，出几次，append几次，要根据前面的数字来

那么我们就需要两个栈，一个记录字符串，一个记录前面的数字

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();
}

739. 每日温度 - 力扣（LeetCode）

这一题呢，一眼单调栈，因为是要找第一个比他大的，那么肯定是递减站啊

注意：栈里我们只要存下标就可以了，方便计算是几天后

理解：找第一个比他大的，那么就得是要递减栈，然后遇到比他大的，就可以对栈的数一个一个比较，直到栈内有数比他还大

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

84. 柱状图中最大的矩形 - 力扣（LeetCode）

虽然是烧鸡100二刷，但是这题是一刷

思考：这个题目和”盛水最多的容器”有异曲同工之妙，但是问题是

此处的高，是在left和right之间的最小值，这也是它和栈联系起来的地方

但是问题是，left可以动，right可以动， 那么这个如何pop呢

然而我发现我的思路是错的，正确答案都是枚举高度，然后看他能取到的最大宽度，呜呜呜

问题转换为当使用某个 height[i]作为矩形高度时，该矩形所能取得的最大宽度为多少

而最大宽度如何去计算？就是height[i]左边第一个比他矮的下标l，右边第一个比他矮的下标r,r-l-1就是宽度

所以我们设置两个数组，分别记录i对应的第一个比他矮的左下标，第一个比他矮的右下标

那么计算这两个数组不就和上一题“每日温度”一样吗

鉴定为易

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

总结：通过上面两题，我们总结出了，找第一个比他小的，那就是递增栈（把比他大的全poo了），找第一个比他大的，那就是递减栈（比它 小的全pop了）

堆

这里的注意点，就是我们要回熟练的写compare

215. 数组中的第K个最大元素 - 力扣（LeetCode）

思路很简单，我设置应该堆，先全进去，然后不断pop，第k个出来的就是第k大的，注意没有第0大的这说法，所以最后判断条件是k>1

当然这个是要最大堆，所以你的compare得重写

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();
}

但是这样傻逼面试官会让你自己实现堆，我认为这是司马行为， 所以如果考到只能用另一种方法

快速排序：

第k大，就是排序完后下标为N-K的元素

每次快速排序后，可以确定这个pivot的最后位置，第一大元素在N-1下标，以此类推

所以思路是：

如果pivot最后<N-K,那么在pivotindex+1~right里继续找

如果>则在left~pivot-1里找

注意这里的pivot是随机找，然后找到了还得先和left交换，最后还得还回去，我曹

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

347. 前 K 个高频元素 - 力扣（LeetCode）

思路：设置map，先统计每个元素出现的次数，然后重写compare方法，加进大小为k的小顶堆当中

当堆满后，新元素和堆头元素比，如果比他大，那么就把新元素加进去，堆头扔掉

全部结束后，队里剩下的就是最大的k个

：注意：如果不设置大小为k，然后用大顶堆，最后push k 次大顶堆的堆头，这样复杂度不会优于ologn

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

二刷一遍过，鉴定为掌握了

295. 数据流的中位数 - 力扣（LeetCode）

思路：求中位数，那就是说要获得最中间的两个数的和/2，如何较快的获得中间两个数呢？

建立两个堆，一个大，一个小，那么大顶堆的顶，就是前一半的最大值，小顶堆的顶就是后一半的最小值

问题是如何处理奇数的情况呢？

如果是偶数，那么两个堆大小相等，对于奇数的情况，我们人为控制较小的一半size不小于较大的一半，这样奇数情况，直接返回大堆的size即可

add的时候如何知道加入哪一个堆呢？

我们的解决方案是，先进较小的一半（大堆），然后把大堆里最大的add到最大的一半里

但是这样会导致较小的一半永远只有一个元素了

我们人为控制较小的一半size不小于较大的一半，这样奇数情况，直接返回大堆的size即可

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();
        }
    }
}

贪心

121. 买卖股票的最佳时机 - 力扣（LeetCode）

思路：设置res[i]表示第i天卖出股票能取得的最大收入

最大收入肯定等于：当前股票的价格-这一天之前股票的最低价

所以我们维护一个i，维护一个最低价，然后再维护一个最高利润即可

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

55. 跳跃游戏 - 力扣（LeetCode）

思路：维护跳跃的最远位置

我卡在哪了？

我认为只能知道第一轮跳跃的最远位置manlen，然后进行for(int i=0;i<maxlen)循环，更新了maxlen也没用啊

正解：还是对整个进行遍历，i如果超过了maxlen就return false不就行了

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

45. 跳跃游戏 II - 力扣（LeetCode）

一开始的思路：就是每次跳到最远

但是发现这样通过不了很多测试用例

后来的思路：还是对整个进行遍历，当maxlen边长了之后才增加steps+1，还是不对，因为你无法保证变长的时候，是变的最长的那个情况

正确的思路：对maxlen中的nums[i]+i进行贪心，也就是说选择当前可以跳到的位置中，他们又能跳到的位置里，最远的

也就是关注下一次跳跃的距离，而不是这一次

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

考虑以下情况，如果 i 的值等于 nums.length - 1，那么在下一步的迭代中，我们会更新 maxPos，但由于 i 已经等于 nums.length - 1，我们无需再进行下一步的迭代。因此，为了避免多余的一次迭代，循环条件是 i < nums.length - 1。

763. 划分字母区间 - 力扣（LeetCode）

思路：遇到一个字母，就找他的lastindexof，、

然后顺着遍历，如果新的字母的lastindexof超过了当前的lastindex，那就更新边界end

如果遍历到end了，那么当前长度就从0重新开始，并且把长度加入结果list

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

动态规划

动规南中难，还是得多刷，奶奶滴

70. 爬楼梯 - 力扣（LeetCode）

这个就很简单，地推公式就是，走到这一层的方式等于走到上一层和上上一层的方式加一

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

198. 打家劫舍 - 力扣（LeetCode）

这个问题的核心在于，每一个房子都有两种状态，就是偷与不偷

所以我们dp[i]表示，走到这个屋子时，手上的最大金额

如果偷，dp[i]就是dp[i-2]+nums[i]，不偷那就是dp[i-1]

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

二刷一遍过，无敌

279. 完全平方数 - 力扣（LeetCode）

这个的问题是怎么和动态规划联系在一起

看到输入是int n ，会自然而然想到dp[n+1],但是这个数组代表什么呢

哎，我忘了，这是背包问题！

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

和01背包的不同就是，遍历背包是正序遍历

二维：dp[ i] [ j ]表示0-i的物品任意放到容量为j的背包里的最大价值

一维：dp[j ]容量为j的背包所能装的最大价值

一维就是把二维的上一层状态拷贝下来了

所以这里面，容量就是n，物品就是i，物品的价值就是i*i

完全背包的公式

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

322. 零钱兑换 - 力扣（LeetCode）

有了上一题的基础，这一题也是完全背包问题

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

139. 单词拆分 - 力扣（LeetCode）

有了上两题的基础，这样又是经典完全背包问题

物品就是单词，容量就是什么String的长度

然后我们还是用一维，dp[j]就是长度为j的字符串能否被拆分

地推公式就是，如果[i,j]这个部分在单词数组里，并且dp[i]=true，那么dp[j]也是true

这一题只能先遍历背包，再遍历物品，为什么？

因为你的String里单词是有顺序的，你要求的并非存不存在，而是包含了顺序的，所以你得先遍历背包，也就是String

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

300. 最长递增子序列 - 力扣（LeetCode）

刚开始的思路：dp[i]为以i结尾的最长递增子序列的长度

递推公式,如果nums[i]比nums[i-1]大，那么等于dp[i-1]+1,否则等于dp[i-1]

然后发现错了

新的思路：

dp[i]为以i结尾的最长递增子序列的长度

递推公式,如果nums[i]比nums[i-1]大，那么等于0-i-1里面dp[j]最大的+1,否则等于1

这个过程可以优化为：

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

118. 杨辉三角 - 力扣（LeetCode）

这一题是一刷，南蚌

//思录：按规律来,
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;
}

152. 乘积最大子数组 - 力扣（LeetCode）

思路：因为数组里面有正有负，所以我们要维护一个最大正值和最小负值(也不一定是负值，反正是最小值)

dp[i]是什么？以nums[i]为结尾的子数组的最大乘积

递推公式是什么？如果nums[i]大于0，那么就去乘最大正值，如果这个值比dp[i-1]大，那么就更新，否则dp[i]等于他本身

这种思路不对，因为题目只要求返回最大的值就行了

所以我们的dp应该对最大正值和最小负值去进行dp

maxdp[],mindp[],

地推公式，没啥地推的，就是nums[i],maxdp[i-1]** nums[i] ,mindp[i-1]* *nums[i]直接比较就行了

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

416. 分割等和子集 - 力扣（LeetCode）

思路：我上来直接先排序

后来发现错了，因为可以有 1 2 1 2这样的情况，但是你i排序后1 1 2 2这样用排序的方法是没用的！！！！

但是这个问题，细看你就会发现，这不就是背包问题么

总容量就是sum/2，然后物品就是你给的数组，就看看你给的数组里能不能装满这个背包不就行了!然后元素不能重复使用

01背包！

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

32. 最长有效括号 - 力扣（LeetCode）

上次通过还是二月五号，奶奶第

思路一：也就是我上次通过的思路，用栈，就是做括号匹配，过程中记录最大匹配长度

那么如何记录呢，栈存放 下标就行了，但是这里的一些细节比较反直觉，不用这种

ps:反直觉个锤子，我曹，简单的一批好吧:angry:

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

具体思路比较复杂我这就不谢了，到时候自己看题解吧

技巧部分

136. 只出现一次的数字 - 力扣（LeetCode）

异或：同0异1

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

169. 多数元素 - 力扣（LeetCode）

之前没有用时间复杂度On解决问题，这次来解决一下

这里用的是投票算法

选取一个数为候选人，如果遇到和他相同的数，那么count++,否则count–,如果count=0了，那么就切换候选人

很好理解，因为你的多数元素肯定是大于一半的，如果你能等于0 ，那就说明和你不一样的，比和你一样的多，那你就是不是超过半数的元素了

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

75. 颜色分类 - 力扣（LeetCode）

思路：22222->1112222->0011222

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

思路2：有没有觉得很类似于“一次排序把奇数放到偶数之前”

那个题目原理就是快速排序的一次partition，这个题目也类似

先鸽了

31. 下一个排列 - 力扣（LeetCode）

这题思路很吊，建议看题解

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

287. 寻找重复数 - 力扣（LeetCode）

思路：将数组看做链表

重复的数字就是环的入口，那么我们用环形链表2的思路就很好解了

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

多维动态规划

62. 不同路径 - 力扣（LeetCode）

这个就很简单，因为你只能从左边或者上面过来，所以递推公式就是

dpij=dpi-1j+dpij-1

然后初始化，第一行和第一列都只有一种走法

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

64. 最小路径和 - 力扣（LeetCode）

这和62异曲同工之妙啊

dpij是到达ij最小的路径和

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

}

5. 最长回文子串 - 力扣（LeetCode）

一开始的思路：设置左右指针，但是不知道什么时候移动他们

正解：左右指针不是在首尾，而是中心扩散，这是方法一

动态规划方法：

回文天然具有「状态转移」性质：一个长度严格大于 2的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。

dpij：i到j是不是回文（闭区间，而不是说dpi表示以i结尾的最长回文子串

递推公式也很简单，就是si等不等于sj并且dpi+1j-1也是true即可

初始化：单个字符肯定是回文，所以dpii=true

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

1143. 最长公共子序列 - 力扣（LeetCode）

又是经典问题

注意dpi,j定义为0，i-1 0，j-1的最长公共子序列长度

为什么这么定义呢，为了方便初始化，反正你记住就行了

是为了方便当 i = 0 或者 j = 0 的时候，dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为 0.

如何理解递推公式：

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

72. 编辑距离 - 力扣（LeetCode）

这个题目的关键在于：

1. 添加元素和删除元素，他们加的次数都是1，所以没必要区分

   所以这样就变成了，删除和修改两个操作

   删除：要么word1删，要么word2删，这两个得分开来

   修改：随便哪个修改，结果都是一样的，反正都变得一样了

2. 你无需具体知道每一步到底是用删除还是修改，只需要把所有的情狂都考虑到，然后取最小的情况就行了

   dp[i][j]：还是i-1,j-1的字符串，编辑的最小距离
   初始化：dp[i][0]全是i，因为你是和空字符串比,dp[0][j]也是
   递推公式：
   如果不同
   	当word1删，那就变成了dp[i-1][j],word2删，就是dp[i][j-1]
   	当修改，那就是dp[i-1][j-1]
   	然后取最小的加一
   如果相同
   	那不用操作

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