Hot 100笔记

源于力扣

1-10

1.两数之和

class Solution {
    //思路key存余值，v存索引，比如2 找不到，存7，下次7就找到
       public static int[] twoSum(int[] nums, int target) {
            int re [] = new int [2];
            Map<Integer,Integer>  map = new HashMap<>();
            for(int i = 0;i<nums.length;i++){
                if(!map.containsKey(nums[i])){
                    map.put(target - nums[i],i);
                }else{
                    // return new int[]{i, j};用这种可以直接创建数组固定
                    re[0] = i;
                    re[1] = map.get(nums[i]);
                    return re;
                }
            }
            return re ; 
        }
}

2.字母异位词分组

class Solution {
    //    思路：排序就能判断是不是一个字符串,用map key是排序后，value是原str里面的数组
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String newStr = new String(charArray);//这里不能用toString
            if (hm.containsKey(newStr)) {
                hm.get(newStr).add(str);
            } else {
                List<String> fenlei = new ArrayList<String>();
                fenlei.add(str);
                hm.put(newStr, fenlei);
            }
        }
        List<List<String>> re = new ArrayList<List<String>>();
        for(Map.Entry<String, List<String>> Entry : hm.entrySet()){
                re.add(Entry.getValue());
            }
        return re;
    }
}

3.最长连续序列

public class Code3 {
//   每次去找是否存在x - 1 ，直到不存在那么这个x就是某个序列的最小值
//   Set进行去重,遍历找到每个序列的最小值,然后反向找长度
    public int longestConsecutive(int[] nums) {
        if (nums.length < 1) return nums.length;
        int ans = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        for (Integer integer : set) {
            if (set.contains(integer - 1)) {
                continue;
            }
//            找到某个序列的最小值
            int y = integer;
            while (set.contains(y)) {
                y++;
            }
//           找到某个序列的最大值此时是y-1   因此距离（y - 1） - integer + 1
            ans = Math.max(ans, y - integer);
//
        }
        return ans;
    }
}
​

4.移动零

public class Code4 {
//    找出所有不等于0的个数，然后直接替换，然后剩下补0
    public void moveZeroes(int[] nums) {
       int count = 0;
       for (int i = 0; i < nums.length;i++){
           if (nums[i] != 0 ) {
               nums[count++] = nums[i];
           }
       }
       for (int i = count; i < nums.length;i++){
           nums[i] = 0;
       }
    }
}

5.盛最多水的容器

public class Code5 {
    public int maxArea(int[] height) {
//头尾指针，优先移动小的，因为面积想要找更大只能移动最小值
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            ans = Math.max(ans,(r-l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

6.三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //排序加双指针加去指针去重
        Arrays.sort(nums);
        ArrayList<List<Integer>> re = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //第一次去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1, r = nums.length - 1;
            int target = -nums[i];
            while (l < r) {
                if (nums[l] + nums[r] == target) {
                    re.add(Arrays.asList(nums[l], nums[r], -target));
                    while (l < r && nums[l] == nums[l + 1])//先跳过重复元素再移动指针
                        l++;
                    while (l < r && nums[r] == nums[r - 1])
                        r--;
                    l++;
                    r--;
                    //还要去重

                } else if (nums[l] + nums[r] > target)
                    r--;
                else
                    l++;
            }
        }
        return re;
    }
}

7.接雨水

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        //前缀和，计算从左到右的和从右到左边的前缀和
        //注意遍历的边界，初始化，以及最大值替换都很恶心
        int[] prel = new int[n];
        int[] prer = new int[n];
        prel[0] = height[0];
        prer[n-1] = height[n - 1];
        int max = height[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(height[i], max);//更新max后赋值
            prel[i]=  max ;
        }
        max = height[n - 1];
        for (int i = n - 2; i > 0; i--) {
            max = Math.max(max, height[i]);
            prer[i]=  max ;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.max(Math.min(prel[i], prer[i]) - height[i],0);
        }
        return ans;
    }
}
    public int trap2(int[] height) {
//思路二：双指针，维护左侧和右侧的最大值，并且移动小的指针，
//       由是对于小的是确定的，另一边是未知的，但是可以提取出至少大于某个高度
        int n = height.length;
        if (n == 0) return 0;  // 处理空数组的情况
        int ans = 0;
        int leftMax = height[0];
        int rightMax = height[n - 1];
        int l = 1, r = n - 2;
        while (l <= r) {
            if (leftMax <= rightMax) {//处理左侧
                if (height[l] < leftMax) {//是否超过左边最大值
                    ans += leftMax - height[l];
                } else {//更新最大值
                    leftMax = height[l];
                }
                l++;
            } else {
                if (height[r] <= rightMax) {
                    ans += rightMax - height[r];
                } else {
                    rightMax = height[r];
                }
                r--;
            }
        }
        return ans;
    }

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

class Solution {
public int lengthOfLongestSubstring(String s) {
    // 用哈希去重，哈希表数组，set，map都可以，维护好左指针为上一个重复字符的下一位且不回退
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)){
                //跳到上一个出现的地方取start最大值不能让左指针回退
                if(start <= map.get(ch)+1){
                    start = map.get(ch)+1;
                }
            }
            max = Math.max(max,end - start + 1);
            map.put(ch,end);
        }
        return max;
    }
}

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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //定长滑动窗口，计数用两个数组，对比数组数量字母- ’a‘用equals
        int[] counts = new int[26];
        int[] countp = new int[26];
        List<Integer> result = new ArrayList<Integer>();
        if(s.length()< p.length()){
         return result;   
        }
        //初始化窗口计数
        for (int i = 0; i < p.length(); i++) {
            countp[p.charAt(i) - 'a']++;
        }
        //定长思路，初始化第一个窗口，先进后出
        for (int i = 0; i < p.length(); i++) {
            counts[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(countp, counts)) {
            result.add(0);
        }
        for (int i = p.length(); i < s.length(); i++) {
            counts[s.charAt(i) - 'a'] ++;
            counts[s.charAt(i - p.length()) - 'a'] --;
            if (Arrays.equals(countp, counts)) {
                result.add(i - p.length() +1 );//最终记录的是起始点！
            }
        }
        return result;
    }
}

10.和为K的子数组

