【Leecode】Hot100刷题笔记

YanDDDeat2025/12/19...大约 58 分钟

1、computeIfAbsent、getOrdefault、merge

2、List.toArray(new int[0][])

3、map.keySet().iterator().next()

4、Arrays.copyOfRange(nums,mid+1,len)

Scanner sc = new Scanner(System.in);

sc.next()...

方法	读取内容	分隔符	特点
`next()`	String	空格	读到空格/换行停止，返回String
`nextInt()`	int	空格	读到空格/换行停止，返回int
`nextLine()`	String	\n	读到换行停止，返回整行（包含空格）

一、数组

1. 两数之和

遍历数组，用map记录遍历过的元素，每轮获取map.getOrDefault(target-nums[i],-1)
若不为-1直接返回找到的值
若为-1把当前元素放进map继续下一个

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

49. 字母异位词分组

1、用 map<String, List<String>> 维护，key 是排序后的 String，value 是异位词的数组。
2、遍历字符串数组，先取strs[i].toCharArray()进行排序后，得到顺序的异位词，取出map的list，把实际的String添加进去即可
3、把 Map 的 value 处理成 List<List<String>> 返回即可
注：记一下 map 的函数 computeIfAbsent(key, key -> xxx)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap();
        for(int i=0;i<strs.length;i++){
            char[] currChar = strs[i].toCharArray();
            Arrays.sort(currChar);
            String sameStr = new String(currChar);
            map.computeIfAbsent( sameStr,_->new ArrayList<String>()).add(strs[i]);
        }
        // List<List<String>> ans = new ArrayList();
        // for(String curr:map.keySet()){
        //     ans.add(map.get(curr));
        // }   
        // return ans;
        return new ArrayList(map.values());
    }
}

128. 最长连续序列X-Chat

1、用HashSet把数组里面的元素装起来。
2、从头遍历Set里面的元素Curr，拿到后去Set里面看有没有contains(curr-1)（找连续）
3、若有，表示当前位置不是最小的元素，继续遍历set，直到Curr-1不存在（表示当前元素是某个连续序列的最小元素），则当前位置和最开始的Curr的距离就是一个连续序列，执行while(set.contain(curr+1))直到不存在，得到当前连续序列长度；维护最长序列长度。
o(n2)

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set =  new  HashSet();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int ans=0;
        for(int curr:set){
            if(set.contains(curr-1)){
                continue;
            }
            int y = curr+1;
            while(set.contains(y)){
                y++;                
            }
            ans = Math.max(ans,y-curr);
            // 说明此链已经最长
            if(ans*2>set.size()) break;
        }
        return ans;
    }
}

283. 移动零

用两个指针，一个指针X记录数组遍历位置，一个指针Y记录非0元素可以填充的位置。
1、遍历数组，若当前元素为0，X++，Y不变
2、若当前元素不为0，表示此元素要保留，将此元素填充到指针Y的位置，然后Y++
3、遍历完后，指针Y-nums.length位置fill成0

class Solution {
    public void moveZeroes(int[] nums) {
        int X=0,Y=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                continue;
            }else{
                nums[Y]=nums[i];
                Y++;
            }
        }
        Arrays.fill(nums,Y,nums.length,0);
    }
}

11. 盛最多水的容器

使用左右双指针，向中间移动
1、初始化最左最右指针，计算当前面积（水量），min(nums[l],nums[r])*(r-l)，计算后维护全局最大量
2、根据左右柱子高度，移动柱子矮的那一方，重复计算

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

15. 三数之和X-Chat

1、先对数组排序，指针初始定义i=0遍历数组，每轮：j=i+1,k=nums.length-1，然后基于此找元素和为0满足要求
2、要满足不重复的三元组，当有 nums[i]+nums[j]+nums[k]==0 时，后面的j,k和不能与其上一个相邻

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int j=1,k=2;
        Arrays.sort(nums);
        List<List<Integer>> ans =new ArrayList();
        for(int i=0;i<=nums.length-2;i++){
            j=i+1;k=nums.length-1;
            if(i!=0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[j]>0) break;
            while(j<k){
                if(nums[i]+nums[j]+nums[k]==0){
                    // List.of(i, j, k) or Arrays.asList(i,j,k)
                    ans.add(new ArrayList(Arrays.asList(nums[i],nums[j],nums[k])));
                    j++;k--;
                    while(j<k&&nums[j]==nums[j-1]) j++;
                    while(j<k&&nums[k]==nums[k+1]) k--;
                }else if(nums[i]+nums[j]+nums[k]>0){
                    k--;
                }else{
                    j++;
                }
            }

        }
        return ans;
    }
}

42. 接雨水

1、用两个数组，分别计算存储每个柱子左右最高的柱子。只有左右柱子都比当前柱子高才能蓄水
2、然后遍历数组，计算min(左最高柱子,右最高柱子)与当前柱子谁高，若当前柱子高，则当前柱子蓄水直接为0，因为左右都并不高没法蓄水

class Solution {
    public int trap(int[] height) {
        int[] l =new int[height.length],r = new int[height.length];
        int lmax=height[0],rmax=height[height.length-1];
        for(int i=0;i<height.length;i++){
            l[i] = lmax;
            lmax=Math.max(lmax,height[i]);
        }
        for(int i=height.length-1;i>=0;i--){
            r[i] = rmax;
            rmax=Math.max(rmax,height[i]);
        }
        int ans=0;
        for(int i=0;i<height.length;i++){
            int curr = Math.min(l[i],r[i]);
            if(curr>height[i])
                ans+=curr-height[i];
        }
        return ans;
    }
}

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

1、str转char数组，使用双指针窗口遍历char数组，维护一个cnt =new int[101]数组（因为包含数字、字符），记录当前窗口里面每个字符数量
2、每次右指针移动时，cnt[curr]++，若当前cnt[curr]>1，则有重复，左指针移动直到当前cnt[curr]==1

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] c = s.toCharArray();
        int[] cnt= new int[128];
        int l = 0,ans=0;
        for(int i=0;i<c.length;i++){
            cnt[c[i]]++;
            while(cnt[c[i]]>1){
                cnt[c[l]]--;
                l++;
            }
            ans=Math.max(i-l+1,ans);
        }
        return ans;
    }
}

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

1、固定窗口p.length大小，分别用两个cnt[26]数组记录p的元素个数和s的窗口里面元素个数。
2、移动固定窗口，每轮比较两个cnt是否相同，若相同则为异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] snums = new int[126],pnums = new int[128];
        List<Integer> ans = new ArrayList<>();
        for(int i=0;i<p.length();i++){
            pnums[p.charAt(i)]++;
        }
        for(int i=0;i<s.length();i++){
            snums[s.charAt(i)]++;
            if(i+1<p.length()){
                continue;
            }
            if(isSame(snums,pnums)){
                ans.add(i-p.length()+1);
            }
            // 最左移出窗口
            snums[s.charAt(i-p.length()+1)]--;
        }
        return ans;
    }
    boolean isSame(int[] snums,int[] pnums){
        for(int i=0;i<126;i++){
            if(pnums[i]!=snums[i]) return false;
        }
        return true;
    }
}

560. 和为 K 的子数组

和为K的子数组，即计算不同前缀和的差。前缀和的差即为子数组的和。
1、维护一个map(Integer,Integer)，初始化map.put(0,1)，因为空数组的前缀和就是 0，而空数组本身是一个合法的"子数组"，这个初始化让前缀和算法能够处理所有从索引 0 开始的子数组。
2、，遍历数组，维护前缀和prefix，每一轮算map.getOrDefault(prefix-k,0)，若存在，即有子数组和为k。
3、然后把当前prefix值，加入若有相同的prefix值，则增加数量，然后继续直到遍历完

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int ans=0,prefix=0;
        for(int i=0;i<nums.length;i++){
            prefix+=nums[i];
            ans+=map.getOrDefault(prefix-k,0);
            map.merge(prefix,1,Integer::sum);
        }
        return ans;
    }
}

239. 滑动窗口最大值

在滑动窗口上，维护一个单调栈。
1、每次移动窗口时，移出最左的元素+所有比新进元素小的
2、每次就取栈里面最大的即可

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> s = new ArrayDeque();
        int[] ans = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            while(!s.isEmpty()&&nums[s.getLast()]<=nums[i]){
                s.removeLast();
            }
            s.addLast(i);
            if(i-k+1<0){
                continue;
            }
            while(s.getFirst()<i-k+1){
                s.removeFirst();
            }
            ans[i-k+1]=nums[s.getFirst()];
        }
        return ans;
    }
}

76. 最小覆盖子串

维护两个cnt数组，使用双指针维护滑动窗口；
1、窗口向右扩大，每轮比较两个cnt数组，若窗口内cnt包含t数组的cnt，则算覆盖，维护最小子串下标。

