面试喵

主题

LeetCode 热题 100 待完善 ​

LeetCode 热题 100
https://leetcode.cn/studyplan/top-100-liked/

哈希表 ​

两数之和 ​

题目可以理解成，给定 x 找到 target - y 的索引，使用哈希表查找。

key 存值，因为 key 是用来查找的值；value 存放索引。

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

字母异位词分组 ​

java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}
  1. map 使用 put(key, value)，list 使用 add(value)
  2. 字符串按字母排序
  3. map.values() 返回所有映射值的集合视图，再转换成 ArrayList。

最长连续序列 ​

要求是找到最长连续序列。首先使用 Set 去重，再找到每个序列的序列头（判断是否存在 value - 1 的值），向后逐一遍历连续序列。

java
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        int ans = 0;
        for (int n : nums) {
            if (!set.contains(n - 1)) {
                int cnt = 1;
                while (set.contains(n + cnt)) cnt++;
                ans = Integer.max(ans, cnt);
            }
        }
        return ans;
    }
}

双指针 ​

移动零 ​

java
class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int b = 0;
        for (int a = 0; a < len; a++) {
            if (nums[a] != 0) {
                int temp = nums[a];
                nums[a] = nums[b];
                nums[b] = temp;
                b++;
            }
        }
    }
}

盛最多水的容器 ​

面积取决于两个高的最小值和底的宽度。

初始时两个板在两边，向内移动长板，两个高的最小值不变，底的宽度变小，总面积一定变小。（双指针需要找到函数的单调性）

题解：https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do

java
class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int i = 0, j = height.length - 1;
        while (i < j) {
            int h = Integer.min(height[i], height[j]);
            int area = h * (j - i);
            ans = Integer.max(ans, area);
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return ans;
    }
}

三数之和 ​

java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < len - 2; i++) {
            // 对i去重
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            // 使用双指针
            int l = i + 1;
            int r = len - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) {
                    l++;
                } else if (sum > 0) {
                    r--;
                } else {
                    // sum == 0
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 对l去重
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    // 对r去重
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return ans;
    }
}

接雨水 ​

题解视频：LeetCode-42 "臭名昭著"的接雨水问题，三种解法演示+代码～哔哩哔哩 bilibili

当前位置能储存的水量，取决于左边最大高度和右边最大高度。

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

滑动窗口 ​

无重复字符的最长子串 ​

哈希表 + 滑动窗口