public class Code10 {
    public int subarraySum(int[] nums, int k) {
//        思路一：由于是连续，可以直接两个for跑
//        思路二：区间和等于前缀和减去某个位置的前缀和
//        拓展：类似两数之和，利用哈希找对应的数，寻找a - b = k
        int res = 0, n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = nums[i] + pre[i];
        }
​
        for (int i = 0; i < pre.length; i++) {
            for (int j = i + 1; j < pre.length; j++) {
                if (pre[j] - pre[i] == k) {
                    res++;
                }
            }
        }
        return res;
    }
    public static int subarraySum2(int[] nums, int k) {
        int res = 0, n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = nums[i] + pre[i];
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
//        寻找a - b = k，就是相当于pre[j]-之前某个pre[i] = 成立
        map.put(0, 1);//要保证1 - 0  = 1 有零可以找到
        for (int i = 1; i < pre.length; i++) {
            if (map.containsKey(pre[i] - k)) {
                res += map.get(pre[i] - k);
            }
            map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
        }
        return res;
    }
}

11-20

11.滑动窗口最大值

public class Code10 {
    public int[] maxSlidingWindow(int[] nums, int k) {
// 单调队列：维护某个区间的最大值，存下标
// 思路是入的时候弹出比他小的，如果遍历值超过k范围就出， 弹的是坐标  
        int n = nums.length;
        int[] re = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
//            入
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.add(i);
//            出
            if (i- deque.getFirst() >=k) {   
                deque.removeFirst();
            }
//           记录答案
            if (i >= k-1 ) {
                re[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return re;
    }
}

12.最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        //双指针，覆盖函数自己写，维护两个单词计数数组
        int[] cntT = new int[128];
        int[] cntS = new int[128];
        int n = s.length();
        int m = t.length();
        if(n < m )return "";
        for (int i = 0; i < m; i++) {
            cntT[t.charAt(i)]++;
        }
        int l = 0,ll = -1 ,rr = n;
        for (int r = 0; r < n; r++) {
            cntS[s.charAt(r)]++;
            //如果当前字串覆盖大于覆盖串，就开始收缩
            while (isCovered(cntT,cntS)) {
                //由于返回需要记录字符串，这里需要记录最小的左右指针
                if(rr - ll  >r -l){
                    rr= r;
                    ll = l;
                }
                cntS[s.charAt(l)]--;
                l++;
            }
        }
        return ll == -1 ? "":s.substring(ll,rr+1);
    }

    private boolean isCovered(int[] cntT, int[] cntS) {
        for (int i = 0; i < 128; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}

13.最大子数组和

    public static int dp(int[] nums) {//[-2,1,-3,4,-1,2,1,-5,4]    [4,-1,2,1] 的和最大，输出6
// 思路动态规划：dp[i]表示0-i的最大子数组和，那么对于新的数，要么加入和dp[i-1],要么自己做头等于dp[i]
        int n = nums.length; //           -2,1,-2,4,3,5,6,1,5
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i];
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
    public static int preSum(int[] nums) {//[-2,1,-3,4,-1,2,1,-5,4]    [4,-1,2,1] 的和最大，输出6
// 思路前缀和：子数组和等于两个前缀和相减,维护当前前缀和减去当前最小前缀和
        int n = nums.length; //               -2,-1,-4,0,-1,1,2,-3,1   2-(-4) = 6
        int[] pre = new int[n];
        pre[0] = nums[0];
        int min = Math.min(pre[0], 0), res = pre[0];
        for (int i = 1; i < nums.length; i++) {
            pre[i] = pre[i - 1] + nums[i];
            res = Math.max(res, pre[i] - min);
            min = Math.min(min, pre[i]);
        }
        return res;
    }

14.合并区间

    public static int[][] merge(int[][] intervals) {
        //根据左端点排序，然后判断区间右端点是否大于下一个区间的左端点,需要熟悉api，排序，集合转数组，获取集合最后一个
        //先把第一个丢进结果数组，然后进一个判断一个
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
           if(merged.get(merged.size()-1)[1]>=intervals[i][0]){
               merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1],intervals[i][1]);
           }else{
               merged.add(intervals[i]);
           }
        }
        return merged.toArray(new int[merged.size()][]);
    }

15.轮转数组

​
public class Code14 {
    public static void rotate1(int[] nums, int k) {
        //复制数组，然后平移
        int n = nums.length;
        int[] tmp = Arrays.copyOf(nums, n);
        for (int i = 0; i < n; i++) {
            int i1 = (i + k) % n;
            nums[i1] = tmp[i];
        }
    }
    public static void rotate2(int[] nums, int k) {
        //构造一个反转的函数，传入对应的下表，那么变成对应的需要反转三次
        int n = nums.length;
        k %= n;
        rotate(nums, 0, n - 1);
        rotate(nums, 0, k - 1);
        rotate(nums, k, n - 1);
    }
    public static void rotate(int[] nums, int start, int end) {
        //7 6 5 4 3 2 1      567 1234
        int n = nums.length;
        while (start <= end && start >= 0) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}
​

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

class Solution {
    public static int[] productExceptSelf(int[] nums) {//1 2 3 4
//思路，用两个数组分别左前缀和和后缀和，然后可以计算0~x-1 和x+1~i 的乘积了
        int n = nums.length;
        int[] pre = new int[n];
        int[] post = new int[n];
        pre[0] = 1;//记得两个都要错位，得到的是左边的数据，也就是多一个无论第一个多少第一个都一次1 
        post[n-1] = 1;
        for (int i = 1; i < nums.length; i++) { // 1 1 2 6
            pre[i] = pre[i - 1] * nums[i-1];
            post[n - i - 1] = post[n - i] * nums[n -i];
        }
        int[] re = new int[n];
        for (int i = 0; i < re.length; i++) {
            re[i] = pre[i] * post[i];
        }
        return re;
    }
}

17.缺失的第一个正数

public class Code16 {
    public static int firstMissingPositive(int[] nums) {
// 思路：把他们交换到下标+1上，然后从头遍历就知道谁没来
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 交换 nums[i] 和 nums[nums[i] - 1] //就是当前值是否是当前值对应的下标位置
                int temp = nums[i];
                nums[i] = nums[nums[i] - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] - 1 != i) {
                return i + 1;//遍历数据
            }
        }
        return n + 1;
    }
}

18.螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
//先计算出下一个要走的位置，然后进行标记，用数组代表移动方向
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//不同下标可以表示转向
        List<Integer> ans = new ArrayList<>(m * n);
        int i = 0, j = 0, di = 0;
        for (int k = 0; k < m * n; k++) {
            ans.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;
//            计算下一个坐标
            int x = i + dirs[di][0];
            int y = j + dirs[di][1];
                    if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MAX_VALUE) {
                di = (di + 1) % 4; // 右转 90°
            }
            i +=dirs[di][0];
            j +=dirs[di][1];
        }
        return ans;
    }
}