class Solution {
    public String minWindow(String s, String t) {
        int[] cnS = new int[128],cnT = new int[128];
        for(int i=0;i<t.length();i++){
            cnT[t.charAt(i)]++;
        }
        int l=0;
        int maxl=-1,maxr=s.length();
        for(int i=0;i<s.length();i++){
            cnS[s.charAt(i)]++;
            while(isConclude(cnS,cnT)){
                if(maxr-maxl>i-l){
                    maxl=l;maxr=i;
                }
                cnS[s.charAt(l)]--;
                l++;
            }
        }
        return maxl==-1?"":s.substring(maxl,maxr+1);
    }
    boolean isConclude(int[] cnS,int[] cnT){
        for(int i=0;i<cnT.length;i++){
            if(cnT[i]>cnS[i]) return false;
        }
        return true;
    }
}

53. 最大子数组和X-Chat

遍历子数组，维护最大前缀和与最小前缀和即可。
注：

class Solution {
    public int maxSubArray(int[] nums) {
        int ans=Integer.MIN_VALUE, pmin=0,prefix=0;
        for(int i=0;i<nums.length;i++){
            prefix+=nums[i];
            ans = Math.max(prefix-pmin,ans);
            pmin=Math.min(pmin,prefix);
        }
        return ans;
    }
}

56. 合并区间

1、把二维数组按第一个数排序。
2、遍历二维数组，若满足上一个数组的第二个数>=当前数组的第一个数，则可合并。

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

189. 轮转数组

k可能比数组长度大，若刚刚等于数组长度，相当于没有动；所以先对数组长度取余，找到实际轮转的个数。
0、将数组按【0，nums.length-k】【nums.length-k+1，nums.length】分成两块来看
1、向右动k个，即右边部分都要变到前面去，且翻转。左边部分也要变到后面去且翻转。
2、故只需要先整体翻转，然后把前部分和后部分再次翻转即可。

class Solution {
    public void rotate(int[] nums, int k) {
        k = k%nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }
    void reverse(int[] nums,int i,int j){
        while(i<j){
            int tmp = nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
            i++;j--;
        }
    }
}

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

只需要分别维护前缀积和后缀积，然后遍历数组分别把当前位置的前后两个积相乘就行。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] l = new int[nums.length+1],r = new int[nums.length+1];
        //前后缀积的第一个为1
        l[0]=1;
        r[nums.length]=1;
        for(int i=1;i<nums.length+1;i++){
            l[i] = l[i-1]*nums[i-1];
        }
        for(int i=nums.length-1;i>=0;i--){
            r[i] = r[i+1]*nums[i];
        }
        int[] ans = new int[nums.length];
        //算积时，前后缀的积为1的都要被算到。
        for(int i=0;i<nums.length;i++){
            ans[i] = l[i]*r[i+1];
        }
        return ans;
    }
}

41. 缺失的第一个正数

找缺失的第一个正数，则表示从有序1开始找。将内部数，按照对应nums[i]-1作为下标放到对应的位置，然后遍历找数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            // 若此数是正数，且在1，nums.length之间，把它放到对应的下标位置
            while(nums[i]>0&&nums[i]<=nums.length&&nums[nums[i]-1]!=nums[i]){
                int tmpIndex = nums[i]-1;
                int tmp = nums[tmpIndex];
                nums[tmpIndex] = nums[i];
                nums[i] = tmp;
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }
}

73. 矩阵置零

class Solution {
    public void setZeroes(int[][] matrix) {
        int rlen = matrix.length,clen = matrix[0].length;
        //记录哪些行列需要被置0，最后统一处理
        int[] rowZ = new int[rlen],colZ = new int[clen];

        //需要被置0的行与列，可以归属到对应的首行首列，先标注首行首列的那一行那一列需要置0，然后遍历数组，看当前元素是否在对应行列上即可。
 
        // 看哪些行列要被置0
        for(int i=0;i<rlen;i++){
            for(int j=0;j<clen;j++){
                if(matrix[i][j]==0){
                    rowZ[i]=1;
                    colZ[j]=1;
                }
            }
        }
        // 置0
        for(int i=0;i<rlen;i++){
            for(int j=0;j<clen;j++){
                if(rowZ[i]==1||colZ[j]==1){
                    matrix[i][j]=0;
                }
            }
        }
    }
}

54. 螺旋矩阵

声明一个方向数组，和当前已遍历的元素个数。
1、while循环：当已遍历个数少于总数时
2、记录一个当前的访问坐标x,y；在每一轮新入时，根据当前方向进行移动，用临时坐标记录移动位置。
3、移动后：while循环：保证当前坐标在容器内且当前元素未被访问；若不满足任一要求：说明需要换方向了。
4、换方向后再次检验第三条。直到满足。
5、满足条件后，把临时坐标赋值到x,y，然后把访问的元素添加到答案，并且将访问过的元素设为已访问，然后sum--。

class Solution {
    // x,y
    int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public List<Integer> spiralOrder(int[][] matrix) {
        int x=0,y=-1;
        List<Integer> ans = new ArrayList();
        int sum=matrix.length*matrix[0].length;
        int k=0;
        while(sum!=0){
            int tmpX = x + dir[k][0];
            int tmpY = y + dir[k][1];
            // 被访问或不在容器内,说明需要换方向了
            while(tmpX<0||tmpY<0||tmpX>=matrix.length||tmpY>=matrix[0].length||matrix[tmpX][tmpY]==-101){
                k=(k+1)%4;
                tmpX = x + dir[k][0];
                tmpY = y + dir[k][1];
            }
            x=tmpX;y=tmpY;
            ans.add(matrix[x][y]);
            matrix[x][y]=-101;
            sum--;
        }
        return ans;
    }
}

48. 旋转图像

先做矩阵转置，再做矩阵列对称reverse变换

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

240. 搜索二维矩阵 II

从右上角开始，int c = matrix[0].length-1,r =0;
1、右上角，左边全是比他小的，下面全是比他大的。
2、只需要移动即可

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

二、链表

1、进行快慢节点时，注意要条件是while(h!=null&h.next!=null)不要写漏了

2、map.keySet().iterator().next()

160. 相交链表

将其看做一个循环链表，找交点即可。每条路走到null后，回到起点，总会交汇，若交汇的是null，则无交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode hA=headA,hB=headB;
        while(hA!=hB){
            hA=hA==null?headB:hA.next;
            hB=hB==null?headA:hB.next;
        }
        return hA;
    }
}

206. 反转链表

头插法
1、定义一个null节点，作为新翻转后链表
2、while(head!=null)逐个把原链表的每个节点放到一个新链表的头上去。

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

234. 回文链表

1、找到链表中点，切割成俩个
2、把其中一个进行reverse翻转
3、然后逐个比对即可

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 找到链表中点
        ListNode prev=head,h=head,mid = head;
        while(h!=null&&h.next!=null){
            h=h.next.next;
            prev=mid;
            mid=mid.next;
        }
        // 切断链表为两份
        prev.next=null;
        // reverse后面那段
        ListNode sentinel = null;
        while(mid!=null){
            ListNode tmp = mid.next;
            mid.next=sentinel;
            sentinel=mid;
            mid=tmp;
        }
        // 逐个比对是否相同
        while(sentinel!=null&&head!=null){
            if(sentinel.val!=head.val) return false;
            sentinel=sentinel.next;
            head=head.next;
        }
        return true;
    }
}

141. 环形链表

1、定义快慢节点
2、一直循环跑，只要有环，fast必定会追上slow；
3、若无环，会跑到null节点，while会退出

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

142. 环形链表 IIX-Chat

1、同上，只不过slow==fast相遇时，不一定是入口交叉点。
2、定义一个节点从头开始，一个节点从slow开始，向后移动，相遇就是入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                // 说明有交点，h从头结点开始移动
                ListNode h=head;
                while(h!=slow){
                    h=h.next;
                    slow=slow.next;
                }
                return slow;
            }

        }
        return null;
    }
}

21. 合并两个有序链表X-Chat

1、合并递增，一定需要一个尾节点去链接后面的节点。
2、先用尾节点连接后面的节点后，对应的list1或list2直接移动到下一个就行，不用单独先摘除当前节点。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode senti = ans;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                senti.next = list1;
                list1=list1.next;
            }else{
                senti.next=list2;
                list2=list2.next;
            }
            senti=senti.next;
        }
        senti.next=list1==null?list2:list1;
        return ans.next;
    }
}

2. 两数相加

1、链表是从左到右逐渐高位，超过10要进位到后面。
2、挨个节点递归相加即可，递归终止条件是1、两个链表的节点都为空了 且 没有要进位的数字了。
3、单次就把进位的数与两个节点的数加起来，然后计算出个位数和要进位的数即可

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1,l2,0);
    }
    ListNode add(ListNode l1,ListNode l2,int jin){
        int sum=0;
        if(l1==null&&l2==null&&jin==0) return null;
        if(l1!=null){
            sum+=l1.val;
        }
        if(l2!=null){
            sum+=l2.val;
        }
        sum+=jin;
        jin = sum/10;
        // 当前数字为sum%10，因为节点不能大于10
        ListNode ans = new ListNode(sum%10);
        ans.next = add(l1!=null?l1.next:null,l2!=null?l2.next:null,jin);
        return ans;
    }

}

19. 删除链表的倒数第 N 个结点

