Hot100

哈希

两数之和

用哈希表维护一个当前<期望值，当前值>的哈希表即可。

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

字母异位词分组

用一个哈希表维护<字母异位词，原字符串>

其中可以将每一个质数代替一个字母，质数相乘独特的字母异位词有独立的质数相乘结果。但是使用此方法要注意存在溢出的风险。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for(String str : strs){
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String t = new String(c);
            if(hashMap.containsKey(t)){
                List l = hashMap.get(t);
                l.add(str);
                hashMap.put(t,l);
            } else {
                List<String> l = new ArrayList<>();
                l.add(str);
                hashMap.put(t,l);
            }
        }
        List<List<String>> res = new ArrayList<>();
        for(Map.Entry<String, List<String>> p : hashMap.entrySet()){
            res.add(p.getValue());
        }
        return res;
    }
}

最长连续序列

首先全部加入Set中，然后遍历Set判断当前数字是否为该段序列的开头，如果是则遍历下去。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        int res = 0;

        for(int i = 0 ; i < nums.length; i ++){
            hashSet.add(nums[i]);
        }
        for(int t : hashSet){//注意这里需要从hashSet遍历，不能从nums，nums有重复元素
            if(!hashSet.contains(t-1)){
                int num = t+1;
                while(hashSet.contains(num)) num++;
                res = Math.max(res, num-t);
                
            }
        }

        return res;
    }
}

本质上还是双指针

双指针

移动零

本质上还是双指针，采用覆盖写的方式实现。

class Solution {
    public void moveZeroes(int[] nums) {
        //维护两个指针，p1指向第一个零，p2指向第一个非零
    int i = 0;
    for(int j = 0 ; j < nums.length;j++){
        if(nums[j]!=0){
            nums[i] = nums[j];
            i++;
        }
    }
    
    for(;i<nums.length;i++){
        nums[i] = 0;
    }
    
    }
}

盛水最多的容器

当height[i] < height[j] 时，i向右移动，有可能实现height[i++] > height[i]从而增大最大面积。如果向左移动j，则Math.min(height[i],height[j–])始终为height[i]，不可能增大最大面积。

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

三数之和

正确的去重逻辑应该在找到一个结果后再跳过重复的 j 和 k。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res= new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length -2 ; i ++){
            
            if( i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            int j = i + 1;
            int k = nums.length -1;
            while( j < k){

                if(nums[j] + nums[k] + nums[i] < 0){
                    j ++;
                } else if(nums[j] + nums[k] + nums[i] > 0){
                    k --;
                } else{
                    List<Integer> t = new ArrayList<>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(nums[k]);
                    res.add(t);
        while (j < k && nums[j] == nums[j + 1]) j++;
        while (j < k && nums[k] == nums[k - 1]) k--;
        j++;
        k--;
                }

            }
        }
        return res;
    }
}

接雨水

实际上就是找到i位置，左边的最大值，以及右边的最大值height[i]

使用双向指针，分别维护一个前缀最大值和一个后缀最大值

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int preSum = 0;
        int aftSum = 0;
        int i = 0;
        int j = height.length - 1;
        while( i < j ){
            preSum = Math.max(preSum, height[i]);
            aftSum = Math.max(aftSum, height[j]);
            if(preSum < aftSum){
                res += preSum - height[i];
                i++;
            } else{
                res += aftSum - height[j];
                j--;
            }
        }
    return res;
    }

}

滑动窗口

和为k的子数组

连续子数组之和可以使用sum(i,j) = sum(0,j) - sum(0,i)表示，然后用一个HashMap维护sum(0,i)的值

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int preSum = 0 ;
        int res = 0;
        hashMap.put(0,1);
        for(int i = 0 ; i < nums.length ; i ++){
            preSum += nums[i];
            res += hashMap.getOrDefault(preSum - k, 0);
            hashMap.put(preSum, hashMap.getOrDefault(preSum,0) + 1);

        }
        return res;
    }
}

滑动窗口的最大值

使用单调队列，维护一个递减的单调队列，一旦入队一个n，需要删除前面所有小于n的值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonoQueue d = new MonoQueue(k);
        int[] res = new int[nums.length - k + 1];
        for(int i = 0 ; i < k ; i ++){
            d.push(nums[i]);
            res[0] = d.peek();
        }
        for(int i = k; i < nums.length ; i ++){
            d.push(nums[i]);
            d.pop(nums[i-k]);
            res[i - k + 1] = d.peek();
        }
        return res;

    }
}

class MonoQueue{
    Deque<Integer> d; 
    int size;
    public MonoQueue(int size){
        this.size = size;
        this.d = new ArrayDeque<>();
    }

    public void push(int n ){

        while(!d.isEmpty() && d.peekLast() < n){
            d.removeLast();
        }
 
        d.addLast(n);
    }

    public int peek(){
        return d.peekFirst();
    }

    public void pop(int n){
        if(!d.isEmpty() && d.peekFirst() == n){
            d.removeFirst();
        }
    }



}

单调队列：在滑动窗口中快速获取最大值和最小值

单调栈：在一维数组中快速找到某个元素左右两边第一个比它大或小的元素。

无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        int res = 1;
        Set<Character> hashSet = new HashSet<>();
        int i = 0;
        int j = 0;
        for(i = 0 ; i < s.length();i++){
            while(hashSet.contains(s.charAt(i))){
                hashSet.remove(s.charAt(j));
                j++;
            }
            hashSet.add(s.charAt(i));
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int m = s.length(), n = p.length();
        if (m < n) return res;

        int[] count = new int[26];
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }

        int diff = 0;
        for (int c : count) if (c != 0) diff++;

        if (diff == 0) res.add(0);

        for (int i = n; i < m; i++) {
            int add = s.charAt(i) - 'a';
            int remove = s.charAt(i - n) - 'a';

            if (count[add] == 0) diff++;
            count[add]++;
            if (count[add] == 0) diff--;

            if (count[remove] == 0) diff++;
            count[remove]--;
            if (count[remove] == 0) diff--;

            if (diff == 0) res.add(i - n + 1);
        }

        return res;
    }
}

链表

相交链表

遍历两次判断交点

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

子串

和为K的子数组

TODO

滑动窗口最大值

TODO

最小覆盖子串

TODO

普通数组

最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {

        int preMin = 0;
        int cur = 0;
        int res = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length ; i ++){
            cur = cur + nums[i];
            res = Math.max(res, cur - preMin);
            preMin = Math.min(preMin, cur);
        }
        return res;
    }
}