19.旋转图像

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

20.搜索二维矩阵II

public class Code20 {
    public boolean searchMatrix(int[][] matrix, int target) {
//右上角作为一个二叉搜索树，或者二分，或者排除法
        int i = 0;
        int j = matrix[0].length - 1; // 从右上角开始
        while (j >= 0 && i < matrix.length) {
            if (matrix[i][j] == target) {
                return true; // 找到 target
            }
            if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
}

21-30

21.相交链表

public class Code21 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        快慢指针
        ListNode pa;
        ListNode pb;
        pa = headA;
        pb = headB;
        while(pa!=pb){
            pa = pa ==null? pb : pa.next;
            pb = pb ==null? pa : pb.next;
        }
        return pa;
    }
}

22.反转链表

public class Code22 {
    public ListNode reverseList(ListNode head) {
//        遍历赋值，然后需要存储前面的节点,把指针弄给前面的节点
        ListNode prev = null;
        ListNode cur;
        cur = head;
        while(cur != null) {
            ListNode node = cur.next;
            cur.next = prev;
            prev = cur;
            cur = node.next;
        }
    return prev;
    }
}

23.回文链表

public class Code23 {
    public boolean isPalindrome(ListNode head) {
//最快的思路就是数组+头尾指针
//新思路: 快慢指针获取中间，反转后面链表，然后反过来双边遍历
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next.next != null && slow.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow;
        ListNode prev = null;
        while (cur != null) {
            ListNode node = cur.next;
            cur.next = prev;
            prev = cur;
            cur = node;
        }
        ListNode p = head;
        while (p != null && prev != null) {
            if (p.val != prev.val) {
                return false;
            }
            p = p.next;
            prev = prev.next;
        }
        return true;
    }
}

24.环形链表

public class Solution {
    //快慢指针,两个从头跑的话注意while条件只要操作fast, 并且判断的是节点地址是否相同而不是值
       public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

25.环形链表II

public class Code25 {
    public ListNode detectCycle(ListNode head) {
// 快慢指针，然后在相遇地方让头节点和满节点一起跑相遇，证明方法可以去找
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null&&slow.next!=null){
            fast=fast.next.next;
            slow = slow.next;
            if(fast.val == slow.val){
                while(slow!=head){
                    slow = slow.next;
                    head = head.next;
                }
            }
        }
        return slow;
    }
}

26.合并两个有序链表

public class Code27 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//直接把两个数再加上进位数，注意更新记位数
        int carry = 0;
        ListNode node = new ListNode(0);//虚拟节点
        ListNode cur = node;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            node.next = new ListNode(sum % 10);
            node = node.next;
            carry = sum / 10;
            if( l1 != null){
                l1 = l1.next;
            }
            if( l2 != null){
                l2 = l2.next;
            }
        }
        return  cur.next;
    }
}

27.两数相加

public class Code27 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//直接把两个数再加上进位数，注意更新记位数
        int carry = 0;
        ListNode node = new ListNode(0);//虚拟节点
        ListNode cur = node;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            node.next = new ListNode(sum % 10);
            node = node.next;
            carry = sum / 10;
            if( l1 != null){
                l1 = l1.next;
            }
            if( l2 != null){
                l2 = l2.next;
            }
        }
        return  cur.next;
    }
}

28.删除链表的倒数第N个节点

public class Code28 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
//        可以反转链表，然后遍历计数删除
//        虚拟节点 + 快慢指针，让快指针先走n步，用虚拟节点可以遍历到达的地方直接next替换
        ListNode re = new ListNode(0);
        re.next = head;
        ListNode fast = re;
        ListNode slow = re;
        while(n-->0){
            fast = fast.next;
        }
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return re.next;
    }
}

29.两两交换链表中的节点

public class Code29 {
    public ListNode swapPairs(ListNode head) {
//        虚拟节点开始，并且每次都交换其后面的两个节点，需要三次操作
        ListNode re = new ListNode(0);
        re.next = head;
        ListNode cur = re;
        while (cur.next!=null && cur.next.next !=null) {
            ListNode tmp1 =  cur.next;
            ListNode tmp2 = cur.next.next;
            cur.next = tmp2;
            tmp1.next = tmp2.next;
            tmp2.next = tmp1;
            cur = cur.next.next;
        }
        return re.next;
    }
}

30.K个一组翻转链表

class Solution {
       public ListNode reverseKGroup(ListNode head, int k) {
// 可以分组，分组后进行反转的操作，恶心在细节处理
        if(head == null || k == 1){
            return head;
        }
        ListNode re = new ListNode(0);
        re.next = head;
        ListNode preGroup = re; //记录每一组的前缀节点
        while (true) {
            //确定好对应的开始和结束节点
            ListNode start = preGroup.next;
            ListNode end = start;
            for (int i = 0; i < k - 1 && end != null; i++) {
                    end = end.next;
            }
            if(end==null) break;  //不足k个节点就结束
            // 记录下一组的开始节点
            ListNode nextStart = end.next;
            end.next = null;//断开和一下组的链接
            preGroup.next = reverse(start);
               //反转后头节点是尾
            start.next = nextStart;
            preGroup = start;
        }
        return re.next;
    }
    //反转
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head, next;
        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

31-40

31.随机链表的复制

public class Code31 {
    HashMap<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        // 回溯创建，利用哈希表去记录当前节点和新节点的关系
        if(head ==null){
            return null;
        }
        if(!map.containsKey(head)){
            Node headNew = new Node(head.val);
            map.put(head,headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

32.排序链表

public class Code32 {
    public ListNode sortList(ListNode head) {
//  分治法归并排序，注意找中点（快慢指针），合并链表，递归操作
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = middleNode(head);
        mid = sortList(mid);
        head = sortList(head);
        return mergeTwoLists(head, mid);
    }
    //找中点，注意找到后要断开和后面的联系，引入一个slow的前驱节点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;//断开链接
        return slow;
    }
    //合并链表（哨兵机制）
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode re = new ListNode(0);
        ListNode cur = re;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return re.next;
    }
}

33.合并K个升序链表

public class Code33 {
    public ListNode mergeKLists(ListNode[] lists) {
//分治递归，类似归并排序，用m来多一个操作变量，注意ij的操作，然后合并链表
        return merges(lists, 0, lists.length);
    }
    private ListNode merges(ListNode[] list, int i, int j) {
        int m = j - i;
        if (m == 0) {
            return null;
        }
        if (m == 1) {
            return list[i];
        }
        ListNode left = merges(list, i, i + m / 2);
        ListNode right = merges(list, i + m / 2, j);
        return merge(left, right);
    }
    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode re = new ListNode(0);
        ListNode cur = re;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return re.next;
    }
}

34.LRU缓存

public class Code34 {
// 利用一个双向链表LinkedHashMap, Code34就是LRU对象,用好api，比如迭代器，remove等操作
    private final int capacity;
    private final Map<Integer, Integer> map = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        Integer remove = map.remove(key);
        if(remove ==null){
            return -1 ;
        }
        map.put(key, remove);
        return remove;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {//如果存在key，就去删除，然后添加到链表末尾
            map.remove(key);
            map.put(key,value);
            return;
        }else{//如果不存在，判断是否已经满了,获取队头
            if(map.size()==capacity){
                Integer first = map.keySet().iterator().next();//用迭代器去获取第一个元素
                map.remove(first);
            }
        }
        map.put(key,value);
    }
}