1、使用哨兵节点
2、算倒数N个节点，就先用N，把sentinel节点和curr节点构造一个n的长度
3、当curr和sentinel节点一起移动，直到curr为null，则sentinel正好在倒数N+1
4、 sentinel.next=sentinel.next.next;忽略其下一个节点即可。然后返回哨兵节点的下一个节点即头。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curr=head;
        ListNode dummpy = new ListNode(0,head);
        ListNode sentinel = dummpy;
        while(n>0){
            curr = curr.next;
            n--;
        }
        while(curr!=null){
            sentinel=sentinel.next;
            curr=curr.next;
        }
        sentinel.next=sentinel.next.next;
        return dummpy.next;
    }
}

24. 两两交换链表节点

可以优化成k个一组交换
交换时需要考虑的问题：
1、是否满足有两个节点（node1、node2）来交换
2、交换时必须要前一个节点辅助交换
3、交换前必须记录node2的下一个节点

解题思路：

1.要一个哨兵节点辅助交换（问题2）

2.每次只用关注node2是否为空即可（问题1）

3.交换节点之前记录下一个节点（问题3）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n=0;
        ListNode h=head;
        while(h!=null){
            h=h.next;
            n++;
        }
        ListNode curr=head, dummpy = new ListNode(0,head),nxt=null;
        ListNode prevStart = dummpy;
        for(int i=0;i<n;i++){
               if((i+1)%k==0){
                // 到了一个块的尾部，需要交换了。
                // 暂存前后节点
                ListNode start = prevStart.next;
                nxt = curr.next;
                // 1.把当前k长的块裁剪下来
                prevStart.next=null;
                curr.next=null;
                // 2.reverse链表
                reverse(start);
                // 3.拼接回去
                prevStart.next = curr;
                start.next = nxt;
                // 4.设置新的prevStart
                prevStart = start;
                // 5.移动curr
                curr=nxt;
            }else{
                curr=curr.next;
            }
        }
        return dummpy.next;
    }
    ListNode reverse(ListNode head){
        ListNode h=null;
        while(head!=null){
            ListNode nxt=head.next;
            head.next=h;
            h=head;
            head=nxt;
        }
        return h;
    }
}

25. K 个一组翻转链表

思路：本质就是链表翻转。重点在于如何确定翻转的范围：
1、用长度数字进行遍历，记录这段起始点curr_head，到长度k后，翻转curr_head到curr这段链表。
2、翻转后如何拼接链表：此时翻转后变成三段（前，curr，后），需要用哨兵节点记录上一段的最后一个节点拼接前和curr段；翻转前记录后的第一个节点。反转后拼接上curr+后。
3、注意：(i + 1) % k == 0来判断。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n=0;
        ListNode h=head;
        while(h!=null){
            h=h.next;
            n++;
        }
        ListNode curr=head, dummpy = new ListNode(0,head),nxt=null;
        ListNode prevStart = dummpy;
        for(int i=0;i<n;i++){
            if((i+1)%k==0){
                // 到了一个块的尾部，需要交换了。
                // 暂存前后节点
                ListNode start = prevStart.next;
                nxt = curr.next;
                // 1.把当前k长的块裁剪下来
                prevStart.next=null;
                curr.next=null;
                // 2.reverse链表
                reverse(start);
                // 3.拼接回去
                prevStart.next = curr;
                start.next = nxt;
                // 4.设置新的prevStart
                prevStart = start;
                // 5.移动curr
                curr=nxt;
            }else{
                curr=curr.next;
            }
        }
        return dummpy.next;
    }
    ListNode reverse(ListNode head){
        ListNode h=null;
        while(head!=null){
            ListNode nxt=head.next;
            head.next=h;
            h=head;
            head=nxt;
        }
        return h;
    }
}

138. 随机链表的复制

思路：一模一样的复制，若没有random节点，直接遍历复制val即可。有random节点，必须知道在原链表中的节点的random指向哪个节点。做一个交错的复制链表，通过遍历时取next就能取到。但是要注意random为null的情况。
在每个原节点后插入复制节点形成交错链表，这样原节点的复制节点就是它的next，原节点的random指向的节点的复制节点就是random.next。通过三次遍历完成：第一次交错复制、第二次设置random指针、第三次分离链表。

    public Node copyRandomList(Node head) {
        Node h =head;
        // 1.先一个间隔一个的在原链表插入复制一个
        while(h!=null){
            Node tmp = new Node(h.val);
            tmp.next=h.next;
            h.next=tmp;
            h=h.next.next;
        }
        // 2.复制random字段，原链表节点对应的下一个
        h=head;
        while(h!=null){
            Node copy = h.next;
            // 注意random可能是null，没有下一个节点
            copy.random = h.random==null?null:h.random.next;
            h=copy.next;
        }
        // 3.利用dummy拆出节点
        h=head;
        Node dummy = new Node(0);
        Node tmp_dummy=dummy;
        while(h!=null){
            Node copy = h.next;
            tmp_dummy.next = copy;
            tmp_dummy=copy;
            h.next = copy.next;
            h=h.next;
        }
        return dummy.next;

    }

148. 排序链表

思路：链表排序，通过分治思想，把链表切割看成两个链表，然后递归使左右有序，合并有序链表即可

    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode mid = mid(head);
        mid = sortList(mid);
        head = sortList(head);
        return merge(mid,head);
    }

23. 合并K个升序链表->1

思路：分治思想，把数组切割看成两个数组，递归合并左右数组，到数组只剩两个时进行合并有序链表
通过下标指定即可。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        return sortKList(lists,0,lists.length-1);
    }
    ListNode sortKList(ListNode[] lists,int l,int r){
        if(l==r) return lists[l];
        int mid = (r+l)/2;
        return merge(sortKList(lists,l,mid),sortKList(lists,mid+1,r));
    }

146. LRU 缓存X-Chat

思路：借助LinkedHashMap（插入有序，最近最少使用的就在第一个）。注意Hashmap的API，containsKey(),map的iterator()先用keySet()进行获取

class LRUCache {
    int capacity=0;
    LinkedHashMap<Integer,Integer> map = new LinkedHashMap();
    LRUCache(int capacity){
        this.capacity=capacity;
    }
    int get(int key){
       Integer ans = map.remove(key);
        if(ans==null){
            return -1;
        }else{
            map.put(key,ans);
            return ans;
        }
    }

    void put(int key,int value){
        // 1、考虑：有or没有
        Integer tmpVal = map.remove(key);
        if(tmpVal!=null){
            map.put(key,value);
            return;
        }
        // 若没有原值
        // 2、考虑：满or没满
        // 没满
        if(capacity>map.size()){
            map.put(key,value);
        }else{
            map.remove(map.keySet().iterator().next());
            map.put(key,value);
        }
    }
}

三、二叉树

94. 二叉树的中序遍历

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

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
分别求左右即可

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

226. 翻转二叉树

从上到下翻转，先翻转当前左右子节点，再递归翻转其下层节点。
先递归翻转下层节点也行。

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

101. 对称二叉树

1、先看左右子节点是否对称相等
2、分别对左右子节点子树递归判断
注：注意递归时的子节点左右对应要反着

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return isSame(root.left,root.right);
    }
    boolean isSame(TreeNode l,TreeNode r){

        if(l==null&&r==null){
            return true;
        }
        if(l==null||r==null){
            return false;
        }
        boolean LSame = isSame(l.left,r.right);
        boolean RSame = isSame(l.right,r.left);
        return l.val==r.val&&LSame&&RSame;
    }
}

543. 二叉树的直径

直径，就是求最大左右子树高度和。
参考题目：求树高，在DFS遍历时加一个全局字段，每次比一下最大值就行

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

102. 二叉树的层序遍历

1、使用队列存每一层的节点（从root节点开始）
2、当队列不为空时一直while，每层循环进去时用len算当前层的size()个数，然后逐个把队列里面本层的节点拿出来，然后把val加入结果集，把左右子节点加入队列作为下一层的。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList();
        if(root==null) return ans;
        Deque<TreeNode> s = new ArrayDeque();
        s.addLast(root);
        while(!s.isEmpty()){
            List<Integer> currAns = new ArrayList();
            int len = s.size();
            while(len>0){
                len--;
                TreeNode currNode = s.removeFirst();
                currAns.add(currNode.val);
                if(currNode.left!=null){s.addLast(currNode.left);}
                if(currNode.right!=null){s.addLast(currNode.right);}
            }
            ans.add(currAns);
        }
        return ans;
    }
}

108. 将有序数组转换为二叉搜索树

1、数组有序，以中点构建根节点，左边全是小的，右边全是大的
2、递归构建左部分与右部分数组

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

98. 验证二叉搜索树

1、初始一个全局的最小值（Integer.MIN_VALUE），因为树的最左下角节点肯定是最小的
2、先看左子树是不是搜索树
3、看当前节点是否比左子树节点小或等与（小或等于都是错）
4、看右子树是不是搜索树