合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 1)
            return intervals;
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        int j = 1;
        int[] a = intervals[i];
        while(j < intervals.length){
            int[] b = intervals[j];
            if(a[1] >= b[0]){
                //可以合并
                a[1] = Math.max(a[1],b[1]);
            } else {
                //不能合并
                List<Integer> t1 = new ArrayList<>();
                t1.add(a[0]);
                t1.add(a[1]);
                res.add(t1);
                i = j;
                a = intervals[i];
            }
            j = j + 1;

        }
        List<Integer> t1 = new ArrayList<>();
        t1.add(a[0]);
        t1.add(a[1]);
        res.add(t1);
        int[][] t = new int[res.size()][2];
        for(int k = 0 ; k < res.size(); k ++){
            t[k][0] = res.get(k).get(0);
            t[k][1] = res.get(k).get(1);
        }
        return t;
    }

}

轮转数组

使用
$$
[b,a] -> [a^T,b^T]^T
$$

class Solution {
    public void rotate(int[] nums, int k) {
        //[b,a] -> [a^T,b^T]^T
        int t = k % nums.length;
        swap(nums, 0, nums.length - 1 - t);
        swap(nums, nums.length - t, nums.length-1);
        swap(nums, 0, nums.length - 1);
    }
    public void swap(int[] nums, int i, int j){
        while(i < j){
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
            i++;
            j--;
        }

    }
}

除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] suf = new int[nums.length];
        int[] res = new int[nums.length];
        Arrays.fill(suf, 1);
        for(int i = nums.length - 2 ; i >= 0 ; i --){
            suf[i] = nums[i+1] * suf[i+1]; 
        }

        int pre = 1;
        for(int i = 0 ; i < nums.length ; i ++){
            res[i] = suf[i] * pre;
            pre *= nums[i];
        }
        return res;
    }
}

缺失的第一个正数

交换每个数到其该放直的位置上

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i = 0 ; i < nums.length ; i ++){
            
                //交换
                while(nums[i] <= nums.length && nums[i]  > 0 && nums[i] != nums[nums[i] - 1]){
                    swap(nums, i, nums[i] - 1);
                } 
            
        }
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] != i + 1)
                return i + 1;
        }
        return nums.length + 1;
    }
    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

矩阵

矩阵置零

使用两个变量暂存第一行和第一列是否置为零，使用第一行和第一列暂存，第二行以及第二列之后的元素是否置为零。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row_flag, col_flag = False, False
        
        # 处理第一行
        for i in range(n):
            if matrix[0][i] == 0:
                row_flag = True
                break
        
        # 处理第一列
        for i in range(m):
            if matrix[i][0] == 0:
                col_flag = True
                break
        
        # 从第二行开始遍历矩阵，若有0则将对应的行和列头元素置为0
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        # 根据第一行和第一列的标记更新矩阵
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        # 最后处理第一行
        if row_flag:
            for i in range(n):
                matrix[0][i] = 0
        
        # 最后处理第一列
        if col_flag:
            for i in range(m):
                matrix[i][0] = 0

螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        V v = new V(matrix);
        v.move();
        return v.res;
    }
}

class V {
    int[][] matrix;
    int[][] visit;
    int i;
    int j;
    int d;
    int m;
    int n;
    int cnt;
    List<Integer> res;

    public V(int[][] matrix) {
        this.matrix = matrix;
        this.visit = new int[matrix.length][matrix[0].length];
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.res = new ArrayList<>();
        this.i = 0;
        this.j = -1;
    }

    public int move() {
        while (cnt < m * n) {
            if (d == 0) {
                if (canMove(i, j + 1, m, n, visit)) {
                    j++;
                    visit[i][j] = 1;
                    cnt++;
                    res.add(matrix[i][j]);
                } else {
                    d = 1;
                }
            } else if (d == 1) {
                if (canMove(i + 1, j, m, n, visit)) {
                    i++;
                    visit[i][j] = 1;
                    cnt++;
                    res.add(matrix[i][j]);
                } else {
                    d = 2;
                }
            } else if (d == 2) {
                if (canMove(i, j - 1, m, n, visit)) {
                    j--;
                    visit[i][j] = 1;
                    cnt++;
                    res.add(matrix[i][j]);
                } else {
                    d = 3;
                }

            } else if (d == 3) {
                if (canMove(i - 1, j, m, n, visit)) {
                    i--;
                    visit[i][j] = 1;
                    cnt++;
                    res.add(matrix[i][j]);
                } else {
                    d = 0;
                }
            }
        }
        return 0;
    }

    public boolean canMove(int i, int j, int m, int n, int[][] visit) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visit[i][j] == 1) {
            return false;
        }
        return true;
    }
}

旋转图像

转置后进行轴对称

搜索二维矩阵II

链表

相交链表

反转链表

反转的板子

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;    // 前一个节点
        ListNode cur = head;    // 当前节点

        while (cur != null) {
            ListNode next = cur.next; // 暂存下一个节点
            cur.next = pre;           // 反转指向
            pre = cur;                // 前移 pre
            cur = next;               // 前移 cur
        }

        return pre; // 最后 pre 指向新头结点
    }
}

回文链表

1.通过快慢指针找到中点

2.判断节点个数奇偶

3.反转前段或者后段链表

public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isOdd = false;
        while(fast.next != null && fast.next.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast.next != null){
            slow = slow.next;
            isOdd = false;
        } else{
            isOdd = true;
        }
        ListNode slow2 = head;
        ListNode p = rev(slow2, slow);
        if(isOdd){
            slow = slow.next;
        }
        while(slow != null){
            if(slow.val != p.val){
                return false;
            }
            p = p.next;
            slow = slow.next;
        }
        return true;
    }
    public ListNode rev(ListNode head, ListNode stop){
        ListNode pre = null;
        ListNode cur = head;
        while( cur != stop  ){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;

        }
        return pre;
    }

环形链表

环形链表II

合并两个有序链表

两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int cin = 0;
        ListNode head = new ListNode();
        ListNode p = head;
        while(l1 != null || l2 != null){
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            
            int c = (a + b + cin) % 10;
            cin = (a + b + cin) / 10;
            ListNode t = new ListNode(c);
            p.next = t;
            p = p.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }

        if (cin == 1){
            ListNode t = new ListNode(1);
            p.next = t;
        }
        return head.next;
         
    }
}

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

两两交换链表中的节点

K个一组翻转链表