35.二叉树的中序遍历

public class Code35 {
    //递归中序遍历，dfs解决
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(res, root);
        return res;
    }
​
    public void dfs(List<Integer> res, TreeNode root) {
        if (root == null) return;
        dfs(res, root.left);
        res.add(root.val);
        dfs(res, root.right);
    }
}
​

36.二叉树的最大深度

public class Code36 {
    //注意节点空返回的是0，左右递归找最大值就行
    public int maxDepth(TreeNode root) {
        return max(root);
    }

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

37.翻转二叉树

public class Code37 {
    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;
    }
}

38.对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //递归判断其中有个是null，那么另一边不是null就是错的，递归是左左对右右，左右对右左
        return isSameTree(root.left,root.right);
    }
    public boolean isSameTree(TreeNode left, TreeNode right) {
        if (left==null|| right==null)   return left==right;
        if(left.val !=right.val){
            return false;
        }
        return isSameTree(left.left, right.right)&&isSameTree(right.left, left.right);
    }
}

39.二叉树的直径

public class Code39 {
    int ans;
// 怕绕住建议把最终答案写在成员变量里面
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans -2 ;//减去开始的两高度，其实也可以在下面返回-1
    }
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int lmax = dfs(root.left) + 1;
        int rmax = dfs(root.right) + 1;
        ans = Math.max(ans, lmax + rmax);//相当于左子树深度加右子树深度
        return Math.max(lmax, rmax);  //需要递归返回的是哪一边的树大用哪个
    }
}

40.二叉树的层次遍历

    public List<List<Integer>> levelOrder(TreeNode root) {
        //bfs借助队列Queue（Deque）的长度，对队列里面的弹出进行添加最终的答案，然后添加左右节点
        List<List<Integer>> re  = new ArrayList<>();
        if(root==null) return re;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int n = queue.size();
            while(n-->0){
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if(poll.left!= null) queue.add(poll.left);
                if(poll.right!= null) queue.add(poll.right);
            }
            re.add(list);
        }
        return re;
    }

41-50

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

class Code41 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length);
    }
​
    public static TreeNode dfs(int[] nums, int start, int end) {
        if (start == end) {
            return null;//如果相等就证明没有节点可以创建那就是null
        }
        int m = (start + end) / 2;
        TreeNode treeNode = new TreeNode(nums[m]);
        treeNode.left = dfs(nums, start, m);
        treeNode.right = dfs(nums, m + 1, end);
        return treeNode;
    }
}

42.验证二叉搜索树

class Solution {
    private long pre = Long.MIN_VALUE;//这里必须用long，因为int如果他是最大那么就找不到比他大的

    public boolean isValidBST(TreeNode root) {
//直接走一个中序遍历，并且保证左小于中小于右
        //先递归左下角，然后更新pre，然后递归回去就是判断当前点大于上一个成立
        if (root == null) return true;

        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}

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

public class Code43 {
    private int k;

    public int kthSmallest(TreeNode root, int k) {
// 中序遍历起来，然后第k个就是答案Z
        this.k = k;
        return dfs(root);
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return -1;
        }
        int leftRes = dfs(root.left);
        if (leftRes != -1) {
            return leftRes;
        }
        k--;//要在这里减
        if (k == 0) {
            return root.val;
        }

        return dfs(root.right);
    }
}

44.二叉树的右视图

public class Code44 {
    public List<Integer> rightSideView(TreeNode root) {
// 借助队列层次遍历，记录每次出队的最后一个数
        List<Integer> re = new ArrayList<>();
        if (root == null) {
            return re;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {//判断队列非空
            int n = queue.size();
            while (n-- > 0) {
                TreeNode poll = queue.poll();
                if (n == 0) {
                    re.add(poll.val);
                }
                if (poll.left != null) queue.add(poll.left);//这里别写成root 
                if (poll.right != null) queue.add(poll.right);
            }
        }
        return re;
    }
}

45.二叉树展开为链表

public class Code45 {
    private TreeNode pre;
    public void flatten(TreeNode root) {
//  来个后序遍历，类似反转链表一样有个前置节点就行
        if (root==null){
            return ;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;  //这里一定要清空左边的指针，理解成处理中间的数据后清空左指针
        root.right = pre;
        pre = root;
    }
}

46.从前序和中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //用哈希表进行映射，然后根据前序头节点去中序里面找，然后不断往下递归，然后回溯赋值
        //     Arrays.copyOfRange注意这个赋值的数组是左闭右开
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        int n = preorder.length;
        if (n == 0) { // 空节点
            return null;
        }
        //找左子树的大小
        Integer index = map.get(preorder[0]);
        int[] pre1 = Arrays.copyOfRange(preorder, 1, index);  //这里切分的数组要不带头元素
        int[] pre2 = Arrays.copyOfRange(preorder, index + 1, n);
        int[] in1 = Arrays.copyOfRange(inorder, 0, index+1); //这里切分的数组不带中元素
        int[] in2 = Arrays.copyOfRange(inorder, index + 1, n);
        TreeNode node = new TreeNode();
        node.left = buildTree(pre1, in1);
        node.right = buildTree(pre2,in2);
        return node;
    }
}