class Solution {
    Long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean l = isValidBST(root.left);
        // 若左子树不是搜索树或当前节点比其左子树节点小，则不是搜索树
        if(!l||root.val<=prev)  return false;
        prev = Long.valueOf(root.val;)
        return isValidBST(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素

1、定义一个ans最终值，以及一个index，当前遍历到第几个了
2、找第k小，要通过中序遍历，然后每次更新index位置，对比是否到k了，到了则赋值结果即可

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

199. 二叉树的右视图

就是层序遍历，在当前层，len==1时，把当前节点加入。
或者直接层序遍历代码不懂，然后把层析遍历的得到的结果，每个list的最后一个值取出来

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        if(root==null)  return ans;
        stack.add(root);
        while(!stack.isEmpty()){
            ans.add(stack.getLast().val);
            int len = stack.size();
            while(len>0){
                len--;
                TreeNode curr = stack.removeFirst();
                if(curr.left!=null) stack.addLast(curr.left);
                if(curr.right!=null) stack.addLast(curr.right);
            }
        }
        return ans;
    }
}

114. 二叉树展开为链表X-Chat

思路：题目要求将二叉树展开为链表，即按照按后序遍历顺序进行遍历。
展开后的结构应为所有左子树为空、仅用右指针连接的链表。
我们可以利用一个全局变量 prev 来记录当前已经构建好的链表的头节点。
对原树进行后序遍历（右子树 → 左子树 → 根节点），在遍历过程中依次将节点重新连接。
当前节点的右指针指向 prev（已构建的链表头），左指针置空；
更新 prev 为当前节点，使其成为新的链表头。

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

105. 从前序与中序遍历序列构造二叉树

思路：根据前序（根节点在最前）和中序（根节点在中间）特点，分割左右两个数组，然后分别递归构建左右子树。
1、先用获取前序（根节点在最前），把中序数组分割为两个子数组
2、用序数组分割的两个子数组的长度，将前序数组分割为左右两个子数组
3、分别将上述两个子数组递归构建左右子树
4、在数组长度为0时返回null
思考：为什么长度为1时进行mid+1取子数组也不会出现out length：因为先取inorder，mid只能为0为，mid+1=1，取（1，length）实际就是空数组了，就结束递归。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen  = preorder.length,inLen = inorder.length;
        if(preLen==0) return null;
        // 前序遍历第一个是root节点
        int inorderMidIndex = -1;
        for(int i=0;i<inLen;i++){
            if(inorder[i]==preorder[0]) inorderMidIndex=i;
        }
        // 根据中序遍历root节点切分左右子树的遍历数组
        int[] l_inorder = Arrays.copyOfRange(inorder,0,inorderMidIndex);
        int[] r_inorder = Arrays.copyOfRange(inorder,inorderMidIndex+1,inLen);
        int[] l_preorder = Arrays.copyOfRange(preorder,1,l_inorder.length+1);
        int[] r_preorder = Arrays.copyOfRange(preorder,l_inorder.length+1,preLen);
        // 根据切分的数组，递归构建左右子树
        TreeNode root = new TreeNode(preorder[0]);
        root.left=buildTree(l_preorder,l_inorder);
        root.right=buildTree(r_preorder,r_inorder);
        return root;
    }
}

437. 路径总和 IIIX-Chat

思路：要求路径和是从上到下满足targetsum，其实就是前缀和之差，递归二叉树，用curr记录到了的前缀和，用一个map存前缀个数，然后通过map.get(curr-targetsum)若有则表示有一段是满足和为targetsum的。
注意：
1、要先get后再进行存储个数（特殊情况tree=[1],targetSum=0）
2、当前节点结束后要把这包含这个节点的前缀和从map中取消。
3、map的key要设置为Long

class Solution {
    int ans=0;
    int targetSum=0;
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long,Integer> cnt = new HashMap();
        cnt.put(0L,1);
        this.targetSum=targetSum;
        dfs(root,cnt,0L);
        return ans;
    }
    void dfs(TreeNode root,HashMap<Long,Integer> cnt,Long prefix){
        if(root==null) return;
        prefix+=root.val;
        ans+=cnt.getOrDefault(prefix-targetSum,0);
        cnt.merge(prefix,1,Integer::sum);
        dfs(root.left,cnt,prefix);
        dfs(root.right,cnt,prefix);
        cnt.merge(prefix,-1,Integer::sum);
    }
}

236. 二叉树的最近公共祖先 X-Chat

思路：最次返回当前节点。
如果当前节点 root == null，返回 null（空树无结果）；
如果当前节点 root == p 或 root == q，返回 root（找到目标节点，向上传递）；
递归遍历左子树，得到结果 left；递归遍历右子树，得到结果 right；
对 left 和 right 做核心判断：
情况 1：left != null 且 right != null → 当前节点就是最近公共祖先（p、q 分别在当前节点的左右子树）；
情况 2：left != null 且 right == null → 返回left（p、q 都在左子树，继续向上传递）；
情况 3：left == null 且 right != null → 返回right（p、q 都在右子树，继续向上传递）；
情况 4：left == null 且 right == null → 返回null（当前子树无目标节点）。

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

124. 二叉树中的最大路径和

思路：最大路径和是一条路径上的和，每一个节点都可能成为路径的 “顶点”（即路径以该节点为中心，向左右子树延伸）。
通过后序递归遍历，返回当前节点的最大有效和（注意：这个地方返回的最长和是要么左要么右，因为要满足向上回溯的路径连续性，只需要向上返回当前节点下的最优，但如果左右都小于0直接返回0）。且每次每个节点要再计算当前节点作为 “顶点” 时的路径和（根节点值 + 左子树有效贡献 + 右子树有效贡献），并更新全局最大值。

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    int dfs(TreeNode root) {
        if (root == null)
            return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        int curr_path = root.val+l+r;
        max = Math.max(Math.max(curr_path,curr),max);
        return Math.max(0,Math.max(l,r)+root.val);
    }
}

四、图论

200. 岛屿数量

思路：以第一个（0,0）为入口直接遍历图。若发现一个'1'，则是一个新的岛屿，ans++，然后递归的把这个岛屿（上下左右遍历为'1'的格子）赋值为'2'，表示这个岛屿已经被发现过了（停止遍历当前岛屿条件：整周围只有'0'和'2'了）。

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

994. 腐烂的橘子X-Chat

思路：因为每一分钟，所有腐烂的橘子要同时感染其周围的，所以要按照一个批次的烂橘子进行感染。先初始记录存在的烂橘子list。以这个list去做层序遍历，一次遍历就是一分钟，每次遍历把感染的新的加入到新的list，这批完后老的list就不要了，改为用新的list去遍历。
注意：要记录感染的个数和原新鲜的个数，一致才表示全部感染了。此外注意停止感染的边界（下标越界或者不是新鲜橘子）
错误原因（未思考到）：1、主循环枚举四个方向，子方法判断是否成功；2、四个方向要修改了，minutes才能加一

class Solution {
    public int orangesRotting(int[][] grid) {
        int fresh=0,badNum=0;
        int ans=0;
        List<int[]> bad =  new ArrayList();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1) fresh++;
                if(grid[i][j]==2) bad.add(new int[]{i,j});
            }
        }
        // 层序遍历，一次就是一分钟
        while(bad.size()!=0){
            List<int[]> tmp =  new ArrayList();
            for(int[] curr:bad){
                makeBad(grid,curr[0],curr[1]-1,tmp);
                makeBad(grid,curr[0],curr[1]+1,tmp);
                makeBad(grid,curr[0]-1,curr[1],tmp);
                makeBad(grid,curr[0]+1,curr[1],tmp);
            }
            bad=tmp;
            if(tmp.size()!=0) ans++;
            // 新的坏果，之前的不用了
            badNum+=bad.size();

        }
        return fresh==badNum?ans:-1;
    }
    void makeBad(int[][] grid,int i,int j,List<int[]> tmp){
        // 是否还在格子内，且当前是否有好橘子
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!=1){
            return;
        }
        grid[i][j]=2;
        tmp.add(new int[]{i,j});
    }
}

207. 课程表XXX-Chat

208. 实现 Trie (前缀树)XX-Chat

思路：用一个26路的树结构（a-z）来记录存入的值。
Node[] child = new Node[26]; //只是数组，内容是空的
在存入时注意，未使用过的子节点为空，需要手动初始化。且在使用时要以上一层.child[i]来访问当前层，若为空，进行初始化。
此外用一个字段记录当前节点是否为一个单词的结束位置。因为不同单词会重复，有可能长的包含短的如app和apple。

五、回溯

回溯要点：

当前操作：确定当前要做的操作是什么
子问题：构造当前节点之后的部分
下一个问题
结束条件

46. 全排列X-Chat

思路：需要递归的去找所有的可能，用一个index记录到了哪个下标。
当前操作：确定当前位置可能的数（index）。当前的值可以是和其本身以及其之后的值sawp。
for（int i=index;i<nums.length;i++）
下一个操作：对当前位置之后的数进行排列（index+1）
结束条件：当index为数组长度（递归到数组最后），就将当前数组为一个结果加入返回值列表。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        back(nums,0,ans);
        return ans;
    }
    void back(int[] nums,int index,List<List<Integer>> ans){
        if(index==nums.length){
            List<Integer> tmp = new ArrayList();
            for(int i=0;i<nums.length;i++){
                tmp.add(nums[i]);
            }
            ans.add(tmp);
        }
        for(int i=index;i<nums.length;i++){
            swap(nums,i,index);
            back(nums,index+1,ans);
            swap(nums,i,index);
        }
    }
}