java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            while (set.contains(s.charAt(i))) {
                set.remove(s.charAt(i - set.size()));
            }
            set.add(s.charAt(i));
            ans = Integer.max(ans, set.size());
        }
        return ans;
    }
}`

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

字符串排序 + 暴力：O(n2logn)O(n^2 \log n)

Java 实现字符串排序：

java
   char[] charArray = input.toCharArray();
        Arrays.sort(charArray);
   String sortedString = new String(charArray);
java
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] charP = p.toCharArray();
        Arrays.sort(charP);
        String pp = String.valueOf(charP);
        ArrayList<Integer> ans = new ArrayList<>();
        int len = p.length();
        for (int i = 0; i + len - 1 < s.length(); i++) {
            char[] charS = s.substring(i, i + len).toCharArray();
            Arrays.sort(charS);
            String ss = String.valueOf(charS);
            if (ss.equals(pp)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

子串 ​

和为 K 的子数组 ​

前缀和

java
class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] sums = new int[nums.length + 10];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int ans = 0;
        for (int i = nums.length; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (sums[i] - sums[j] == k) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

普通数组 ​

最大子数组和 ​

DP

java
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Integer.max(ans, sum);
        }
        return ans;
    }
}

轮转数组 ​

java
class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[(i + k) % len] = nums[i];
        }
        System.arraycopy(ans, 0, nums, 0, len);
    }
}

除自身以外数组的乘积 ​

前后缀分解

java
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] p = new int[len];
        int[] q = new int[len];
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                p[i] = nums[i];
            } else {
                p[i] = p[i - 1] * nums[i];
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            if (i == len - 1) {
                q[i] = nums[i];
            } else {
                q[i] = q[i + 1] * nums[i];
            }
        }
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                ans[i] = q[i];
            } else if (i == len - 1) {
                ans[i] = p[i];
            } else {
                ans[i] = p[i - 1] * q[i + 1];
            }
        }
        return ans;
    }
}

矩阵 ​

矩阵置零 ​

java
class Solution {
    public void setZeroes(int[][] matrix) {
        ArrayList<int[]> flags = new ArrayList<>();
        // 标记
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    flags.add(new int[]{i, j});
                }
            }
        }
        // 置0
        for (int[] flag : flags) {
            // 行
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[flag[0]][i] = 0;
            }
            // 列
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][flag[1]] = 0;
            }
        }
    }
}

螺旋矩阵 ​

java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        int[][] flag = new int[matrix.length][matrix[0].length];
        int[][] dict = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int currentDict = 0;
        int x = 0, y = 0;
        for (int i = 0; i < matrix.length * matrix[0].length; i++) {
            ans.add(matrix[x][y]);
            flag[x][y] = 1;
            int xx = x + dict[currentDict % 4][0];
            int yy = y + dict[currentDict % 4][1];
            if (xx < 0 || xx >= matrix.length ||
                    yy < 0 || yy >= matrix[0].length
                    || flag[xx][yy] == 1) {
                currentDict++;
                xx = x + dict[currentDict % 4][0];
                yy = y + dict[currentDict % 4][1];
            }
            x = xx;
            y = yy;
        }
        return ans;
    }
}

旋转图像 ​

先上下翻转，再对角线 \ 翻转

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

搜索二维矩阵 II ​

哈希表

java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        HashSet<Integer> set = new HashSet<>();
        for (int[] ints : matrix) {
            for (int i : ints) {
                set.add(i);
            }
        }
        return set.contains(target);
    }
}

链表 ​

相交链表 ​

java
class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodes = new HashSet<>();
        ListNode temp = headA;
        while (temp != null) {
            nodes.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (nodes.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

反转链表 ​

java
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode temp = head;
        ArrayList<ListNode> nodes = new ArrayList<>();
        while (temp != null) {
            nodes.add(temp);
            temp = temp.next;
        }
        for (int i = nodes.size() - 1; i >= 0; i--) {
            if (i != 0) {
                nodes.get(i).next = nodes.get(i - 1);
            } else {
                nodes.get(i).next = null;
            }
        }
        return nodes.get(nodes.size() - 1);
    }
}

回文链表 ​

java
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode temp = head;
        ArrayList<Integer> nodes = new ArrayList<>();
        while (temp != null) {
            nodes.add(temp.val);
            temp = temp.next;
        }
        int len = nodes.size();
        for (int i = 0; i <= len / 2; i++) {
            if (!nodes.get(i).equals(nodes.get(len - i - 1))) {
                return false;
            }
        }
        return true;
    }
}

环形链表 ​

java
class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (set.contains(temp)) {
                return true;
            }
            set.add(temp);
            temp = temp.next;
        }
        return false;
    }
}

环形链表 II ​

java
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (set.contains(temp)) {
                return temp;
            }
            set.add(temp);
            temp = temp.next;
        }
        return null;
    }
}

合并两个有序链表 ​

java
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode temp = ans;
        while (true) {
            if (list1 == null) {
                temp.next = list2;
                break;
            }
            if (list2 == null) {
                temp.next = list1;
                break;
            }
            if (list1.val < list2.val) {
                temp.next = new ListNode(list1.val);
                list1 = list1.next;
                temp = temp.next;
            } else {
                temp.next = new ListNode(list2.val);
                list2 = list2.next;
                temp = temp.next;
            }
        }
        return ans.next;
    }
}

两数相加 ​

java
import java.math.BigInteger;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        while (l1 != null) {
            a.append(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            b.append(l2.val);
            l2 = l2.next;
        }
        a.reverse();
        b.reverse();
        BigInteger ansInt = (new BigInteger(a.toString())).add(new BigInteger(b.toString()));
        String ansStr = ansInt.toString();
        ListNode ansNode = new ListNode();
        ListNode temp = ansNode;
        if (ansStr.equals("0")) {
            return new ListNode(0);
        }
        for (int i = ansStr.length() - 1; i >= 0; i--) {
            temp.next = new ListNode(Integer.parseInt(String.valueOf(ansStr.charAt(i))));
            temp = temp.next;
        }
        return ansNode.next;
    }
}

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

java
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        ArrayList<ListNode> nodes = new ArrayList<>();
        while (temp != null) {
            nodes.add(temp);
            temp = temp.next;
        }
        nodes.remove(nodes.size() - n);
        ListNode ans = new ListNode();
        temp = ans;
        for (ListNode ln : nodes) {
            temp.next = ln;
            temp = temp.next;
        }
        temp.next = null;
        return ans.next;
    }
}

两两交换链表中的节点 ​

java
class Solution {
    public ListNode swapPairs(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        for (int i = 0; i + 1 < list.size(); i += 2) {
            int t = list.get(i);
            list.set(i, list.get(i + 1));
            list.set(i + 1, t);
        }
        ListNode ans = new ListNode();
        temp = ans;
        for (int n : list) {
            temp.next = new ListNode(n);
            temp = temp.next;
        }
        return ans.next;
    }
}

排序链表 ​

java
class Solution {
    public ListNode sortList(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        Collections.sort(list);
        ListNode ans = new ListNode();
        temp = ans;
        for (int i : list) {
            temp.next = new ListNode(i);
            temp = temp.next;
        }
        return ans.next;
    }
}

二叉树 ​

二叉树的中序遍历 ​

前中后是指父节点的顺序

  1. 前序遍历：先输出父节点，再遍历左子树和右子树
  2. 中序遍历：先遍历左子树，再输出父节点，再遍历右子树
  3. 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

通过递归实现

java
class Solution {
    
    public List<Integer> ans = new ArrayList<>();
    
    public void mid(TreeNode node) {
        // 中序: 前 中 后
        if (node != null) {
            mid(node.left);
            ans.add(node.val);
            mid(node.right);
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        mid(root);
        return ans;
    }
}

二叉树的最大深度 ​

java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root != null) {
            return Integer.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
        return 0;
    }
}

翻转二叉树 ​

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

对称二叉树 ​

java
class Solution {
    public boolean sync(TreeNode l, TreeNode r) {
        if (l == null && r == null) return true;
        if (l == null || r == null) return false;
        if (l.val != r.val) {
            return false;
        }
        return sync(l.left, r.right) && sync(l.right, r.left);
    }

    public boolean isSymmetric(TreeNode root) {
        return sync(root.left, root.right);
    }
}

二叉树的直径 ​

java
class Solution {

    int ans = 0;

    int deep(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = deep(node.left);
        int right = deep(node.right);
        ans = Integer.max(left + right, ans);
        return Integer.max(left, right) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return ans;
    }
}

二叉树的层序遍历 ​

java
class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    void dfs(TreeNode node, int deep) {
        if (node == null) {
            return;
        }
        if (ans.size() < deep) {
            ans.add(new ArrayList<>());
        }
        ans.get(deep - 1).add(node.val);
        dfs(node.left, deep + 1);
        dfs(node.right, deep + 1);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 1);
        return ans;
    }
}

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

java
class Solution {

    int[] nums;

    TreeNode dfs(int l, int r) {
        if (l >= r) return null;
        int mid = (l + r) / 2;
        TreeNode node = new TreeNode();
        node.val = nums[mid];
        node.left = dfs(l, mid);
        node.right = dfs(mid + 1, r);
        return node;
    }


    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0, nums.length);
    }
}

验证二叉搜索树 ​

通过中序遍历转换为数组，判断是否有序。

java
class Solution {
    List<Integer> list = new ArrayList<>();

    void mid(TreeNode node) {
        if (node != null) {
            mid(node.left);
            list.add(node.val);
            mid(node.right);
        }
    }

    public boolean isValidBST(TreeNode root) {
        mid(root);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

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

java
class Solution {

    List<Integer> list = new ArrayList<>();

    void mid(TreeNode node) {
        if (node != null) {
            mid(node.left);
            list.add(node.val);
            mid(node.right);
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        mid(root);
        return list.get(k - 1);
    }
}

二叉树的右视图 ​

java
class Solution {

    Map<Integer, Integer> map = new HashMap<>();

    int maxDeep = 0;

    void dfs(TreeNode node, int deep) {
        if (node == null) return;
        map.put(deep, node.val);
        maxDeep = Integer.max(deep, maxDeep);
        dfs(node.left, deep + 1);
        dfs(node.right, deep + 1);
    }

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 1);
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 1; i <= maxDeep; i++) {
            ans.add(map.get(i));
        }
        return ans;
    }
}

二叉树展开为链表 ​

java
class Solution {
    List<Integer> list = new ArrayList<>();

    void pre(TreeNode node) {
        if (node != null) {
            list.add(node.val);
            pre(node.left);
            pre(node.right);
        }
    }

    public void flatten(TreeNode root) {
        pre(root);
        TreeNode node = root;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0) {
                node.left = null;
                node.val = list.get(i);
            } else {
                node.right = new TreeNode(list.get(i));
                node = node.right;
            }
        }
    }
}

图论 ​

岛屿数量 ​

DFS

java
class Solution {
    char[][] grid;

    int[][] dict = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    void dfs(int x, int y) {
        grid[x][y] = '0';
        for (int i = 0; i < 4; i++) {
            int xx = x + dict[i][0];
            int yy = y + dict[i][1];
            if (xx < grid.length && xx >= 0 && yy < grid[0].length && yy >= 0 && grid[xx][yy] == '1') {
                dfs(xx, yy);
            }
        }
    }

    public int numIslands(char[][] grid) {
        this.grid = grid;
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

腐烂的橘子 ​

DFS

java
class Solution {

    static int[][] dict = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    public int orangesRotting(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;


        int times = 0;
        while (true) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 2) {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dict[k][0];
                            int y = j + dict[k][1];
                            if ((x >= 0 && x < n && y >= 0 && y < m) && grid[x][y] == 1) {
                                grid[x][y] = 3;
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 3) {
                        grid[i][j] = 2;
                        cnt++;
                    }
                }
            }
            if (cnt == 0) break;
            times++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return times;
    }
}

回溯 ​

全排列 ​

java
import java.util.ArrayList;
import java.util.List;

class Solution {

    int[] nums;
    boolean[] flag;

    List<List<Integer>> ans = new ArrayList<>();

    void dfs(List<Integer> list) {
        if (list.size() == nums.length) {
            ans.add(list);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                flag[i] = true;
                List<Integer> temp = new ArrayList<>(list);
                temp.add(nums[i]);
                dfs(temp);
                flag[i] = false;
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        flag = new boolean[nums.length];
        dfs(new ArrayList<>());
        return ans;
    }
}

子集 ​

保证不重复，每次加入上次索引以后的元素。

java
import java.util.ArrayList;
import java.util.List;

class Solution {
    int[] nums;
    boolean[] flag;
    List<List<Integer>> ans = new ArrayList<>();

    void dfs(List<Integer> list, int target, int current) {
        if (list.size() == target) {
            ans.add(list);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flag[i] && i > current) {
                flag[i] = true;
                ArrayList<Integer> temp = new ArrayList<>(list);
                temp.add(nums[i]);
                dfs(temp, target, i);
                flag[i] = false;
            }
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        this.flag = new boolean[nums.length];
        for (int i = 0; i <= nums.length; i++) {
            dfs(new ArrayList<>(), i, -1);
        }
        return ans;
    }
}

电话号码的字母组合 ​

java
class Solution {

    String digits;
    List<String> ans = new ArrayList<>();
    Map<Character, String> dic = new HashMap<>();

    void dfs(int cnt, StringBuffer sb) {
        if (cnt == digits.length()) {
            ans.add(String.valueOf(sb));
            return;
        }
        char c = digits.charAt(cnt);
        if (!dic.containsKey(c)) {
            dfs(cnt + 1, new StringBuffer(sb));
        } else {
            for (int i = 0; i < dic.get(c).length(); i++) {
                StringBuffer buffer = new StringBuffer(sb);
                buffer.append(dic.get(c).charAt(i));
                dfs(cnt + 1, buffer);
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) {
            return new ArrayList<>();
        }
        this.digits = digits;
        dic.put('2', "abc");
        dic.put('3', "def");
        dic.put('4', "ghi");
        dic.put('5', "jkl");
        dic.put('6', "mno");
        dic.put('7', "pqrs");
        dic.put('8', "tuv");
        dic.put('9', "wxyz");

        dfs(0, new StringBuffer());
        return ans;
    }
}

括号生成 ​

java
class Solution {
    List<String> ans = new ArrayList<>();
    int n;

    void dfs(StringBuffer sb, int cnt) {
        if (sb.length() == n) {
            if (cnt == 0) {
                ans.add(String.valueOf(sb));
            }
            return;
        }
        // )
        if (cnt >= 1) {
            StringBuffer buffer1 = new StringBuffer(sb);
            buffer1.append(")");
            dfs(buffer1, cnt - 1);
        }
        // (
        StringBuffer buffer2 = new StringBuffer(sb);
        buffer2.append("(");
        dfs(buffer2, cnt + 1);
    }

    public List<String> generateParenthesis(int n) {
        this.n = n * 2;
        dfs(new StringBuffer(), 0);
        return ans;
    }
}

单词搜索 ​

java
class Solution {
    char[][] board;
    boolean[][] flag;
    String word;
    boolean ans = false;
    int[][] dict = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    boolean in(int x, int y) {
        return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
    }

    void dfs(int x, int y, int cnt) {
        if (ans) return;
        if (word.length() == cnt) {
            ans = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dict[i][0];
            int yy = y + dict[i][1];
            if (in(xx, yy) && !flag[xx][yy] && word.charAt(cnt) == board[xx][yy]) {
                flag[xx][yy] = true;
                dfs(xx, yy, cnt + 1);
                flag[xx][yy] = false;
            }
        }
    }

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.flag = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    flag[i][j] = true;
                    dfs(i, j, 1);
                    flag[i][j] = false;
                }
            }
        }
        return ans;
    }
}

二分查找 ​

搜索插入位置 ​

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

搜索二维矩阵 ​

二分

java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int l = 0;
        int r = matrix.length * matrix[0].length;
        while (l < r) {
            int mid = l + r >> 1;
            int mid_v = matrix[mid / matrix[0].length][mid % matrix[0].length];
            if (mid_v == target) {
                return true;
            } else if (mid_v > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
}

哈希表

java
import java.util.HashSet;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        HashSet<Integer> set = new HashSet<>();
        for (int[] ints : matrix) {
            for (int i : ints) {
                set.add(i);
            }
        }
        return set.contains(target);
    }
}

栈 ​

有效的括号 ​

java
class Solution {
    public boolean isValid(String s) {
        String temp = "(){}[]";
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = temp.indexOf(c);
            if (idx % 2 == 0) {
                // 偶数 => 左边
                stack.push(idx);
            } else {
                if (stack.empty()) {
                    return false;
                }
                Integer value = stack.pop();
                if (idx - value != 1) {
                    return false;
                }
            }
        }
        return stack.empty();
    }
}

堆 ​

数组中的第K个最大元素 ​

排序：O(nlogn)O(n\log n)

java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

快排：O(logn)O(\log n)

贪心算法 ​

买卖股票的最佳时机 ​

java
class Solution {
    public int maxProfit(int[] prices) {
        int minValue = prices[0];
        int ans = 0;
        for (int price : prices) {
            minValue = Integer.min(minValue, price);
            ans = Integer.max(ans, price - minValue);
        }
        return ans;
    }
}

跳跃游戏 ​

能跳到第 n 个，必然能到第 n - 1 个

java
class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxJump < i) break;
            maxJump = Integer.max(maxJump, i + nums[i]);
        }
        return maxJump >= nums.length - 1;
    }
}

跳跃游戏 II ​

java
class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        int[] h = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < len; j++) {
                if (h[j] == 0) {
                    h[j] = h[i] + 1;
                } else {
                    h[j] = Integer.min(h[j], h[i] + 1);
                }
            }
        }
        return h[len - 1];
    }
}

动态规划 ​

DP 分析点

递归 + 重复子问题 = DP

爬楼梯 ​

DP 转移方程： $dp[i+1]=dp[i]+dp[i−1] $

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

杨辉三角 ​

java
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
                }
            }
            ans.add(row);
        }

        return ans;
    }
}

打家劫舍 ​

java

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

完全平方数 ​

java
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[10005];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sqrt = (int) Math.sqrt(i);
            int res = (int) Math.pow(sqrt, 2);
            dp[i] = dp[i - res] + 1;
            while (sqrt-- != 0) {
                res = (int) Math.pow(sqrt, 2);
                dp[i] = Math.min(dp[i], dp[i - res] + 1);
            }
        }
        return dp[n];
    }
}

零钱兑换 ​

题解：https://www.bilibili.com/video/BV1qsvDeHEkg/

java
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        if (dp[amount] == amount + 1) {
            return -1;
        } else {
            return dp[amount];
        }
    }
}

单词拆分 ​

java
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] st = new boolean[len + 1];
        st[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= i; j++) {
                String sub = s.substring(j - 1, i);
                if (set.contains(sub) && !st[i]) {
                    st[i] = st[j - 1];
                }
            }
        }
        return st[len];
    }
}

多维动态规划 ​

技巧 ​

只出现一次的数字 ​

异或位运算

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

多数元素 ​

java
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

颜色分类 ​

java
class Solution {
    public void sortColors(int[] nums) {
        int[] cnt = new int[3];
        for (int num : nums) {
            cnt[num]++;
        }
        int p = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                nums[p++] = i;
            }
        }
    }
}

寻找重复数 ​

java
class Solution {
    public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            }
            set.add(num);
        }
        return 0;
    }
}

Released under the MIT License.

code by wmh