47.路径总和III

class Solution {
    int res;
    HashMap<Long, Integer> map = new HashMap<Long, Integer>();
​
    public int pathSum(TreeNode root, int targetSum) {
//前缀和相减 dfs+哈希（记录路径上的总和的次数，需要添加0） ，采用前缀和的操作往下递归，回溯的时候要恢复现场,
        map.put(0L,1);
        dfs(root, targetSum, 0L);
        return res;
    }
​
    public void dfs(TreeNode root, int targetSum, Long sum) {
        if(root ==null){
            return ;
        }
        sum += root.val;
        if (map.containsKey(sum - targetSum)) {//该路径前面存在某一段和为所求
            res += map.get(sum - targetSum);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        if (root.left != null) dfs(root.left, targetSum, sum);
        if (root.right != null) dfs(root.right, targetSum, sum);
        //回溯
        map.put(sum, map.getOrDefault(sum, 0) - 1);
    }
}

48.二叉树的最近公共祖先

    //    往下递归，并且往上返回，左边找不到就返回右边 , 右边同理
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }

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

public class Code49 {
    private int ans = Integer.MIN_VALUE;
//思路，两边的最大值再对当前节点进行分析
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
​
    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lmax = dfs(root.left);
        int rmax = dfs(root.right);
        ans = Math.max(ans, lmax + rmax + root.val);//记录两边的最大值和加上节点
        return Math.max(0 , Math.max(lmax,rmax) + root.val);//返回两边其中一边的最大值
    }
}

50.岛屿数量

public class Code50 {
    private boolean[][] flag;
​
    public int numIslands(char[][] grid) {
        //遍历，然后四个方向dfs，设计标志数组
        int m = grid.length;
        int n = grid[0].length;
        flag = new boolean[m][n];
        int ans = 0;
​
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !flag[i][j]) {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
​
    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1' || flag[i][j]) {
            return;
        }
        flag[i][j] = true;//四个方向
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
    }
}

51-60

51.腐烂的橘子

class Solution {
        private int[][] Dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
​
    public int orangesRotting(int[][] grid) {
//bfs，拿个队列来存入腐烂的橘子，然后遍历里面的添加新的，
        //开局统计有多少个新鲜橘子，来判断是否还要遍历
        ArrayList<int[]> q = new ArrayList<int[]>();
        int fresh = 0;
        //统计新鲜的
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    q.add(new int[]{i, j}); // 一开始可能也有烂橘子
                }
            }
        }
        int ans = 0;
        while (!q.isEmpty() && fresh > 0) {
            ans++;
            List<int[]> tmp = q;//防止下面添加导致无限循环
            q = new ArrayList<int[]>();
            for (int[] ints : tmp) {
                for (int[] dir : Dirs) {
                    int x = ints[0] + dir[0];
                    int y = ints[1] + dir[1];
                    if (x >= 0 && y >= 0 && x < m && y < n &&grid[x][y] ==1 ){
                        fresh--;
                        grid[x][y] = 2;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
       return fresh>0?-1:ans;
    }
}

52.课程表

public class Code52 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表的操作，然后进行dfs，进行三个状态的判断是否有环
        int[] flags = new int[numCourses];//1表示正在访问，-1表示已经来过，0表示没来
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            list.get(prerequisite[1]).add(prerequisite[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(list, flags, i)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(List<List<Integer>> list, int[] flags, int i) {
        if (flags[i] == 1) {
            return false;
        }
        if (flags[i] == -1) {
            return true;
        }
        flags[i] = 1;
        for (Integer j : list.get(i)) {
            if (!dfs(list, flags, j)) {
                return false;
            }
        }
        flags[i] = -1;
        return true;
    }
}

53.实现前缀树

class Node {
    Node[] sons = new Node[26];
    boolean end;
}

public class Code53 {
    //来个二十六叉树，然后节点存储对应的是否是截止，然后用当前指针的来移动节点
    private Node root;

    public Code53() {
        root = new Node();
    }

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (cur.sons[c] == null) {
                cur.sons[c] = new Node();
            }
            cur = cur.sons[c];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if(cur.sons[c] ==null){
                return false;
            }
            cur = cur.sons[c];
        }
        return cur.end;
    }

    public boolean startsWith(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            c -= 'a';
            if(cur.sons[c] ==null){
                return false;
            }
            cur = cur.sons[c];
        }
        return true;
    }
}

54.全排列

public class Code54 {
    public List<List<Integer>> permute(int[] nums) {
//   全排列就是回溯, 每次需要判断是非达到了n次，没有就往下遍历，并且注意item是不断会变的，需要重新创建    n!复杂度
        //判断是否来过的数组
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        boolean[] used = new boolean[nums.length];
        dfs(0, nums, res, path, used);
        return res;
    }

    public void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] used) {
        if (i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            if (!used[j]) {
                used[j] = true;
                path.add(i , nums[j]);
                dfs(i+1, nums, res, path, used);
                used[j] = false;
                path.remove(i);
            }
        }
    }
}

55.子集

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, path, nums, result);
        return result;
    }

    public static void dfs(int i, List<Integer> path, int[] nums, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j + 1, path, nums, res);
            path.remove(path.size() - 1);
        }
    }

56.电话号码的字母组合

public class Code56 {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    char[] digits;

    //回溯，这里用数组来作为遍历路径，并且做好数和字母的映射，然后dfs里面就是遍历
    public List<String> letterCombinations(String digits) {
        this.digits = digits.toCharArray();
        int n = digits.length();
        List<String> res = new ArrayList<>();
        char[] path = new char[n];
        if (n == 0) return res;
        dfs(0, path, res);
        return res;
    }

    public void dfs(int i, char[] path, List<String> res) {
        if (i == digits.length) {
            res.add(new String(path));
            return;
        }
        for (char c : MAPPING[digits[i] - '0'].toCharArray()) {
            path[i] = c;
            dfs(i + 1, path, res);
            path[i] = '\u0000';
        }
    }
}