78. 子集

思路：安装回溯要素考虑。
当前操作：选还是不选当前值加入此趟结果
下一个操作：将当前位置之后的进行同样的回溯
停止结果：是否到数组最后

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        back(nums,0,ans,new ArrayList<Integer>());
        return ans;
    }
    void back(int[] nums,int index,List<List<Integer>> ans,List<Integer> path){
        if(index==nums.length){
            ans.add(new ArrayList(path));
            return;
        }
        path.add(nums[index]);
        back(nums,index+1,ans,path);
        path.removeLast();
        back(nums,index+1,ans,path);        
    }
}

17. 电话号码的字母组合

思路：回溯的去枚举，用一个path记录当前index按钮下选择了哪个字母，然后回溯index+1后的，用完后移除path。
当前操作：选当前index的哪个字母。每个都有可能，使用for枚举。当前用完后移除。
下一个操作：将当前位置之后的进行同样的回溯
停止结果：是否到数组最后

class Solution {
   char[][] nums = new char[][] { {}, {}, { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' },
            { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList();
        List<Character> path = new ArrayList();
        back(digits.toCharArray(),0,ans,path);
        return ans;
    }
    void back(char[] digits,int index,List<String> ans,List<Character> path){
        if(index==digits.length){
            StringBuilder tmp = new StringBuilder();
            for(int i=0;i<path.size();i++){
                tmp.append(path.get(i));
            }
            ans.add(tmp.toString());
            return;
        }
        char curr = digits[index];
        // 选哪一个
        for(int i=0;i<nums[curr-'0'].length;i++){
            path.add(nums[curr-'0'][i]);
            back(digits,index+1,ans,path);
            path.removeLast();
        }
    }
}

39. 组合总和

思路：回溯的去枚举，用一个path记录当前index按钮是否选择当前数字，sum记录当前的路径的数的和，然后回溯index+1后的，用完后移除path。
当前操作：选当前的数字加入，因为可以重复（2,2,2）= 6，以当前下标，不用i+1进行后续回溯，结束条件为sum>target或sum=target或i==candidate.length。
下一个操作：将当前位置的进行同样的回溯
停止结果：是否到数组最后，sum是否大于target。sum是否等于target

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans=new ArrayList();
        List<Integer> path = new ArrayList();
        back(candidates,0,target,0,ans,path);
        return ans;
    }
    void back(int[] candidates,int index,int target,int  sum,List<List<Integer>> ans,List<Integer> path){
        if(sum==target){
            ans.add(new ArrayList(path));
            return;
        }
        if(index==candidates.length||sum>target){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            sum+=candidates[i];
            path.add(candidates[i]);
            back(candidates,i,target,sum,ans,path);
            path.removeLast();
            sum-=candidates[i];
        }
    }
}

22. 括号生成X-Chat

思路：回溯的去找可能的组合。l和r记录当前左右括号个数。选l（左括号）还是r（右括号），只要l<n，l都可以选。只要r<l,r都可以选
当前操作：当前选l还是r
下一个操作：将当前位置的进行同样的回溯
停止结果：l和r是否到n/2了

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

    void trace(int n,int l,int r,List<String> ans,List<Character> path){
        if(l+r==n*2){
            StringBuilder tmp = new StringBuilder();
            for(int i=0;i<path.size();i++){
                tmp.append(path.get(i));
            }
            ans.add(tmp.toString());
        }
        // 选l还是r，只要l<n，l都可以选。只要r<l,r都可以选
        if(l<n){
            path.add('(');
            trace(n,l+1,r,ans,path);
            path.removeLast();
        }
        if(r<l){
            path.add(')');
            trace(n,l,r+1,ans,path);
            path.removeLast();
        }
    }
}

79. 单词搜索

思路：网格中每一个点都有可能是起点。遍历网格，从每个点作为起点开始trace回溯判断是否是word。
当前操作：当前网格位置（i,j）是否与word中的index一样。若当前一样，就进行网格上下左右下一个元素对比index++。子回溯上下左右有一个满足即可。当前网格位置用完后标记为已使用，用完后撤回标记。
下一个操作：将当前位置的word位置index+1后的进行同样的回溯
停止结果：index==word.length或i,j超限或当前网格元素与word的index位置元素不一样

class Solution {
    boolean ans =false;
    public boolean exist(char[][] board, String word) {
                // 为了方便，直接用数组代替哈希表
        int[] cnt = new int[128];
        for (char[] row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }

        // 优化一
        char[] w = word.toCharArray();
        int[] wordCnt = new int[128];
        for (char c : w) {
            if (++wordCnt[c] > cnt[c]) {
                return false;
            }
        }
        // 优化二
        if (cnt[w[w.length - 1]] < cnt[w[0]]) {
            w = new StringBuilder(word).reverse().toString().toCharArray();
        }

        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(trace(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean trace(char[][] board,int i,int j,String word,int index){
        if(i<0||j<0||i>=board.length||j>=board[0].length){
            return false;
        }
        if(board[i][j]!=word.charAt(index)){
            return false;
        }
        if(index==word.length()-1){
            return true;
        }
        board[i][j]=0;
        boolean find1 = trace(board,i+1,j,word,index+1);
        boolean find2 = trace(board,i-1,j,word,index+1);
        boolean find3 = trace(board,i,j+1,word,index+1);
        boolean find4 = trace(board,i,j-1,word,index+1);
        board[i][j] = word.charAt(index);
        return find1||find2||find3||find4;

    }
}

131. 分割回文串

思路：从下标start=0开始，枚举每个区间for(int end=start;...)；若当前区间【start,end】为回文串，则对end+1的串进行子回溯。
当前操作：从start的位置开始，枚举start->length长度，看【start,end】是否为回文串。
下一个操作：若当前【start,end】是回文串，将当前位置的end+1后的进行同样的回溯
停止结果：strat==length

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList();
        List<String> path  = new ArrayList();
        trace(s,0,ans,path);
        return ans;
    }   
    void trace(String s,int start,List<List<String>> ans,List<String> path){
        if(start==s.length()){
            ans.add(new ArrayList(path));
        }
        for(int end=start;end<s.length();end++){
            if(para(s,start,end)){
                path.add(s.substring(start,end+1));
                trace(s,end+1,ans,path);
                path.removeLast();
            }
        }
    }
}

51. N 皇后X-Chat

思路：每一行，枚举每一列的元素看是否能当Queen。要满足 1.与之前的不在同一列用boolean数组记忆之前Queen在的列位置boolean[] col。2.不在同一正反对角线(如何判断？),用两个boolean[n*2-1] 记录对应的正反对角线是否有Queen在。3.用一个int[] queen记录每行，对应的Queen的下标。
当前操作：从当前行的第一列开始枚举，看当前位置是否可以放Queen，若可以就进行下一行（row+1）同样的操作。
下一个操作：若当前【start,end】是回文串，将当前位置的end+1后的进行同样的回溯
停止结果：row==n

class Solution {
    public List<List<String>> solveNQueens(int n) {
      List<List<String>> ans = new ArrayList();
      List<String> path = new ArrayList();
      //1.记录是否在正反对角线是否有皇后了，互相攻击。
      boolean[] dial1 = new boolean[n*2-1],dial2=new boolean[n*2-1]; 
      //2.记录是否在某列已经有皇后了   
      boolean[] col = new boolean[n];
      //记录每行的哪一列为Q，也可用于判断同列是否攻击
      int[] queens = new int[n];  
      trace(n,0,ans,queens,dial1,dial2,col);  
      return ans; 
    }
    void trace(int n,int row,List<List<String>> ans,int[] queens,boolean[] dial1,boolean[] dial2,boolean[] col){
        if(row==n){
            List<String> tmp = new ArrayList();
            // 遍历每行进行构造，构造的是每一行
            for(int i=0;i<n;i++){
                char[] curr = new char[n];
                Arrays.fill(curr,'.');
                curr[queens[i]]='Q';
                tmp.add(new String(curr));
            }
            ans.add(tmp);
        }
        for(int i=0;i<n;i++){
            if(!col[i]&&!dial1[row+i]&&!dial2[row-i+n-1]){
                queens[row] = i;
                col[i]=dial1[row+i]=dial2[row-i+n-1]=true;
                trace(n,row+1,ans,queens,dial1,dial2,col);
                col[i]=dial1[row+i]=dial2[row-i+n-1]=false;
            }
        }
    }
}

六、二分查找

35. 搜索插入位置

思路：其实就是通过二分找到第一个大于等于target的位置。注意：就算找到了也不要return。

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

74. 搜索二维矩阵

思路：遍历即可

34. 在排序数组中查找元素的第一个和最后一个位置

思路：只需要去找第一个大于等于该元素，以及第一个大于等于该元素加一的即可。
注意，找到后，先看“第一个大于等于该元素”是否存在。
l==nums.length --> 所有元素全部小于该元素
nums[l]!=nums.length --> 所有元素都不等于该元素
l==0 --> 所有元素全部大于该元素

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = loewe(nums,0,nums.length-1,target);
        int r = loewe(nums,0,nums.length-1,target+1);
        if(nums.length==l||nums[l]!=target) return new int[]{-1,-1};
        return new int[]{l,r-1};
    }
    int loewe(int[] nums,int i,int j,int target){
        int mid=0;
        while(i<=j){
            mid=(j-i)/2+i;
            if(nums[mid]<target){
                i=mid+1;
            }else {
                j=mid-1;
            }
        }
        return i;
    }
}