class Result {
    ListNode left;
    ListNode right;
    ListNode theNextOne;
    int count;
    Result(ListNode left, ListNode right, ListNode theNextOne, int count) {
        this.left = left;
        this.right = right;
        this.count = count;
        this.theNextOne = theNextOne;
    }
}
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode h = new ListNode();
        
        h.next = head;
        ListNode p = h.next;
        ListNode last = h;

        while(p!=null){
            int cnt = 0;
            Result r = reverseK(p, k);
            if(r.count == 1){
                last.next = r.left;
                p = r.theNextOne;
                last = r.right;
            } else {
                Result r1 = reverseK(r.left,k);
                last.next = r1.left;
                break;
            }
        }
        return h.next;

    }
    public Result reverseK(ListNode head, int k){
        ListNode pre = null;
        ListNode cur = head;
        ListNode last = head;
        ListNode theNextOne = null;
        int cnt = 0;
        while(cur != null && cnt < k){
            ListNode tmp = cur.next;
            if(cnt == k - 1){
                theNextOne = tmp;
            }
            cur.next = pre;
            pre = cur;
            cur = tmp;
            cnt++;
        }
        int isFinish = 0;
        if(cnt < k){
            isFinish = 0;
        } else {
            isFinish = 1;
        }
        return new Result(pre, last, theNextOne, isFinish);
    }
}

合并K个升序链表