57.组合总和

    //回溯，选和不选的操作，递归的结束是值小于0或者到达最大可选
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs(0, target, path, res, candidates);
        return res;
    }

    public void dfs(int i, int left, List<Integer> path, List<List<Integer>> res, int[] candidates) {
        if (left == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (left < 0 || i == candidates.length) {
            return;
        }
        dfs(i + 1, left, path, res, candidates); //不选上
        path.add(candidates[i]);//选上了,这里可以重复选所以还是i
        dfs(i, left - candidates[i], path, res, candidates);
        path.remove(path.size() - 1);
    }

58.括号生成

public class Code58 {
    public List<String> generateParenthesis(int n) {
// dfs，记录左括号必须大于右括号，用数组来存，因此dfs传递括号和左括号数量
        List<String> res = new ArrayList<String>();
        char[] path = new char[n * 2];
        dfs(0, 0, res, path, n);
        return res;
    }
​
    public void dfs(int i, int left, List<String> res, char[] path, int n) {
        if (i == n * 2) {
            res.add(new String(path));
            return;
        }
        //填写左括号
        if (left < n) {
            path[i] = '(';
            dfs(i + 1, left + 1, res, path, n);
        }
        //填写右括号
        if (left > i - left) {
            path[i] = ')';
            dfs(i + 1, left, res, path, n);
        }
    }
}

59.单词搜索

​
public class Code59 {
    private static final int[][] DIR = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
​
    public static boolean exist(char[][] board, String word) {
// 来个dfs遍历四个方向，并且对当前遍历的元素进行判断,注意记录法访问路径和递归正确结束
        boolean[][] path = new boolean[board.length][board[0].length];
        char[] w = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(0, i, j, board, w, path)) {
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(int count, int i, int j, char[][] board, char[] c, boolean[][] path) {
        if (count == c.length) { // 匹配成功！
            return true;
        }
        if (0 > i || i >= board.length || 0 > j || j >= board[i].length) {
            return false;
        }
        if (board[i][j] != c[count] || path[i][j]) {
            return false;
        }
        path[i][j] = true;
        for (int[] ints : DIR) {
            int x = i + ints[0];
            int y = j + ints[1];
            if (dfs(count + 1, x, y, board, c, path)) {
                return true;
            }
        }
        path[i][j] = false;
        return false;
    }
}
​

60.分割回文串

class Solution {
    private String s;
    private List<List<String>> res = new ArrayList<List<String>>();
    private final List<String> path = new ArrayList<>();
​
    public List<List<String>> partition(String s) {
//回溯，并且把他想成时带逗号的a,a,b 那么dfs就是去找起始字符串位置和逗号的位置, 记录路径，想象成树型结构
        this.s = s;
        dfs(0);
        return res;
    }
    //i 表示当前逗号的位置
    public void dfs(int i) {
        if (i == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(i, j)) {//判断当前是否是
                path.add(s.substring(i, j + 1));
                dfs(j + 1);
                path.remove(path.size() - 1);//回溯
            }
        }
    }
​
    public boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

61-70

61.N皇后

​

62.搜索插入位置

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

63.搜索二维矩阵

public class Code62 {
    public boolean searchMatrix(int[][] matrix, int target) {
        //两次二分查找，或者转换int x = matrix[mid / n][mid % n];，或者排除法从后面排除列
        int i = searchInsert(matrix, target); // 找到目标所在的行
        if (i < 0 || i >= matrix.length) {
            return false;
        }
        return searchInsert(matrix[i], target); // 在该行查找目标
    }
​
    public int searchInsert(int[][] nums, int target) {
        int n = nums[0].length;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid][n - 1] > target) {
                right = mid - 1;
            } else if (nums[mid][n - 1] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
​
    public boolean searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
​

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

public class Code64 {
    public int[] searchRange(int[] nums, int target) {
//  去二分搜索左边的在不在，不在直接返回，如果在再去搜搜target+1的坐标也就是left
        int b = bs(nums, target);
        if (nums[b] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{b,bs(nums, target + 1)};
    }
​
    public int bs(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) { // 这里保证多个重复只会搜索到第一个，缩小的是有边界，往左继续搜，然后让l+1
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            }
        }
        return l;
    }
}

65.搜索旋转排序数组

public class Code65 {
    public int search(int[] nums, int target) {
//    搜索旋转数组的最小值，然后进行分段二分找值
        int index = findMin(nums);
        int flag = bs(nums, target, 0, index-1);
        if (flag != -1) {
            return flag;
        }
        return bs(nums, target, index , nums.length -1 );
    }
​
​
    //二分搜索，去找最右边的值进行边界判断
    public int findMin(int[] nums) {
        int l = 0, r = nums.length -1 ;
        while (l < r) {  //注意停止条件
            int mid = (l + r) / 2;
            if (nums[mid] >= nums[nums.length - 1]) {
                l = mid + 1;
            } else {
                r = mid ;    //当前值也有可能是最小值需要计算
            }
        }
        return l ;
    }
​
​
    public int bs(int[] nums, int target, int l, int r) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

66.寻找旋转排序数组的最小值

//上面一题的一种思路，注释看上面    
public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if(nums[mid] >= nums[nums.length -1]){
                l = mid +1;
            }else{
                r = mid;
            }
        }
        return nums[l] ; 
    }

67.寻找两个正序数组的中位数

​

68.有效括号

public class Code68 {
    public boolean isValid(String s) {
//利用栈结构，遇到左括号就存右括号，否则弹出判断是否一样的括号,消消乐
        Deque<Character> q = new ArrayDeque<>();
        if (s.length() % 2 != 0) {
            return false;
        }
        for (char c : s.toCharArray()) {
            if (c == '{') {
                q.push('}');
            } else if (c == '[') {
                q.push(']');
            } else if (c == '(') {
                q.push(')');
            } else if (q.isEmpty() || q.pop() != c) {
                return false;
            }
        }
        return q.isEmpty();
    }
}

69.最小栈

class MinStack {
    //最小栈，保证获取的时候是最小值，因此我需要维护一个前缀和的最小值，所以我栈里面存数组
    //需要初始化里面的前缀值是最大数   
    private  final Deque<int[]> q = new ArrayDeque<>();
    public MinStack() {
        q.push(new int[]{0,Integer.MAX_VALUE});
    }
​
    public void push(int val) {
        q.push(new int[]{val , Math.min(val,getMin())});
    }
​
    public void pop() {
        q.pop();
    }
​
    public int top() {
         return q.peek()[0];
    }
​
    public int getMin() {
        return q.peek()[1];
    }
}
​

70.字符串解码

public class Code70 {
    public String decodeString(String s) {
      /*  当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
      构建两个栈，resStack 存储「数字前的字符串」，multiStack 存储「括号前的数字」。
        两个变量，multi 暂时保存「遍历到的连续数字（即一个完整的整数）」，
        res 暂时保存「数字前的字符串」或「括号里的字符串」。
        当 c 为字母时，在 res 尾部添加 c；
        当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0：
        记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
        记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。muti会十进制运算
        进入到新 [ 后，res 和 multi 重新记录。
        当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
        last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
        cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2*/
​
        Deque<Integer> mutiS = new ArrayDeque<>();
        Deque<String> resS = new ArrayDeque<>();
        int muti = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                muti = 10 * muti + c - '0';   //如果两个都是数字
            } else if (c >= 'a' && c <= 'z') {
                sb.append(c);
            } else if (c == '[') { //遇到左边，就把当前数据加入两个栈里面，然后清空
                resS.push(sb.toString());
                mutiS.push(muti);
                sb.setLength(0); // 清空sb
                muti = 0;
            } else if (c == ']') {//遇到右边就把两个都弹出，这个的弹出的数字n是接下里弹出的字符串的n倍进行遍历
                int cnt = mutiS.pop();
                String res = sb.toString();
                while (cnt > 1) {
                    sb.append(res);
                    cnt--;
                }
                if (resS.isEmpty()) {
                    continue;
                }
                String pop = resS.pop();
                sb.insert(0, pop);
            }
        }
        return sb.toString();
    }
}