153. 寻找旋转排序数组中的最小值X-Chat

思路：由于这个数组是旋转的【4,5,6,7,0,1,2】，不是强有序，但是数组被最后一个数把数组切割为了两分，一半比最后一个大，一半比最后一个小。
因此最小值就是第一个小于等于 2 的元素（即 0）。用二分查找不断缩小范围：若 nums[mid] > 最后一个数，说明在左半，往右找；否则往左找。最后 left 指向的就是最小值。
旋转后的数组以最后一个数为基准，可以映射成一个布尔数组 [true, true, true, true, false, false, false]（true 表示大于最后一个数，false 表示小于等于最后一个数）。
本题就是要找第一个 false 的位置，也就是最小值。用二分查找寻找这个边界即可。

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

33. 搜索旋转排序数组

思路：基于153，找到旋转排序数组的中点后，看target在哪个部分，然后使用二分查找找即可。

class Solution {
    public int search(int[] nums, int target) {
        int split = findMin(nums);
        int ans=-1;
        if(target>nums[nums.length-1]){
            ans = lowe(nums,0,split-1,target);
        }else{
            ans = lowe(nums,split,nums.length-1,target);
        }
        return ans;
    }

    int lowe(int[] nums,int l,int r,int target) {
        int mid=0;
        while(l<=r){
            mid=l+(r-l)/2;
            if(nums[mid]<target){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        if(nums.length==l||nums[l]!=target) return -1;
        return l;
    }

    int findMin(int[] nums) {
        int mid=0,l=0,r=nums.length;
        while(l<=r){
            mid=l+(r-l)/2;
            if(nums[mid]>nums[nums.length-1]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
}

七、栈、堆

单调栈注意入口和出口保持一致，要么getLast+removeLast要么getFirst+removeFirst

20. 有效的括号

思路：就用一个栈去匹配，若是左括号，就加入；若是右括号就进行匹配若不匹配就直接返回false。注意循环条件用下标。另外，每次取stack最后一个时注意判空。

class Solution {
    public boolean isValid(String s) {
        char[] cs = s.toCharArray();
        ArrayDeque<Character> stack = new ArrayDeque();
        stack.addLast(cs[0]);
        int i=1;
        while(i<s.length()){
            char curr=cs[i];
            if(curr=='[' || curr=='{' || curr=='('){
                stack.addLast(curr);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char last = stack.getLast();
                switch(curr){
                    case ')':
                        if(last=='(') stack.removeLast();
                        else return false;
                        break;
                    case ']':
                        if(last=='[') stack.removeLast();
                        else return false;
                        break;                    
                    
                    case '}':
                        if(last=='{') stack.removeLast();
                        else return false;
                        break;
                }
            }
            i++;
        }
        return stack.isEmpty();
    }
}

155. 最小栈X-Chat

思路：最小栈，即一个数据结构能维护存在数据的最小值。
用一个链表，链表每个节点记录它及其后面的节点的最小值（每次插入这个节点时比一下之前最小和当前val即可）。
使用头插法，这样每次删除和插入时都操作头结点。

class MinStack {
    class Node{
        int minVal;
        int val;
        Node next;
    }
    Node head; 

    public void push(int val) {
        Node curr = new Node();
        curr.val=val;
        curr.minVal=head==null?val:Math.min(val,head.minVal);
        curr.next=head;
        head=curr;
    }

    public void pop() {
        head=head.next;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.minVal;
    }
}

394. 字符串解码

思路：本题主要是遍历这个字符串。有四种情况：1.数字、2.字母、3.'[' 、4.']'。用一个全局的index表示当前到哪儿了。然后进行递归。
1.若是数字，就循环的进行处理，记录一个k，然后因为从左是从高位开始，每次循环就把上一次的k*10；
2.若是字母，直接append
3.若是'['，进入递归，把内部解析后返回回来，然后根据k，用repeat(string,int)，进行重复叠加
3.若是']'，表示递归应该结束了。

class Solution {
    public String decodeString(String s) {
        char[] cs = s.toCharArray();
        return decode(cs);
    }
    int index=0;
    String decode(char[] cs){
        int k=0;
        StringBuilder ans = new StringBuilder();
        while(index<cs.length){
            char curr = cs[index];
            index++;
            if(Character.isDigit(curr)){
                k  = k*10+curr-'0';
            }else if(Character.isLetter(curr)){
                ans.append(curr);
            }else if(curr=='['){
                String tmp = decode(cs);
                ans.repeat(tmp,k);
                // 把k置为0
                k=0;
            }
            // 为']'时退出
            else{
                break;
            }
        }
        return ans.toString();
    }

739. 每日温度

思路：从后向前，维护一个最大值栈。当前位置一直比，删除栈里面比他小的，最后若栈空了，则他的后面是没有比他大的，ans=0,反之，ans=栈的last - index

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans =new int[temperatures.length];
        ArrayDeque<Integer> s = new ArrayDeque();
        int index = temperatures.length-1;
        s.addLast(index--);
        while(index>=0){
            while(!s.isEmpty()&&temperatures[s.getLast()]<=temperatures[index]){
                 s.removeLast();
            }
            ans[index] = s.isEmpty()?0:s.getLast()-index;
            s.addLast(index);
            index--;
        }
        return ans;
    }
}

84. 柱状图中最大的矩形X-Chat

思路：分别找到当前柱子前后距离最近的比他矮的柱子，比当前柱子低或一样高的即可。
// 因为要矩形面积，比当前高的没意义，只有宽才有意义。把每个柱子能构成的最大矩形面积都找到即可。
// 注意若左或右都比当前柱子高，应该是-1或length

class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans=0;
        ArrayDeque<Integer> post = new ArrayDeque();
        ArrayDeque<Integer> pre = new ArrayDeque();
        int[] pres = new int[heights.length],posts = new int[heights.length];
        int i = heights.length-1;
        posts[i] = heights.length;
        post.addLast(i--);
        while(i>=0){
            while(!post.isEmpty()&&heights[post.getLast()]>=heights[i]){
                post.removeLast();
            }
            //空了表示后面的全部比当前柱子高
            posts[i] = post.isEmpty()?heights.length:post.getLast();
            post.addLast(i);
            i--;
        }
        i = 0;
        pres[i]=-1;
        pre.addLast(i++);
        while(i<heights.length){
            while(!pre.isEmpty()&&heights[pre.getLast()]>=heights[i]){
                pre.removeLast
            }
            //空了表示前面的全部比当前柱子高
            pres[i] = pre.isEmpty()?-1:pre.getLast();
            pre.addLast(i);
            i++;
        }
        for( i=0;i<heights.length;i++){
            ans=Math.max(ans,(posts[i]-pres[i]-1)*heights[i]);
        }
        return ans;
    }

}

215. 数组中的第K个最大元素X-Chat

思路：快速排序。快速排序的逻辑是：随机选择一个元素，把这个元素放到他应该在的位置；然后以这个元素为partition将数组分割为左右为比他大/小的，然后递归进行。故找第k个用快速排序不用吧数组全部排序完，就可以找到。注意，第k个转换到下标的话要用nums.length-k。
错误原因：1、考虑初始left指针时不要l，而是l+1；2、最后递归排序时只用根据左右选择k在的位置即可

class Solution {
    int ans=0;
    public int findKthLargest(int[] nums, int k) {
        quick(nums,0,nums.length-1,k);
        return ans;
    }
    void quick(int[] nums,int l,int r,int k){
        if(l>r){
            // if(l==r)    ans=nums[l];
            return;
        }
        int left =  l+1,right=r,pivot = nums[l];
        while(left<=right){
            while(left<=right&&nums[left]<pivot){
                left++;
            }
            while(left<=right&&nums[right]>pivot){
                right--;
            }
            if(left<=right){
                int tmp=nums[left];
                nums[left]=nums[right];
                nums[right]=tmp;
                left++;right--;
            }
        }
        int  tmp = nums[l];
        nums[l]=nums[right];
        nums[right]=pivot;
        int tarfet=nums.length-k;
        if(tarfet==right){
            ans=pivot;
            return;
        }else if(tarfet<right){
            quick(nums,l,right-1,k);
        }else{
            quick(nums,right+1,r,k);
        }
    }
   
}

347. 前 K 个高频元素

思路：将出现频率相同的元素按组统计到一起，然后遍历前k个即可。
先用map统计每个元素出现的评率，然后用列表数组（List[] buckets= new List[Maxtimes]）来将出现频率相同的元素放到同一个LIst下，Maxtimes就是频率最高的数字，下标就表示这个LIst里面的数出现的评率。最后倒着遍历即可。
关键：1、用map统计【元素-相同元素List】；2、用一个List数组，把上一步map元素的个数作为下标，对应下标里面放元素Lｉst；２、倒着遍历List数组，把里面的LIst内容拿出来，前Ｋ个就是答案

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1、先构建<元素->相同元素集合>
        HashMap<Integer,List<Integer>> cnt = new HashMap();
        for(int i=0;i<nums.length;i++){
            cnt.computeIfAbsent(nums[i],_->new ArrayList()).add(nums[i]);
        }
        // 2、先算出最多的元素的个数，根据元素个数，对元素集合，放到List[] cntNums数组，个数作为下标，对应的集合放个数相同的元素。
        int maxNum=0;
        for(int curr:cnt.keySet()){
            maxNum=Math.max(maxNum,cnt.get(curr).size());
        }
        List[] cntNums = new ArrayList[maxNum+1];
        // 初始化cntNums里面的链表
        for(int i=0;i<cntNums.length;i++){
            cntNums[i] = new ArrayList();
        }
        // 开始放
        for(int curr:cnt.keySet()){
            cntNums[cnt.get(curr).size()].add(curr);
        }
        // 3、统计前K个
        int currK=0;
        int[] ans = new int[k];
        for(int i=cntNums.length-1;i>=0;i--){
            if(currK==k) break;
            for(int j=0;j<cntNums[i].size();j++){
                ans[currK++]=(int)cntNums[i].get(j);
            }
        }
        return ans;
    }
}