/**
 * 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 mergeKLists(ListNode[] lists) {
       
        
        ListNode pre = new ListNode();
         ListNode head =pre;
         ListNode curNode = null;
        while(true){
            int minTmp= Integer.MAX_VALUE;
            int k = -1;
            for(int i = 0 ; i < lists.length;i++){
                if(lists[i] == null) continue;
                if(lists[i].val < minTmp){
                    minTmp = lists[i].val;
                    curNode = lists[i];
                    k = i;
                }
            }
            if(minTmp == Integer.MAX_VALUE){
                return head.next;
            }
            pre.next = curNode;
            pre = curNode;
            lists[k] = curNode.next;
        }
    }
}

树

二叉树中序遍历

中序遍历一下，按照

dfs(root.left)

print(root)

dfs(root.right)

public static void dfs(TreeNode root){
    if(root==null)
    return;
    dfs(root.left);
    res.add(root.val);
    dfs(root.right);

}

二叉树的最大深度

递归查找每一层节点的深度

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

对称二叉树

递归交换检查每层的左右节点是否对称

public static boolean dfs(TreeNode left, TreeNode right){
    if(left == null && right == null) 
    return true;
    if(left == null && right != null)
    return false;
    if(right == null && left != null)
    return false;
    if(left.val == right.val && dfs(left.left,right.right) && dfs(left.right,right.left) )
    return true;
    return false;
}

翻转二叉树

使用递归交换每一层的左右子节点

public static void dfs(TreeNode node){
    if(node == null) return;
    TreeNode t = new TreeNode();
    t = node.left;
    node.left = node.right;
    node.right = t;
    dfs(node.left);
    dfs(node.right);
}

二叉树的直径

题目：给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

思路：递归搜索每个节点的左右子树路径和，在主函数使用一个全局变量维护该最大值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    static int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) 
        return 0;
        ans = 1;
        dep(root);
        return ans-1;

    }
    public static int dep(TreeNode node){
        if(node == null) return 0;
        int l = dep(node.left);
        int r = dep(node.right);
        ans = Math.max(ans, l+r+1);
        return Math.max(l,r)+1;
    }
}

注：二叉树的直径不同于图的直径，图的直径可以通过两次遍历先找到一端的直径端点，然后再找到另一端的直径端点实现，模板如下

public static int treeDiameter(int n, List<List<Integer>> adj) {
        if (n == 0) return 0;
        // 从任意节点 0 开始 BFS 找最远点
        int far = bfsFarthest(0, n, adj)[0];
        // 从 far 再次 BFS，得到最远距离
        int[] res = bfsFarthest(far, n, adj);
        return res[1]; // distance
    }

    // 返回长度为2的数组: [farthestNode, distance]
    private static int[] bfsFarthest(int src, int n, List<List<Integer>> adj) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new ArrayDeque<>();
        q.add(src);
        dist[src] = 0;
        int farNode = src;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                    if (dist[v] > dist[farNode]) farNode = v;
                }
            }
        }
        return new int[]{farNode, dist[farNode]};
    }

二叉树层序遍历

使用一个Queue维护二叉树的每层节点。for循环统计当前层节点数量。

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res= new ArrayList<>();
        if(root==null){
            return res;
        }
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while(!d.isEmpty()){
            int size = d.size();
            List<Integer> t = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode n=d.removeFirst();
                t.add(n.val);
                if(n.left!=null) d.addLast(n.left);
                if(n.right!=null) d.addLast(n.right);
            }
            res.add(t);
        }
        return res;
    }

数组转化为平衡二叉搜索树

BST递归后序遍历建立树，核心公式：int mid = (l + r) / 2 选中之后再建树，记住就好。

注意二分法的递归范围为

1
2
3

if (left > right) return null;
TreeNode l = dfs(nums, left, mid - 1);
TreeNode r = dfs(nums, mid + 1, right);

public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    public static TreeNode dfs(int[] nums, int left, int right){
        if(left > right)
        return null;
        int mid = (left + right) / 2;
        TreeNode t = new TreeNode(nums[mid]);
        TreeNode l = dfs(nums,left,mid-1);
        TreeNode r = dfs(nums,mid+1,right);
        t.left = l;
        t.right = r;
        return t;
    }

验证二叉搜索树

递归查询每个节点是否大于其左子树的最大值，并且小于其右子树的最小值。额外创建两个递归查询左子树的最大值和右子树的最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }
    static boolean dfs(TreeNode root){
        if(root == null)
        return true;
        int mid = root.val;
        long l = root.left==null? Long.MIN_VALUE: (long)dfs_r(root.left);
        long r = root.right==null? Long.MAX_VALUE: (long)dfs_l(root.right);
        return mid > l && mid < r && dfs(root.left) && dfs(root.right);
    }
    static int dfs_l(TreeNode root){
        if(root.left != null)
            return dfs_l(root.left);
        else 
            return root.val; 
    }
    static int dfs_r(TreeNode root){
        if(root.right!=null){
            return dfs_r(root.right);
        }else{
            return root.val;
        }
    }
}

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

其实就是中序遍历到的第k个元素，维护一个全局变量统计一下当前统计到的元素个数。

static int cnt;
static int res;
public int kthSmallest(TreeNode root, int k) {
    cnt = 0;
    dfs(root,k);
    return res;
}
static void dfs(TreeNode root, int k){
    if(root == null){
        return; 
    }
    dfs(root.left, k);
    cnt ++;
    if(cnt == k){
        res=root.val;
        return;
    }
    dfs(root.right, k);
}

二叉树的右视图

对于同一深度的节点来说，如果右子树存在的话就只能看见右子树，所以我们要从右->左进行遍历，维护一个数组，统计深度为i的层是否已经有节点在右视图中。从顶部到底部访问，可以改为[根->右->左]

注意：其中[右->左]的顺序可以不变,改变[根]的位置可以实现从顶部到底部，但不能从底部到顶部，考虑这一种情况，如果有一个左子树很大，但是右子树很小的二叉树，在[右->左]的递归顺序下，也会优先存储右子树深度较浅的值。

static int[] a;
    static List<Integer> res;
    public List<Integer> rightSideView(TreeNode root) {
        a = new int[100];
        res = new ArrayList<>();
        dfs(root,0);
        return res;
    }
    static void dfs(TreeNode root, int depth){
        if(root == null)
        return;
        if(a[depth] == 0){
            res.add(root.val);
            a[depth] = 1;
        }
        dfs(root.right,depth + 1);
        dfs(root.left,depth + 1);

    }

二叉树展开为链表

解法一：采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。

为此，要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？

考虑到链表为先序遍历的结果，我们要将递归的根节点的右子树指向【右->左->根】的访问到的倒数第二个节点，所以需要反向遍历为【右->左->根】，用全局变量记录下访问到的根节点。

private static TreeNode head;

public void flatten(TreeNode root) {
    head=null;
    dfs(root);

}
public static void dfs(TreeNode node){
    if(node == null)
    return;
    dfs(node.right);
    dfs(node.left);
    node.left = null;
    node.right = head;
    head = node;

}

解法二：

正常使用先序遍历的结果，由于进入递归后，但是依然要使用全局变量记录下前一个节点，以及当前节点的原始右子树。

private static TreeNode pre; // 记录前一个访问过的节点

public void flatten(TreeNode root) {
    pre = null;   // 每次调用前要清空
    dfs(root);
}

public static void dfs(TreeNode node) {
    if (node == null) return;

    // 如果 pre 已经存在，把 pre 的 right 指向当前节点
    if (pre != null) {
        pre.left = null;   // 左子树要断掉
        pre.right = node;  // 前一个节点的右指针连到当前节点
    }
    pre = node; // 更新 pre，表示“当前节点就是下一个节点的前驱”

    // ⚠️ 保存右子树，避免被覆盖
    TreeNode right = node.right;

    // 递归处理左子树
    dfs(node.left);

    // 递归处理原始右子树
    dfs(right);
}

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

由于前序是[根->左->右]，每个节点的构造由一个全局变量维护，不要将这个全局变量作为递归的变量传入！中序是[左->根->右]，可以使用前序的[根]找到中序[根的位置]，然后中序[根]的左右分别为左右子树。

class Solution {
    private int i = 0;
    private int[] preorder;
    private int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return dfs(0,preorder.length-1);
    }
    public TreeNode dfs(int j, int k){
        if(j > k)
        return null;
        int root = this.preorder[i];
        int n = 0;
        for(int m = j; m <= k;m++){
            if(this.inorder[m] == root){
                n = m;
                break;
            }
        }
        TreeNode node = new TreeNode(root);
        i++;
        node.left = dfs(j,n-1);
        node.right = dfs(n+1,k);
        return node;
    }
}

路径综合III

使用两层递归

class Solution {
    private int res = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        dfs(root,targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right,targetSum);
        return res;
    }
    public void dfs(TreeNode root, int targetSum){
        if(root == null){
            return;
        }
        int val = root.val;
        if(val == targetSum){
            res ++;
        }
        
        dfs(root.left, targetSum - val);
        dfs(root.right, targetSum - val);
    }
}

使用全局变量记录路径和为n的次数为m，然后使用回溯法+一层递归

class Solution {
    private int res = 0;
    private Map<Long, Integer> prefix = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        prefix.put(0L, 1); // 前缀和为 0 出现过 1 次（空路径）
        dfs(root, 0L, targetSum);
        return res;
    }

    private void dfs(TreeNode node, long currSum, int targetSum) {
        if (node == null) return;

        currSum += node.val;

        // 找到满足条件的路径数
        res += prefix.getOrDefault(currSum - targetSum, 0);

        // 更新前缀和
        prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);

        // 递归子树
        dfs(node.left, currSum, targetSum);
        dfs(node.right, currSum, targetSum);

        // 回溯，撤销当前节点的贡献
        prefix.put(currSum, prefix.get(currSum) - 1);
    }
}

二叉树的最近公共祖先

定义dfs为在以当前节点为根的子树中，返回找到的 p、q 或者公共祖先。

class Solution {
    private TreeNode m;
    private TreeNode n;
    private TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        m = p;
        n = q;
        
        return dfs(root);
    }
 
    public TreeNode dfs(TreeNode node){
        if(node == null || node == n || node == m){
            return node;
        }
        TreeNode l = dfs(node.left);
        TreeNode r = dfs(node.right);
        if(l!=null && r!=null){
            return node;
        }
        return l==null?r:l;
    }
}

二叉树中的最大路径和

和二叉树的直径类似，使用递归函数维护一个当前节点向下走单边路径的最大值

dfs 的含义

返回值：从当前节点出发，向下走一条单边路径（只能选左子树或右子树，不可能两边都选，因为往父节点传递的时候只能走一边）。
如果子树路径和为负数，那还不如不要，所以用 Math.max(..., 0)。

res 的含义

res 是一个全局变量，存储 当前遍历过程中出现的最大路径和。
在每个节点 root 处，路径最大值可能是：
1
左子树贡献 + root.val + 右子树贡献
这个结果可以形成一条经过 root 的完整路径，因此要用它更新 res。

为什么返回 root.val + Math.max(l, r)

父节点只能选择一边接上当前节点的路径。
所以返回值是 “当前节点值 + 左右子树中较大的一边”。

class Solution {
    private int res = 0;

    public int maxPathSum(TreeNode root) {
        if(root == null) 
            return 0;
        res = root.val;       // 初始化结果为根节点值，避免 res 初始值太小
        dfs(root);            // 深度优先遍历计算
        return res;
    }

    // 返回 "以 root 为起点，到叶子方向的最大路径和"
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        // 分别计算左子树、右子树的最大贡献（小于0的路径直接舍弃，所以用 Math.max(..., 0)）
        int l = Math.max(dfs(root.left), 0);
        int r = Math.max(dfs(root.right), 0);

        // 更新全局最大路径：可能经过当前 root，路径 = 左贡献 + root.val + 右贡献
        res = Math.max(res, l + r + root.val);

        // 返回 "当前节点能提供给父节点的最大单边贡献"
        return root.val + Math.max(l, r);
    }
}

图论

岛屿数量

dfs递归感染四周岛屿，将岛屿由’1’变为’2’，通过边界条件控制感染。

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

腐烂的橘子

类似于图的层序遍历


    class Node{
    int x;
    int y;
    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
    public int getX(){
        return x;
    }
    public int getY(){
        return y;
    }
    }

class Solution {

    public int orangesRotting(int[][] grid) {
        int res = -1;
        int fresh =0 ;
            int m = grid.length;
            int n = grid[0].length;
            
            Deque<Node> d = new ArrayDeque<>();
            for(int i = 0 ; i < m; i ++){
                for(int j = 0 ;j<n;j++){
                    if(grid[i][j] == 2){
                        Node node = new Node(i,j);
                        d.addLast(node);
                    } else if (grid[i][j] == 1){
                        fresh ++;
                    }
                }
            }
            while(!d.isEmpty()){
                res++;
                int size = d.size();
                for(int k = 0 ; k < size ; k++){
                    Node t = d.removeFirst();
                    int x = t.getX();
                    int y = t.getY();
                    if(x + 1 < m && grid[x+1][y] == 1){
                        Node t1 = new Node(x+1,y);
                        d.addLast(t1);
                        grid[x+1][y]='2';
                        fresh--;
                    }
                    if( x - 1 >=0 && grid[x-1][y] == 1){
                        Node t1 = new Node(x-1,y);
                        d.addLast(t1);
                        grid[x-1][y]='2';
                        fresh--;
                    }
                    if( y-1 >=0 && grid[x][y-1] == 1){
                        Node t1 = new Node(x,y-1);
                        d.addLast(t1);
                        grid[x][y-1]='2';
                        fresh--;
                    }
                    if(y+1 < n && grid[x][y+1] == 1){
                        Node t1 = new Node(x,y+1);
                        d.addLast(t1);
                        grid[x][y+1]='2';
                        fresh--;
                    }
                }
            }
            return fresh==0?Math.max(0,res):-1;
    }
}

课程表

构造一个邻接表，用拓扑排序的方式遍历，计算最后是否有节点无法被写入拓扑排序中

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //入度统计
        int[] inDegree = new int[numCourses];
        //建图
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0 ; i < numCourses; i ++){
            List<Integer> l = new ArrayList<>();
            graph.add(l);
        }
        for(int i = 0 ; i < prerequisites.length;i++){
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            graph.get(a).add(b);
            inDegree[b] ++;
        }
        //统计删除点的数量
        List<Integer> res = new ArrayList<>();
        //入度为0的点加入队列
        Deque<Integer> d = new ArrayDeque<>();
        for(int i = 0 ; i < numCourses ; i++){
            if(inDegree[i] == 0){
                d.addLast(i);
                res.add(i);
            }

        }
        while(!d.isEmpty()){
            int size = d.size();
            for(int i = 0 ; i < size ; i ++){
                //找到所有入度为0的点所指向的边
                int c = d.removeFirst();
                List<Integer> t = graph.get(c);
                for(int m  : t){
                    inDegree[m]--;
                    //如果导致其入度为0，则入队
                    if(inDegree[m] == 0){
                        d.addLast(m);
                        res.add(m);
                    }
                }
            }
        }
        //判断是否删除了所有节点
        if(res.size() == numCourses){
            return true;
        }
        return false;

    }
}

前缀树Trie

前缀树实际上就是一个多节点的树，用HashMap<Character,Trie>或者Tire[]来维护子节点，然后在每个节点额外维护一个符号表示是否有输入到此为止。

class Trie {
    HashMap<Character, Trie> hashMap;
    int flag ;
    public Trie() {
        hashMap = new HashMap<>();        
        flag = 0;
    }
    
    public void insert(String word) {
        Trie t = this;
        int len = word.length();
        for(int i = 0 ; i < len ; i ++){
            char c = word.charAt(i);
            if(t.hashMap.containsKey(c)){
                t = t.hashMap.get(c); 
            } else {
                Trie trie = new Trie();
                t.hashMap.put(c,trie);
                t = trie;
            }
        }
        t.flag = 1;
    }
    
    public boolean search(String word) {
        Trie t = this;
        int len = word.length();
        for(int i = 0 ; i < len ; i ++){
            char c = word.charAt(i);
            if(t.hashMap.containsKey(c)){
                t = t.hashMap.get(c); 
            } else {
                return false;
            }
        }
        return t.flag == 1 ? true : false;
    }
    
    public boolean startsWith(String prefix) {
        Trie t = this;
        int len = prefix.length();
        for(int i = 0 ; i < len ; i ++){
            char c = prefix.charAt(i);
            if(t.hashMap.containsKey(c)){
                t = t.hashMap.get(c); 
            } else {
                return false;
            }
        }
        return true;
    }
}

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

回溯

全排序

🧩 问题：res.add(num) 加进去的值会跟着变化

这段代码：

if (num.size() == nums.length) {
    res.add(num);
    return;
}

这里 num 是一个 引用（引用传递），
当你后面继续修改 num（比如 num.add() 或 num.remove()）时，
res 里保存的那个引用指向的同一个 List 对象，也会被一起改动。

因此在结果里面加入时应该使用构造函数进行拷贝。

class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        dfs(new ArrayList<>(), nums);
        return res;
    }

    public void dfs(List<Integer> path, int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); // ✅ 一定要复制
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!path.contains(nums[i])) {
                path.add(nums[i]);
                dfs(path, nums);
                path.remove(path.size() - 1);
            }
        }
    }
}

子集

class Solution {
    List<List<Integer>> res;
      public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        List<Integer> t = new ArrayList<>();
        dfs(t,0,nums);
        return res;
    }
    public void dfs(List<Integer> cur, int j, int[] nums){
        List<Integer> tmp = new ArrayList<>(cur);
        res.add(tmp);
        for(int i = j ; i < nums.length;i++){
            cur.add(nums[i]);
            dfs(cur, i+1,nums);
            cur.remove(cur.size()-1);
        }
        

    }
}

分割回文串

class Solution {
    List<List<String>> res;

    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) {
                    dp[i][j] = 1;
                    continue;
                }
                if (s.charAt(i) == s.charAt(j)) {
                    if (i + 1 <= j - 1) {
                        dp[i][j] = dp[i + 1][j - 1];
                    } else {
                        dp[i][j] = 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        List<String> c = new ArrayList<>();
        dfs(c,0,s,dp);
        return res;
    }

    public void dfs(List<String> cur, int i, String s, int[][] dp){
        List<String> tmp = new ArrayList<>(cur);
        if(i == s.length()){
            res.add(tmp);
            return;
        }
        for(int j = i; j < s.length();j++){
            if(dp[i][j] == 1){
                String o = s.substring(i,j+1);
                tmp.add(o);
                dfs(tmp, j+1,s,dp);
                tmp.remove(tmp.size()-1);
            }
        }

    }
}

八皇后

二分查找

搜索二维矩阵

从左下角或者右上角开始搜索，这样每个方向都是单调的

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

搜索插入位置

找到第一个大于等于目标元素的下标

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

找到第一个小于等于目标元素的下标

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

两种二分查找写法的核心区别

写法	区间含义	循环条件	mid 更新逻辑	常见返回值	常用于
✅ 写法1：`while (left < right)`	左闭右开区间 `[left, right)`	`left < right`	`mid = left + (right - left) / 2` 如果条件不满足则 `right = mid`	最后返回 `left`	查找“第一个满足条件的位置”
✅ 写法2：`while (left <= right)`	左右都闭区间 `[left, right]`	`left <= right`	`mid = left + (right - left) / 2` 如果条件不满足则 `right = mid - 1`	最后返回 `left` 或 `right`，取决于逻辑	查找“是否存在某个值”

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

二分搜索板题

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int i = 0;
        int j = nums.length-1;
        while(i <= j){
            int mid = i + (j - i)/2;
            if(nums[mid] == target){
                int start = mid;
                int end = mid;
                while(start-1 >=0 && nums[start-1] == target) start --;
                while(end+1<=nums.length-1 && nums[end+1] == target) end++;
                return new int[]{start,end};
            }else if(nums[mid] < target){
                i = mid +1;
            } else{
                j = mid - 1;
            }
        }
        return new int[]{-1,-1};
    }
}

栈

有效的括号

维护一个符号栈

class Solution {
    public boolean isValid(String s) {
        //维护一个栈
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(':
                    stack.addLast(c);
                    break;
                case ')':
                    if (stack.isEmpty() ||stack.peekLast() != '(')
                        return false;
                    stack.removeLast();
                    break;
                case '[':
                    stack.addLast(c);
                    break;
                case ']':
                    if (stack.isEmpty() || stack.peekLast() != '[')
                        return false;
                    stack.removeLast();
                    break;
                case '{':
                    stack.addLast(c);
                    break;
                case '}':
                    if (stack.isEmpty() || stack.peekLast() != '{')
                        return false;
                    stack.removeLast();
                    break;
                default:
                    return false;
            }
            ;

        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

最小栈

在每个节点入栈时，维护当前入栈时的最小值

class MinStack {
Stack<int[]> s1;

    public MinStack() {
        s1 = new Stack<>();
    }
    
    public void push(int val) {
        if(!s1.isEmpty()){
            int[] t = s1.peek();
            if(val < t[1]){
                s1.push(new int[]{val,val});
            } else {
                s1.push(new int[]{val,t[1]});
            }
        } else {
            s1.push(new int[]{val,val});
        }
    }
    
    public void pop() {
        int[] t = s1.pop();
    }
    
    public int top() {
        int[] t = s1.peek();
        return t[0];
    }
    
    public int getMin() {
        int[] t = s1.peek();
        return t[1];
    }
}

每日温度

还是维护一个单调栈，栈里面的pair对分别为index和nums[index]

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //维护一个单调递减的栈
        Stack<int[]> s = new Stack<>();
        int[] res = new int[temperatures.length];
        for(int i = 0 ;  i< temperatures.length;i++){
            int[] x  = new int[]{temperatures[i], i};
            if(s.isEmpty()){
                s.push(x);
            } else {
                while(!s.isEmpty() && s.peek()[0] < x[0]){
                    int[] t = s.pop();
                    res[t[1]] = i - t[1];
                }
                s.push(x);
            }
        }
        for(int i=0;i<s.size();i++){
            int[] t = s.pop();
            res[t[1]] = 0;
        }
        
        return res;
    }
}

柱状图中的最大矩形

维护两个单调栈

class Solution {
        public int largestRectangleArea(int[] heights) {
        //找到每个位置[i]两侧，第一个小于heights[i]的元素位置。两侧维护单调递增的栈。
        //dp数组维护[i]到两侧的长度
        Stack<int[]> s_l = new Stack<>();
        Stack<int[]> s_r = new Stack<>();
        int n = heights.length;
        int[] r = new int[n];
        int[] l = new int[n];
        for(int i=0; i < n ;i++){
            int j = n - 1 - i;
            int[] x = new int[]{heights[i], i};
            int[] y = new int[]{heights[j], j};
            if(s_r.isEmpty()){
                s_r.push(x);
            } else {
                while(!s_r.isEmpty() && s_r.peek()[0] > x[0]){
                    int[] t = s_r.pop();
                    r[t[1]] = i - t[1];
                }
                s_r.push(x);
            }

            if(s_l.isEmpty()){
                s_l.push(y);
            } else {
                while(!s_l.isEmpty() && s_l.peek()[0] > y[0]){
                    int[] t = s_l.pop();
                    l[t[1]] = t[1] - j ;
                }
                s_l.push(y);
            }
        }
        int s_r_size = s_r.size();
        for(int i = 0 ; i < s_r_size;i++){
            int[] t = s_r.pop();
            r[t[1]] = n  - t[1];
        }
        int s_list_size = s_l.size();
        for(int j = 0 ; j < s_list_size;j++){
            int[] t = s_l.pop();
            l[t[1]] = t[1] + 1;
        }

        int res = Integer.MIN_VALUE;
        for(int k = 0 ; k < n ; k ++){
            if(r[k] == 1 || r[k] == 0){
                r[k] = 0;

            } else {
                r[k] --;
            }
            if(l[k] == 1 || l[k] == 0){
                l[k] = 0;

            } else {
                l[k] --;
            }

        }
        for(int k = 0 ; k < n ; k ++){
            res = Math.max(res, heights[k] * (r[k] + l[k] +1 ));
        }

        return res;

    }
}

堆

数组中的第k个最大元素

定义一个最大堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> p = new PriorityQueue<>((a,b)->b-a);
        for(int n : nums){
            p.offer(n);
        }
        int res = 0;
        for(int i = 0 ; i < k ; i ++){
            res = p.poll();
        }
        return res;
    }
}

前K个高频元素

使用HashMap维护<元素,个数>信息，使用最大堆找到前K个个数最大的元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> p = new PriorityQueue<>((a,b)->b[1]-a[1]);
        HashMap<Integer,Integer> hashMap = new HashMap<>();

        for(int n : nums){
            hashMap.put(n, hashMap.getOrDefault(n,0) + 1);
        }
        for(Map.Entry<Integer,Integer> hash : hashMap.entrySet()){
            int[] o = new int[2];
            o[0] = hash.getKey();
            o[1] = hash.getValue();
            p.offer(o);
        }
        List<Integer> r = new ArrayList<>();
        int cnt = 0;
        while(cnt < k){
            int[] u = p.poll();
            r.add(u[0]);
            cnt++;
        }
        int[] res = new int[r.size()];
        for(int t = 0; t<r.size() ; t++){
            res[t] = r.get(t);
        }
        return res;
    }
}

数据流的中位数

维护一个最大堆表示排序的前半部分，一个最小堆表示排序的后半部分。二者的堆顶即中位数所在的位置。

class MedianFinder {
    PriorityQueue<Integer> preHalf;
    PriorityQueue<Integer> suffHalf;
    public MedianFinder() {
        preHalf = new PriorityQueue<>();
        suffHalf = new PriorityQueue<>((a,b)->b-a);
    }
    
    public void addNum(int num) {
        if(preHalf.size()!=0 &&  num > preHalf.peek()){
            preHalf.offer(num);
            if(preHalf.size() - suffHalf.size() > 1 ){
                suffHalf.offer(preHalf.poll());
            }
        } else{
            suffHalf.offer(num);
            if(suffHalf.size() - preHalf.size() > 1 ){
                preHalf.offer(suffHalf.poll());
            }
        }
    }
    
    public double findMedian() {
        int preCnt = preHalf.size();
        int sufCnt = suffHalf.size();
        if((preCnt + sufCnt) % 2 == 1){
            if(preCnt > sufCnt) return preHalf.peek();
            else return suffHalf.peek();
        } else{
            return (preHalf.peek() + suffHalf.peek()) / 2.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

贪心算法

买卖股票的最佳时机

买一次卖一次
卖的时间>买的时间

解法：维护一个从0到i的最小值的dp数组

class Solution {
    public int maxProfit(int[] prices) {
        //维护一个从0到i的最小值的dp
        int n = prices.length;
        if(n==0)
        return 0;
        int[] dp = new int[n]; 
        dp[0] = prices[0];
        int res = Integer.MIN_VALUE;
        for(int i = 1 ; i < n ; i ++){
            dp[i] = Math.min(prices[i] , dp[i-1]);
            res = Math.max(res, prices[i] - dp[i]);
        }
        return res < 0 ? 0 : res;
    }
}

跳跃游戏

用dp[i]维护i+nums[i]的地点是否可达

class Solution {
    public boolean canJump(int[] nums) {
        //dp的含义为维护一个i所在的地点是否可达
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for(int i = 0 ; i < nums.length;i++){
            if(dp[i] == 0) return false;
            int step=i+nums[i];
            for(int j = i ; j <= step; j ++){
                if(j<nums.length)
                    dp[j] =1;
            }
        }
        return true;
         
    }
}

跳跃游戏II

和跳跃游戏I类似，dp[i]要维护到i这个地点所有的步数的最小值

class Solution {
    public int jump(int[] nums) {
        //dp[i]维护到i所用的步数
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < n; i ++){
            int step = i + nums[i];
            for(int j = i ; j <= step ; j++){
                if(j < n){
                    dp[j] = Math.min(dp[j],dp[i]+1); 
                }
            }
            
        }
        return dp[n-1];
    }
}

划分字母区间

题目的意思是一个字母只能在一个区间内出现
这实际上就是区间合并

class Solution {
    public List<Integer> partitionLabels(String s) {
        //1.获得每个字符的左右边界
        HashMap<Character,int[]> hashMap = new HashMap<>();
        int n = s.length();
        for(int i = 0 ; i < n ; i ++){
            char c = s.charAt(i);
            if(hashMap.containsKey(c)){
                int[] seg = hashMap.get(c);
                seg[1] = i;
                hashMap.put(c,seg);
            } else {
                int[] seg = new int[]{i,i};
                hashMap.put(c,seg);
            }
        }
        int m = hashMap.size();
        int[][] in = new int[m][];
        int p = 0;
        for(Map.Entry<Character,int[]> e : hashMap.entrySet()){
            char e1 = e.getKey();
            int[] e2 = e.getValue();
            in[p] = e2;
            p++;
        }

        //2.将所有区间合并,首先将所有区间按照左界由小到大排序、
        Arrays.sort(in, (a,b) -> Integer.compare(a[0],b[0]));
        List<Integer> res = new ArrayList<>();
        int curLeft = in[0][0];
        int curRight = in[0][1];
        for(int i = 1 ; i < m ; i ++){
            //可以合并
            if(curRight >= in[i][0]){
                curRight = Math.max(curRight,in[i][1]);
            } else { //不能合并
                int len = curRight - curLeft + 1;
                res.add(len);
                curLeft = in[i][0];
                curRight = in[i][1];
            }
        }
        res.add(curRight-curLeft + 1);


        return res;
    }
}

动态规划

爬楼梯

实际上是斐波那契数列

class Solution {
    public int climbStairs(int n) {
        if( n <= 2) 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];
    }
}

杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
            List<Integer> t0 = new ArrayList<>();
            t0.add(1);
            res.add(t0);
        if(numRows == 1){
            return res;
        }
            List<Integer> t1 = new ArrayList<>();
            t1.add(1);
            t1.add(1);
            res.add(t1);
        if(numRows == 2){
            return res;
        }
        
        for(int i = 2 ; i < numRows ; i ++){
            List<Integer> t = new ArrayList<>();
            t.add(1);
            for(int j = 1 ; j < i ; j ++){
                t.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            t.add(1);
            res.add(t);
        }
        return res;   
    }
}

完全平方数之和

这是一个完全背包问题，递推公式为
$$
dp[i] = 1 + min_{j}^{\sqrt{i}} dp[i-j^2]
$$

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i = 1 ; i < n + 1; i ++ ){
            int minn = Integer.MAX_VALUE;
            for(int j = 1 ; j*j<=i;j++){
                minn = Math.min(minn, dp[i - j * j]);
            }
            dp[i] = minn + 1;
        }
        return dp[n];
    }
}

零钱兑换

和完全平方数之和类似，是一个完全背包问题，递推公式为：
$$
dp[i] = 1 + min_{j \in coins} dp[i-j]
$$

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

拆分单词

依然是一个完全背包问题，记录一下，递推公式：

但是需要额外处理一下，dp[i]应该为或的关系，即只要出现满足的单词前缀即可。
$$
dp[i] = dp[i] \ || \ dp[i-t.length()]
$$

class Solution {
   public boolean wordBreak(String s, List<String> wordDict) {
        //还是背包问题
        //分段去截取
        boolean dp[] = new boolean[s.length()+1];
        dp[0] = true;
        for(int j = 1 ; j <= s.length(); j++){
            for(int k = 0 ; k < wordDict.size(); k ++){
                String t = wordDict.get(k);
                if( j - t.length() < 0 )
                    continue;
                if(s.substring( j - t.length(), j).equals(t) && dp[j - t.length()]){

                    dp[j] = dp[j - t.length()];
                }
            }
        }
        return dp[s.length()];

    }
}

最长递增子序列

解法一：维护一个普通的动态规划

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

            dp[i] = t + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

解法二：

二分查找+贪心

维护一个辅助数组 p，它的每一项 p[i] 的含义是，所有长度为 i+1 的上升子序列的末尾元素中的最小值

参考: https://writings.sh/post/longest-increasing-subsequence-revisited

最大乘积子数组

考虑到负数的存在，维护一个最大值和一个最小值（最小值在乘上负数时反而变成最大值）

class Solution {
    public int maxProduct(int[] nums) {
        //维护一个最大值和最小值
        int n = nums.length;
        int[] dp_max = new int[n+1];
        int[] dp_min = new int[n+1];
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];
        int res = nums[0];
        for(int i = 1 ; i < n ; i ++){

            if(nums[i] < 0){
                dp_max[i] = dp_min[i - 1] * nums[i];
                dp_min[i] = dp_max[i - 1] * nums[i]; 
            } else if(nums[i] > 0) {
                dp_max[i] = dp_max[i - 1] * nums[i];
                dp_min[i] = dp_min[i - 1] * nums[i];
            } else {
                dp_max[i] = nums[i];
                dp_min[i] = nums[i];
            }
            dp_max[i] = Math.max(dp_max[i], nums[i]);
            dp_min[i] = Math.min(dp_min[i], nums[i]);
            res = Math.max(dp_max[i],res);
        }
        return res;
    }
}

分割等和子集

01 背包问题的“可达性版本”：

public boolean canPartition(int[] nums) {
        int n = nums.length;

        int sum = 0;
        for(int i = 0 ; i < n ; i ++){
            sum += nums[i];

        }
        if(sum % 2 == 1) return false;
        int[] dp = new int[sum];
        dp[0] = 1;

        int halfSum = sum / 2;
        for(int i = 0 ; i < nums.length ; i ++){
            for(int j = halfSum; j >= nums[i] ; j --){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]);
            }
        }
        return dp[halfSum] == 1 ? true : false;
    }

最长有效括号

首先判断当前位是否能组成括号，是为1，否为0
转为判断最长连续1的问题

class Node{
    char c;
    int index;
    public Node(char c, int index){
        this.c = c;
        this.index = index;
    }
    char getC(){
        return this.c;
    }
    int getIndex(){
        return this.index;
    }
}
class Solution {
    public int longestValidParentheses(String s) {
        //
        int n = s.length();
        if(s.length() == 0) return 0;
        int[] num = new int[n];
        Stack<Node> stack = new Stack<>();
        for(int i = 0 ; i  <  s.length();i++){
            char c = s.charAt(i);
            switch(c){
                case '(' :
                    Node t = new Node(c,i);
                    stack.push(t);
                    break;
                case ')' :
                    if(!stack.isEmpty() && stack.peek().getC() == '('){
                        Node t1 = stack.pop();
                        num[i] = 1;
                        num[t1.getIndex()] = 1;
                    }
                    break;
                default:
                return 0;
            }
        }
        //获得了一个0为不匹配，1为匹配的num[]，现在要求最长的连续1的序列
        int res = 0;
        int temp = 0;
        for(int i = 0 ; i < n ; i ++){
            if(num[i] == 1){
                temp ++;
            } else{
                
                temp = 0;
            }
            res = Math.max(res,temp);

        }
        return res;
    }
}

多维动态规划

不同路径

维护一个二维dp数组，代表到该点时的路径数量

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 0;
        for(int i = 0 ; i < n ; i++){
            dp[0][i] = 1;

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

最小路径和

维护一个二维dp数组代表到i,j的最小路径

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1 ; i < m ; i ++){
            dp[i][0] = dp[i-1][0]+ grid[i][0];

        }
        for(int j = 1 ; j < n ; j ++){
            dp[0][j]  = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < m ; i ++){
            for(int  j = 1; j < n ; j ++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

最长公共子序列

public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];  // 使用 (m+1) x (n+1) 的 DP 表，避免边界判断
        
        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];
    }

编辑距离

dp维护为dp代表前n和前m转换需要的最小次数，使用i+1和j+1来处理边界条件

考虑到dp可以从三个方向获得，分别为左上角，上方，左方

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        //dp代表前n和前m转换需要的最小次数
        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 ++){
                char c1 = word1.charAt(i-1);
                char c2 = word2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] =Math.min(dp[i-1][j-1] + 1 , Math.min(dp[i][j-1] + 1 , dp[i-1][j] + 1)) ;
                }
            }
        }
        return dp[m][n];
    }
}

技巧

只出现一次的数字，其他数字

使用异或操作，异或操作的特性：

a ^ a = 0
a ^ 0 = a
异或具有交换律

class Solution {
    public int climbStairs(int n) {
        if( n <= 2) 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];
    }
}

多数元素

多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

采用投票法，意味着在元素抵消的过程中，多数元素必定会留下。

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

            }
        }
        return cur;
    }
}

下一个排列

1.从后向前找到第一个递减的数

2.记录递减的数

3.找到第一个大于记录的数

4.重排记录的数之后的数

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1)
            return;
        //从后向前遍历，找到第一个降序的数字即其应该开始交换的位置
        int flag = 0;
        int i = nums.length -2;
        for(; i >= 0; i --){
            if(nums[i] <nums[i + 1]){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            int m = 0;
            int n = nums.length-1;
            while(m<n){
                int tmp = nums[m];
                nums[m] = nums[n];
                nums[n] = tmp;
                m++;
                n--;
               
            }
             return;
        }
        //记录第一个下降的值，从后向前找到第一个大于下降值的值
        int pre = nums[i];
        int j = nums.length - 1;
        for(; j > i ; j --){
            if(nums[j] > pre){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                break;
            }

        }
        //将i之后的从小到大排序
        Arrays.sort(nums,i+1,nums.length);

    }
}

寻找重复数

将每个数字放到其该放的位置上，如果其该放置的位置上已经有值，则该值为重复数

class Solution {
    public int findDuplicate(int[] nums) {
        for(int i = 0 ; i < nums.length ; i ++){
            while(nums[i] != i + 1){
                if( nums[nums[i] - 1] != nums[i]){
                swap(nums, i, nums[i] - 1);

                } else{
                    return nums[i] ;
                }
            }
        }
        return 0;
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leetcode

#Leetcode

Hot100

https://yicizhang00.github.io/posts/算法题/leetcode/hot100/

作者

Yici Zhang

发布于

2025年8月12日

许可协议

Leetcode(3500-3600) 上一篇

滴滴笔试题下一篇