71-80

71.每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
// 从后往前走，栈里面从后开始存索引，大于栈顶值就不断弹出，小于栈顶值就加入，然后相减
        Deque<Integer> q = new ArrayDeque<>();
        int n = temperatures.length;
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            while(!q.isEmpty()&&t >= temperatures[q.peek()]){
                q.pop();
            }
            if(!q.isEmpty()){
                ans[i] = q.peek() - i ;
            }
            q.push(i);
        }
        return ans;
    }
}
​

72.柱状图中的最大矩形

​

73.数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        sort(nums,0,nums.length-1 );
        return nums[nums.length - k];
    }
​
​
        public static void sort(int[] arr, int start, int end) {
//注意思路，两种交换，并且注意移动指针的范围变化
        if (start < end) {
            int index = partition(arr, start, end);//获取分区
            sort(arr, start, index - 1);
            sort(arr, index + 1, end);
        }
    }
​
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        while (i <= j) {
            //找到第一个比基准大的元素
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, low, j);
        return j;
    }
​
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

74.前K个高频元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        sort(nums,0,nums.length-1 );
        return nums[nums.length - k];
    }
​
​
        public static void sort(int[] arr, int start, int end) {
//注意思路，两种交换，并且注意移动指针的范围变化
        if (start < end) {
            int index = partition(arr, start, end);//获取分区
            sort(arr, start, index - 1);
            sort(arr, index + 1, end);
        }
    }
​
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        while (i <= j) {
            //找到第一个比基准大的元素
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, low, j);
        return j;
    }
​
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

75.数据流的中位数

​

76.买入股票的最佳时机

class Solution {
    //贪心做法，拿遍历路上的最小值来对后面减掉这个价的最大值就是最大利润
    public static int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE ;
        int profit  = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min , prices[i]);
            profit = Math.max(profit, prices[i] - min);
        }
        return profit;
    }
}

77.跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
//每走一步-1，然后对应+上当前值,更新step找大值，返回的step只能大于等于0
        int n = nums.length;
        if(n ==1 ){
            return true;
        }
        int step = nums[0];
        for (int i = 1; i < n; i++) {
            step--;
            if(step>=0&&step <= nums[i]) {
                step  = nums[i];
            }
​
        }
        return step >= 0 ;
    }
}

78.跳跃游戏II

class Solution {
    public int jump(int[] nums) {
//贪心，每次我都走到最远的最远的距离
        int max = 0;
        int step = 0;
        int end  = 0; // end表示上个起跳点能够到达的最远距离
        for (int i = 0; i < nums.length -1 ; i++) {//这里最后一次不需要跳很关键
            max = Math.max(max, i + nums[i]);//更新当前起跳点最大取值
            if(i ==end){//经过上个点最远距离
                end = max;
                step++;
                
            }
        }
        return step ;
    }
}

79.划分字母区间

​

80.爬楼梯

//数组斐波那契
public class Code80 {
    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

81-90

81.杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //注意前后都要添加1 ，除了1的之外就是集合直接操作，不用换数组
        //画张图并排看一下，然后当前值等于上面和左上角的值相加
        List<List<Integer>> res = new ArrayList<>(numRows);
        List<Integer> list = new ArrayList<>();
        list.add(1);
        res.add(list);
        for (int i = 1; i < numRows; i++) {
            List<Integer> tmp = new ArrayList<>();
            tmp.add(1);
            for (int j = 1; j < i; j++) {
                tmp.add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));
            }
            tmp.add(1);
            res.add(tmp);
        }
        return res;
    }
}

82.打家劫舍

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

83.完全平方数

class Solution {
        public static int numSquares(int n) {
         //dp[i]表示i的最小值，那么只需要去对比前面的状态
            int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                dp[i] = i;//最差也是i
                for (int j = 0; j * j<= i; j++) {
                    dp[i] =Math.min(dp[i],dp[i - j * j] + 1);
                }
            }
            return dp[n];
        }
}

84.零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n =  coins.length;
        //表示n个货币组成对应价值需要的最小硬币数，完全背包
        int[][] dp = new int[n +1][ amount +1 ];
        Arrays.fill(dp[0],Integer.MAX_VALUE /2 );
        dp[0][0] = 0;
//枚举的话这边硬币需要被枚举0索引，所以访问的事coin[i-1]的操作
//然后最大值那块以后都去进行一个/2操作防止+1越界
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if(j < coins[i-1 ]) {
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j] , dp[i][j - coins[i-1 ]] +1 );
                }
            }
        }
        int ans = dp[n][amount];
        return dp[n][amount] == Integer.MAX_VALUE /2 ? -1 : dp[n][amount];
    }
}

85.单词拆分

class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
//用dp[i]记录到i是否可以通过字典构成
        int length = s.length();
        boolean[] dp = new boolean[length + 1];
        dp[0] = true;//0可以通过任何构成
        for (int i = 0; i <= length; i++) {
                        if(!dp[i]){//这里需要记录只有他前面是ture后面接上才有意义
                continue;
            }
            for (String word : wordDict) {
                if(word.length() + i <= s.length()&&s.startsWith(word,i)){
                    dp[i+ word.length()] = true;//内循环遍历子串注意startwith要带偏移量
                }
            }
        }
        return dp[length];
    }
}