八、贪心算法

121. 买卖股票的最佳时机

思路：遍历数组，然后需要比较选出然后出现过的最小的值，然后每次当前值-最小值比较即可。

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

55. 跳跃游戏

思路：ToMax记录能到的最远的下标
1、初始化时，能到的下标就是nums[0]+0
2、到了新的位置，先判断 toMax < i，确认能否到这个位置
2、后面遍历数组，能到的就是nums[i]+i

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

45. 跳跃游戏 IIX-Chat

思路：和上一题类似，需要在遍历时记录能到的最远位置。
但是区别是。
判断改为若上一次移动的位置到了，移动次数+1，然后把新的能移动到的最远位置改为新的。
且不用遍历到i<nums.length，到i<nums.length-1即可，因为到了最后一个就不用算次数了。
错误原因：不熟练

class Solution {
    public int jump(int[] nums) {
        int curr=0,toMax=0,ans=0;
        for(int i=0;i<nums.length-1;i++){
            toMax=Math.max(toMax,i+nums[i]);
            if(curr==i){
                curr=toMax;
                ans++;
            }        
        }
        return ans;   
    }
}

763. 划分字母区间X-Chat

思路：用一个new int[26]数组，来记录s中每个字符在的最远的下标。
然后遍历数组，用一个值来维护能走的最远下标，
若end==i表示这个区间的这批数据只在这里了。就可以加入答案了。
错误原因：初始last要为-1

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

九、动态规划

70. 爬楼梯

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

118. 杨辉三角

1、第一层直接初始化
2、后面的就开始循环，每个节点=上一层同节点+上一层的前一个节点

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans =  new ArrayList();
        List<Integer> curr = new ArrayList();
        curr.add(1);
        ans.add(curr);
        for(int i=1;i<numRows;i++){
            curr = new ArrayList();
            curr.add(1);
            for(int j=1;j<i;j++){
                List<Integer> last = ans.get(i-1);
                curr.add(last.get(j-1)+last.get(j));
            }
            curr.add(1);
            ans.add(curr);
        }
        return ans;
    }
}

198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        int[] ans = new int[nums.length+2];
        ans[0]=0;ans[1]=0;
        for(int i=2;i<nums.length+2;i++){
            // 偷or不偷的最大值
            // 偷 = 上一家不偷，结果为上两家（ans[i-2]）与当前这家（nums[i-2]，为什么不是i，因为下标是以nums.length+2,所以，nums数组的下标要前移动2） 
            // 不偷 = 上一家偷，ans[i-1]
            ans[i] = Math.max(ans[i-1],nums[i-2]+ans[i-2]);
        }
        return ans[nums.length+1];
    }
}

279. 完全平方数XXX-Chat

外层循环的 i 表示当前考虑的完全平方数（i²），即枚举有哪些平方数可以用于组成 n。每遍历一个 i，就相当于向已有的方案中加入一种新的选择。
内层循环的 j 表示当前需要求解的目标数字，也就是尝试更新 f[j]。对于每一个 j，我们尝试加入一个当前的平方数 i²，看看是否能够让组成 j 所需的平方数数量变少。
状态转移：
f[j] = Math.min(f[j], f[j - i*i] + 1);
表示：
f[j]：不使用当前平方数 i² 时，组成 j 的最优方案；
f[j - i*i] + 1：使用一个 i² 后，剩余部分 j-i*i 的最优方案，再加上当前这个 i²。
两者取较小值，就是加入 i² 后组成 j 的最优方案。

class Solution {
    // 外层 i 枚举可使用的完全平方数；内层 j 遍历当前需要求解的数字，尝试加入一个 i²，判断是否能够减少组成 j 所需要的平方数数量，从而更新 f[j]。
    public int numSquares(int n) {
        int[] f= new int[n+1];
        Arrays.fill(f,0,f.length,Integer.MAX_VALUE);
        f[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                f[j] = Math.min(f[j],f[j-i*i]+1);
            }
        }
        return f[n];
    }
}

322. 零钱兑换XXX-Chat

同上，但是要加一个 if(f[i-coin]!=Integer.MAX_VALUE)，因为完全平方数至少有"1"去构成，但是硬币有可能没办法构成amount。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount+1];
        Arrays.fill(f,Integer.MAX_VALUE/2);
        f[0]=0;
        // 加入某个面额（coin）后，构成的个数是否能变
        for(int coin:coins){
            for(int i=coin;i<=amount;i++){
                // 若f[i-coin]==Integer.MAX_VALUE/2，表示，当前硬币没法构成此金额，直接加1。
                f[i] = Math.min(f[i],f[i-coin]+1);
            }
        }
       //当前硬币组成可能没法构成此金额
        return f[amount]>=Integer.MAX_VALUE/2?-1:f[amount];
    }
}

300. 最长递增子序列XXX-Chat

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] f=new int[nums.length];int ans=0;
        // 遍历nums，每次到i，计算i为最大值时，f[i] = 0-i区间的中最长严格递增子序列,所以最后要把++f[i]，把nums[i]算进去
         // f[i]记录了当前i的最长递增序列，若满足nums[j] < nums[i]，则nums[i]一定大于nums[j]及其之前的递增，一定可以递增续上，长度就是i之前的最长递增序列的长度加上自身1.
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    f[i]=Math.max(f[i],f[j]);
                }
            }
            // ++f[i],是因为，f[i]是第一次到，要把当前nums[i]算进去
            ans=Math.max(ans,++f[i]);

        }
        return ans;
    }
}

152. 乘积最大子数组XXX-Chat

class Solution {
    public int maxProduct(int[] nums) {
        // 1、前面乘积最小值（负数），在遇到当前nums[i]（负数）相乘后，可能变成最大值
        // 2、故要记录1、乘积最小值 2、乘积最大值 3、ans
        int minji=1,maxji=1,ans=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            int curr=maxji;
            // 3、注意，可能之前的最大最小积是0，但是到了新的数，应该加上与当前nums[i]进行比，不然要一直是0
            maxji=Math.max(Math.max(maxji*nums[i],minji*nums[i]),nums[i]);
            minji=Math.min(Math.min(curr*nums[i],minji*nums[i]),nums[i]);
            ans=Math.max(ans,maxji);
        }
        return ans;
    }
}

139. 单词拆分XXX-Chat

思路：
1、类似回溯的“分割回文串”，按index进行分块，将分块的string去匹配wordDict，若存在且递归dfs剩余串成功，就成功。
2、额外用一个mem[]数组去记录string下标，是否已经被算过了。
3、mem[index] = 0 表示：
从字符串下标 index 开始的后缀，无法被字典中的单词完整拆分。

class Solution {
    int[] mem = new int[301];
    public boolean wordBreak(String s, List<String> wordDict) {
          Arrays.fill(mem,-1);
        return dfs(s,0,new HashSet<String>(wordDict));
    }
    boolean dfs(String s,int index,HashSet subS){
        if(index==s.length()) return true;
        if(mem[index]!=-1) return mem[index]==1;
        for(int i=index;i<s.length();i++){
            if(subS.contains(s.substring(index,i+1))&&dfs(s,i+1,subS)){
                mem[i]=1;
                return true;
            }
        }
        mem[index]=0;
        return false;
    }
}

九一、多维动态规划

dfs数组，用mem数组维护已经做过的路

62. 不同路径XXX-Chat

class Solution {
    int[][] mem = new int[101][101];
    public int uniquePaths(int m, int n) {
        for (int[] row : mem) {
            Arrays.fill(row, -1); // -1 表示未计算
        }
        return dfs(0,0,m,n);
    }
    int dfs(int i,int j,int m,int n){
        if(i<0||j<0||j==n||i==m){
            return 0;
        }
        if(i==m-1&&j==n-1) return 1;        
        if(mem[i][j]!=-1) return mem[i][j];
        int path = dfs(i+1,j,m,n)+dfs(i,j+1,m,n);
        mem[i][j] = path;
        return path;
    }
}

64. 最小路径和XXX-Chat

同上

class Solution {
    int[][] mem = new int[201][201];
    int ans=Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        for(int[] curr:mem){
            Arrays.fill(curr,-1);
        }
        return dfs(0,0,grid);
    }
    int dfs(int i,int j,int[][] grid){
        if(i==grid.length||j==grid[0].length){
            return Integer.MAX_VALUE;
        }
        if(i==grid.length-1&&j==grid[0].length-1){
            return grid[i][j];
        }
        if(mem[i][j]!=-1) return mem[i][j];
        int maxPath = Math.min(dfs(i+1,j,grid),dfs(i,j+1,grid))+grid[i][j];
        mem[i][j]=maxPath;
        return maxPath;
    }
}

5. 最长回文子串

1、从头遍历数组，从当前节点双指针同时向外移动，判断是否是回文串
2、有两种情况，一种是对称（aba直接i=j从两方向走），一种是非对称（abba,i,j+1）先动一个

class Solution {
    public String longestPalindrome(String s) {
        char[] sc = s.toCharArray();
        int l, r, ansl = 0, ansr = 0, len = sc.length;
        for (int i = 0; i < len; i++) {
            l = i;
            r = i;
            while (l >= 0 && r < len && sc[l] == sc[r]) {
                l--;
                r++;
            }
            if (r - l > ansr - ansl) {
                ansl = l+1;
                ansr = r;
            }
        }
        for (int i = 0; i < sc.length - 1; i++) {
            l = i;
            r = i+1;
            while (l >= 0 && r < len && sc[l] == sc[r]) {
                l--;
                r++;
            }
            if (r - l > ansr - ansl) {
                ansl = l+1;
                ansr = r;
            }
        }
        return s.substring(ansl,ansr);
    }
}

1143. 最长公共子序列XXX-Chat

mem[i][j] 表示：从 t1[i] 和 t2[j] 开始，分别取两个字符串的后缀，能够得到的最长公共子序列长度。

class Solution {
    int[][] mem = new int[1001][1001];

    public int longestCommonSubsequence(String text1, String text2) {
        for(int[] curr:mem){
            Arrays.fill(curr,-1);
        }
        return dfs(text1.toCharArray(),text2.toCharArray(), 0, 0);
    }
    int dfs(char[] t1,char[] t2,int i, int j){
        if(i==t1.length||j==t2.length){
            return 0;
        }
        if(mem[i][j]!=-1) return mem[i][j];
        if(t1[i]==t2[j]) {
            mem[i][j] = dfs(t1,t2,i+1,j+1)+1;
            return mem[i][j];
        }
        mem[i][j] = Math.max(dfs(t1,t2,i+1,j),dfs(t1,t2,i,j+1));
        return mem[i][j];
    }
}

72. 编辑距离XXX-Chat

class Solution {
    private char[] s, t;
    private int[][] memo;

    public int minDistance(String text1, String text2) {
        s = text1.toCharArray();
        t = text2.toCharArray();
        int n = s.length;
        int m = t.length;
        memo = new int[n][m];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        // 边界情况：一个字符串已经处理完
        if (i == s.length) {
            return t.length - j; // 需要插入剩余的所有字符
        }
        if (j == t.length) {
            return s.length - i; // 需要删除剩余的所有字符
        }
        
        if (memo[i][j] != -1) return memo[i][j];
        
        if (s[i] == t[j]) {
            return memo[i][j] = dfs(i + 1, j + 1); // 字符匹配，继续
        }
        
        // 三种操作
        int insert = dfs(i, j + 1) + 1;     // 插入 t[j]
        int delete = dfs(i + 1, j) + 1;     // 删除 s[i]
        int replace = dfs(i + 1, j + 1) + 1; // 替换 s[i] 为 t[j]
        
        return memo[i][j] = Math.min(Math.min(insert, delete), replace);
    }
}

十、技巧

136. 只出现一次的数字

思路：利用异或运算 a⊕a=0 的性质，我们可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素。其中用到了异或运算的交换律 a⊕b=b⊕a，以及结合律 (a⊕b)⊕c=a⊕(b⊕c)

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

169. 多数元素

思路：打擂台，。记录一个数的个数，初始第一个元素。若相等cnt++，不等就cnt--。cnt为0了就换元素，并且cnt置为1。最后存在擂台上的元素为结果。

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

75. 颜色分类

思路：三指针遍历即可

class Solution {
    public void sortColors(int[] nums) {
        int  red=0,white=0,blue=nums.length-1;
        while(white<=blue){
            if(nums[white]==0){
                swap(nums,white,red);
                red++;white++;
            }else if(nums[white]==1){
                white++;
            }else{
                swap(nums,white,blue);
                blue--;
            }
        }
    }
}

287. 寻找重复数

思路：这是数组里面寻找重复数，可以把其看做找循环链表的入口节点。i = num[num[i]]是快节点，i=num[i]是慢节点。
为什么可以这么做？因为给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）。故通过num[num[i]]去访问一定是可以访问到的。

class Solution {
    public int findDuplicate(int[] nums) {
      int i=0,j=0;
      i=nums[i];j=nums[nums[j]];
        while(i!=j){
            i=nums[i];
            j=nums[nums[j]];
        }
        int s=0;
        while(s!=i){
            s=nums[s];
            i=nums[i];
        }
        return i;
    }
}

31. 下一个排列X-Chat

思路：这道题主要是要找到第一个拐点。
1、从右往左找到第一个“升序点”（即 nums[i] < nums[i+1]），因为第一个升序点的右边一定是是递减的，已经是最大排列；
2、然后在 i 的右侧递减区间中，从右往左找到第一个比 nums[i] 大的数，与其交换，让当前位尽量“小幅度变大”；
3、最后把 i 右边的部分整体反转，使其从递减变为递增（最大变成最小了），从而得到刚好比当前排列大的最小字典序排列。

// 13542
class Solution {
    public void nextPermutation(int[] nums) {
        int i=0;
        // 1.找到第一个nums[i-1]>nums[i]的点，可以最小的变大
        for( i=nums.length-2;i>=0;i--){
            // 有不符合排序的点。退出
            if(nums[i]<nums[i+1]){
                break;
            }
        }
        // 2.找到i这个拐点，其右边一定是递减的。不然i不会是第一个拐点
        if(i>=0){
            // 若有这个拐点，去找第一个最近的拐点,把大的换到前面去
            int j=nums.length-1;
            while(nums[i]>=nums[j]){
                j--;
            }
            swap(nums,i,j);
        }
        // 3.若不满足第一步的有大小拐点，则i=-1
        reverse(nums,i+1,nums.length-1);
    }
        private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }

}

287. 寻找重复数X-Chat

把其当做是一个有环链表，因为数字在[1,n]的范围

// 代码逻辑同 142. 环形链表 II
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0; // 0 一定不在环上，适合作为起点
        int fast = 0;
        while (true) {
            slow = nums[slow]; // 等价于 slow = slow.next
            fast = nums[nums[fast]]; // 等价于 fast = fast.next.next
            if (fast == slow) { // 快慢指针移动到同一个节点
                break;
            }
        }

        int head = 0; // 再用一个指针，从起点出发
        while (slow != head) {
            slow = nums[slow];
            head = nums[head];
        }
        return slow; // 入环口即重复元素
    }
}

十一、排序

冒泡排序

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }
    void sort(int[] nums,int l,int r){
       for(int i=0;i<nums.length;i++){
            for(int j=1;j<nums.length-i;j++){
                if(nums[j]<nums[j-1]){
                    int tmp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = tmp;
                }
            }
       }
    }
}

快速排序

思路：通过分治的思想，先把数组以pivot分割为左小于，右大于的数组，然后递归的再把左右进行相同操作实现排序。

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }
    void sort(int[] nums,int l,int r){
        if(l>=r) return;
        // 随机pivot，效率更好
        int index = l+(int)(Math.random()*(r-l+1));
        int tmp = nums[l];
        nums[l] = nums[index];
        nums[index] = tmp;

        int left=l+1,right=r,pivot = nums[l];
        while(left<=right){
            while(left<=right&&pivot>nums[left]){
                left++;
            }
            while(left<=right&&pivot<nums[right]){
                right--;
            }
            if(left<=right){
                tmp = nums[left];
                nums[left]=nums[right];
                nums[right] = tmp;
                left++;right--;
            }
        }
        nums[l]=nums[right];
        nums[right]=pivot;
        sort(nums,l,right-1);
        sort(nums,right+1,r);
    }
}