86.最长递增子序列

class Solution {
      public static int lengthOfLIS(int[] nums) {
//dp[i]表示到i包括nums[i]，当中最长的递增子序列，那么就是两个循环去跑dp[i] = max(dp[j]) +1
        int n = nums.length;
        int[] dp = new int[n +1 ];
        Arrays.fill(dp, 1);//所有单个都是1 的序列
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]){//这里大于才进行递归
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(max, dp[i]);//保存dp里面最大值，动画看官方
        }
        return max;
    }
}

87.乘数最大子数组

class Solution {
    public static  int maxProduct(int[] nums) {
//维护最小值和最大值，因为最小可能变最大（负数）
        if(nums.length == 0) return 0;
        int[] dpMin = new int[nums.length];
        int[] dpMax = new int[nums.length];
        dpMin[0] = nums[0];
        dpMax[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            int tmp1  = dpMax[i-1]*nums[i];//正数变大
            int tmp2 = dpMin[i-1]*nums[i];//负负得正
            int tmp3 = nums[i];//遇到0后就是本身
​
​
            dpMax[i] = Math.max(Math.max(tmp1, tmp2), tmp3);
            dpMin[i] = Math.min(Math.min(tmp1, tmp2), tmp3);
            
            max  = Math.max(max, dpMax[i]);
        }
        return max;
    }
}

88.分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
//总和奇数，最大值大于一半这些都是不能存在的
        //01 背包，选和不选的问题，并且选的话需要减去对应的价值
        //这里的容量和价值都是nums，并且内循环需要从大往小遍历防止覆盖
        int n  = nums.length;
        int sum = 0 , max = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        if(max > target) return false;
        int dp[] =new int [target+1];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}

89.最长有效括号

​

90.矩阵置零

这个应该插在18

public class Code17 {
    public void setZeroes(int[][] matrix) {
//     遍历两次，然后把对应的地方记录行列，第二次遍历的时候就是弄0
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] column = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                if(matrix[i][j]==0){
                    row[i] = true;
                    column[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                if(row[i]||column[j]){
                  matrix[i][j] = 0;
                }
            }
        }
    }
}

​

91-100

91.不同路径

class Solution {
    public static  int uniquePaths(int m, int n) {
        //思路一是组合数学，下的作为插入点，也就是cmn
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;//只需要初始化一个，负责会重复计算
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}

92.最小路径和

class Solution {
    public static  int minPathSum(int[][] grid) {
        //也是从上和左边的递归式子
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[1][1] = grid[0][0];//初始化对应的节点
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <=n; j++){
                if(i == 1 && j == 1) continue;//需要分类讨论边界点
                else if(i == 1)  dp[i][j] = dp[i][j - 1] + grid[i-1][j-1];
                else if(j == 1)  dp[i][j] = dp[i - 1][j] + grid[i-1][j-1];
                else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

93.最长回文子串

class Solution {
public static String longestPalindrome(String s) {
//dp[i][j]表示i-j是回文，他通过dp[i-1][j-1]且s[i]==s[j]成立就能转移
//由于长度必须大于2 ，这边可以从长度外循环，左指针内循环，可以构造出对应的右边指针
        int len = s.length();
        if(len < 2) return s;
        int max = 1 ;
        int begin = 0 ;
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = true;//所有长度为1的都是回文
        }
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j  = i + L -1;//右指针+1
                if(j>=len) break;
                if(s.charAt(i)==s.charAt(j)){//两个值相等
                    //这里如果是两个的字符串那么就是true不用转移
                    if(j-i <=2){
                        dp[i][j] = true;
                    }else{
                      dp[i][j] = dp[i+1][j-1];  
                    }
                    
                }else{
                    dp[i][j] = false;
                }
                if(dp[i][j]&&j - i + 1 > max){//更新最大长度
                    max = j - i + 1;
                    begin = i;
                }
            }
​
        }
        return s.substring(begin,begin+max);
    }
}

94.最长公共子序列

class Solution {
    public  static int longestCommonSubsequence(String text1, String text2) {
//dp[i][j]表示对text1中0 - i ，以及text2中0 -j 中最长公共子序列元素个数
        int m = text1.length();
        int n = text2.length();
        int[][]dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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-1][j], dp[i][j-1]); 
                }
                
            }
        }
        return  dp[m][n];
    }
}

95.编辑距离

class Solution {
     public static int minDistance(String word1, String word2) {
//定义dp[i][j]是对应的word1 0 - i 变成word2 0- j 最小需要的步数
​
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        //这边需要初始化，也就是全部删，增的情况
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else{
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                //分别对应改，删，增
                }
                
            }
        }
        return dp[m][n];
    }
}

96.只出现一次的数字

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

97.多数元素

class Solution {
    public int majorityElement(int[] nums) {
        //排序取中值，或者随机取一个数判断是否是众数
        Arrays.sort(nums);
        int n  = nums.length;
        return nums[n/2];
    }
}

98.颜色分类

class Solution {
    public void sortColors(int[] nums) {
        sort(nums,0,nums.length -1 );
    }
    public static void sort(int[] arr, int start, int end) {
//注意思路，两种交换，并且注意移动指针的范围变化
        if (start < end) {
            int index = partition(arr, start, end);//获取分区
            sort(arr, start, index - 1);
            sort(arr, index + 1, end);
        }
    }
​
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        while (i <= j) {
            //找到第一个比基准大的元素
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, low, j);
        return j;
    }
​
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class Code97 {
    public int majorityElement(int[] nums) {
        //排序取中值，或者随机取一个数判断是否是众数
        Arrays.sort(nums);
        int n  = nums.length;
        return nums[n/2];
    }
}

99.下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
//第一步先把从右往左找到第一个左边小于右边的数x
​
        int n = nums.length;
        int i = n - 2;
        while (i>=0&&nums[i] >= nums[i + 1]) {
            i--;
        }
        //第二步筛选出x右边大于x的最小数字(x后面都是单调递减)，并进行交换
        int j = n - 1;
        //
        while (i>=0&&nums[j] <= nums[i]) {
            j--;
        }
        if(i>= 0){
         swap(nums, i, j);   
        }
        
        //最后把x后的数字进行反转
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
​
    }
​
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

100.寻找重复数

class Solution {
    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]];
        }
        int pre1 = 0 ;
        int pre2 = slow;
        while(pre1!=pre2){
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
}