hot100整理

hot100整理

哈希

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        for(int num : set){ // 遍历set，否则超时
            if(set.contains(num - 1)){ // 从最小的开始
                continue;
            }
            int last = num + 1;
            while(set.contains(last)){
                last++;
            }
            res = Math.max(res, last - num);
        }
        return res;
    }
}

双指针

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while(left < right){
            int h = Math.min(height[left], height[right]);
            int w = right - left;
            res = Math.max(res, h * w);
            if(height[left] < height[right]){
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}
三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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; i++){
            if(nums[i] > 0){ // 剪枝
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]){ // 去重
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0){
                    right--;
                } else if(sum < 0){
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}
接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int trap(int[] height) {
        // 从栈顶到栈底单调递增，从而判断出凹槽
        int len = height.length;
        if(len <= 2) return 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int res = 0;

        for(int i = 1; i < len; i++){
            int top = stack.peek();
            while(!stack.isEmpty() && height[i] > height[top]){ // 出现凹槽
                int mid = stack.pop();
                if(!stack.isEmpty()){
                    int left = stack.peek();
                    int h = Math.min(height[left], height[i]) - height[mid];
                    int w = i - left - 1;
                    res += h * w;
                    top = stack.peek();
                }
            }
            stack.push(i);
        }
        return res;
    }
}

滑动窗口

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = 0;
        int slow = 0, fast = 0;
        Set<Character> set = new HashSet<>();

        while(fast < s.length()){
            if(set.contains(s.charAt(fast))){
                while(s.charAt(slow) != s.charAt(fast)){
                    set.remove(s.charAt(slow));
                    slow++;
                }
                slow++; // 移动到重复字符后的第一位
                fast++;
            } else {
                set.add(s.charAt(fast));
                fast++;
            } 
            len = Math.max(len, fast - slow);
        }
        return len;
    }
}
找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){
            return res;
        }
        int[] sCount = new int[26]; // 利用小写字母特性
        int[] pCount = new int[26];

        for(int i = 0; i < p.length(); i++){ // 先看开头，初始化p
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if(Arrays.equals(sCount, pCount)){
            res.add(0);
        }

        for(int i = p.length(); i < s.length(); i++){
            sCount[s.charAt(i - p.length()) - 'a']--; // 滑动窗口
            sCount[s.charAt(i) - 'a']++;
            if(Arrays.equals(sCount, pCount)){
                res.add(i - p.length() + 1);
            }
        }

        return res;
    }
}

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, preSum = 0;
        // 哈希表的key为[0,i]之和（前缀和），value为有多少
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for(int i = 0; i < nums.length; i++){
            preSum += nums[i];
            // 寻找有多少个nums[j]与num[i]的差值为k
            if(map.containsKey(preSum - k)){
                count += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}
滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MyQueue { // 该队列应当保证单调递减，相当于使用单调队列
    // 单调队列保证最大值在离开滑动窗口前始终为里面的队首
    // 而其后面出现的次大值不会消亡，在队首离开后成为最大值
    // 其前面出现的次大值被最大值顶替，从而保证队首一定是最大值
    Deque<Integer> queue = new LinkedList<>();

    void poll(int val){ // 只弹出最大值，其前面的值已消亡，其后面的值应当保留
        if(!queue.isEmpty() && val == queue.peek()){
            queue.poll();
        }
    }

    void add(int val){ // 消除前面的次大值，防止其到不了队首
        while(!queue.isEmpty() && val > queue.getLast()){
            queue.removeLast();
        }
        queue.add(val);
    }

    int peek(){ // 前面的操作让滑动窗口的最大值保持在队首
        return queue.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length - k + 1;
        int[] res = new int[len];
        int index = 0;
        MyQueue queue = new MyQueue();

        for(int i = 0; i < k; i++){ // 初始化
            queue.add(nums[i]);
        }
        res[index++] = queue.peek();

        for(int i = k; i < nums.length; i++){
            queue.poll(nums[i - k]);
            queue.add(nums[i]);
            res[index++] = queue.peek();
        }

        return res;
    }
}
最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    // 滑动窗口+哈希表
    public String minWindow(String s, String t) {
        char[] newS = s.toCharArray();
        int resLeft = -1;
        int resRight = s.length();
        int[] count = new int[128]; // 记录字符哈希
        int remain = 0; // 记录有哪些字母出现在t中

        for(char c : t.toCharArray()){
            if(count[c] == 0){
                remain++;
            }
            count[c]++;
        }

        int left = 0, right = 0;
        while(right < s.length()){
            // 右指针移动添加元素
            char c = newS[right];
            count[c]--;
            if(count[c] == 0){ // 这个字母在滑动窗口的数目与t中一致，remain减少以便于判断
                remain--;
            }
            
            while(remain == 0){ // 滑动窗口已出现所有字母，左指针移动
                if(right - left < resRight - resLeft){
                    resLeft = left;
                    resRight = right;
                }
                c = newS[left];
                if(count[c] == 0){ // 注意此时未出现在t中却出现在滑动窗口的字符count为负数
                    remain++;
                }
                count[c]++;
                left++;
            }
            
            right++;
        }

        return resLeft < 0 ? "" : s.substring(resLeft, resRight + 1);
    }
}

普通数组

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        // 只需要反转三次即可
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    private void reverse(int[] nums, int i, int j){
        while(i < j){
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
            i++;
            j--;
        }
    }
}
除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];

        res[len - 1] = 1;
        for(int i = len - 2; i >= 0; i--){
            res[i] = res[i + 1] * nums[i + 1]; // 先计算后面所有数字的乘积
        }

        int pre = 1;
        for(int i = 0; i < len; i++){
            res[i] *= pre; // 再乘上前面所有数字的乘积
            pre *= nums[i];
        }

        return res;
    }
}
缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len; i++){
            // 让数字1在下标0处，数字2在下标1处，以此类推
            while(nums[i] >= 1 && nums[i] <= len && nums[i] != nums[nums[i] - 1]){
                // 交换位置使其回到正确的位置上
                int j = nums[i] - 1;
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }

        for(int i = 0; i < len; i++){
            if(nums[i] != i + 1){ // 第一个不匹配的位置就是答案
                return i + 1;
            }
        }

        return len + 1;
    }
}

矩阵

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public void setZeroes(int[][] matrix) {
        // 使用第一行和第一列来标志有无0
        int m = matrix.length, n = matrix[0].length;
        boolean col0 = false, row0 = false;

        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0){
                col0 = true; // 表示第一列需要全0
            }
        }
        for(int j = 0; j < n; j++){
            if(matrix[0][j] == 0){
                row0 = true; // 表示第一行需要全0
            }
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        if(col0){
            for(int i = 0; i < m; i++){
                matrix[i][0] = 0;
            }
        }
        if(row0){
            for(int j = 0; j < n; j++){
                matrix[0][j] = 0;
            }
        }
    }
}
旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void rotate(int[][] matrix) {
        // 一次转置，一次行翻转即可
        int n = matrix.length;
        // 转置
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){ // 遍历对角线以下元素
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 行翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n / 2; j++){ // 遍历左半部分元素
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 反复使用右上角元素排除
        int i = 0;
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target){
                return true;
            } else if(matrix[i][j] < target){ // 排除第一行
                i++;
            } else { // 排除最后一列
                j--;
            }
        }
        return false;
    }
}

图论

岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){ // 未访问岛屿
                    dfs(grid, i, j); // 将这个岛屿全部访问
                    res++;
                }
            }
        }
        return res;
    }

    private 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'; // 2表示已访问岛屿
        // 上下左右移动
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
    }
}
腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    // 记录移动的方向
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int orangesRotting(int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;
        int fresh = 0; // 记录新鲜橘子数，以判断是否腐烂完
        List<int[]> queue = new ArrayList<>();

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    fresh++;
                } else if(grid[i][j] == 2){ // 初始的腐烂的橘子
                    queue.add(new int[]{i, j});
                }
            }
        }

        int res = 0;
        // 使用广度优先搜索bfs
        while(fresh > 0 && !queue.isEmpty()){
            res++;
            List<int[]> temp = queue;
            queue = new ArrayList<>();
            for(int[] pos : temp){ // 遍历本层中已经腐烂的橘子
                for(int[] d : DIRECTIONS){ // 遍历方向
                    int i = pos[0] + d[0];
                    int j = pos[1] + d[1];
                    if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1){ // 新鲜橘子
                        fresh--;
                        grid[i][j] = 2;
                        queue.add(new int[]{i, j}); // 新的一层中腐烂的橘子
                    }
                }
            }
        }

        return fresh > 0 ? -1 : res;
    }
}
课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 拓扑排序，其实就是判断该有向图是否存在环
        // 使用三色标记法
        // 0：未被访问
        // 1：正在访问，dfs未结束
        // 2：已访问，dfs已返回
        List<Integer>[] graph = new ArrayList[numCourses];
        Arrays.setAll(graph, i -> new ArrayList<>());
        for(int[] pre : prerequisites){
            graph[pre[1]].add(pre[0]); // 使用链表表示该图
        }

        int[] colors = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            if(colors[i] == 0 && dfs(i, graph, colors)){ // 对未访问节点进行深度优先搜索
                return false; // 存在环，无法排序
            }
        }
        return true; // 无环，可以排序
    }

    private boolean dfs(int x, List<Integer>[] graph, int[] colors){
        colors[x] = 1; // 正在访问
        for(int y : graph[x]){
            if(colors[y] == 1 || (colors[y] == 0 && dfs(y, graph, colors))){
                return true; // 找到环
            }
        }
        colors[x] = 2; // 返回
        return false;
    }
}
实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Trie { // 26叉树
    private static class Node{
        Node[] son = new Node[26];
        boolean end; // end表示其前缀组成了一个插入的单词
    }

    private final Node root = new Node();

    public Trie() {
        
    }
    
    public void insert(String word) {
        Node cur = root;
        for(char c : word.toCharArray()){
            c -= 'a';
            if(cur.son[c] == null){ // 插入
                cur.son[c] = new Node();
            }
            cur = cur.son[c];
        }
        cur.end = true;
    }
    
    public boolean search(String word) {
        return find(word) == 2;
    }
    
    public boolean startsWith(String prefix) {
        return find(prefix) != 0;
    }
    
    private int find(String word){
        Node cur = root;
        for(char c : word.toCharArray()){
            c -= 'a';
            if(cur.son[c] == null){ // 没找到
                return 0;
            } cur = cur.son[c];
        }
        // 找到，判断是否是完整的单词
        return cur.end ? 2 : 1;
    }
}

/**
 * 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);
 */

回溯

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    List<String> res = new ArrayList<>();
    // path记录左括号的索引
    List<Integer> path = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        backtracking(n, 0, 0);
        return res;
    }

    // balance等于左括号减右括号
    private void backtracking(int n, int idx, int balance){
        if(path.size() == n){
            char[] temp = new char[2 * n];
            Arrays.fill(temp, ')');
            for(int i : path){
                temp[i] = '(';
            }
            res.add(new String(temp));
            return;
        }

        // 先填i个右括号，再填一个左括号，idx - 1为上一个左括号的下标
        for(int i = 0; i <= balance; i++){
            path.add(idx + i);
            backtracking(n, idx + i + 1, balance - i + 1);
            path.removeLast();
        }
    }
}
单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(backtracking(i, j, 0, board, w)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtracking(int i, int j, int k, char[][] board, char[] word){
        if(board[i][j] != word[k]){
            return false; // 不匹配，回溯
        }

        if(k == word.length - 1){ // 这里减一是因为前面确定了最后一位是匹配的
            return true;
        }

        board[i][j] = 0; // 标记为已访问过

        for(int[] dir : direction){
            int x = i + dir[0];
            int y = j + dir[1];
            if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && backtracking(x, y, k + 1, board, word)){
                return true; // 已找到
            }
        }

        board[i][j] = word[k]; // 恢复
        return false;
    }
}
N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    List<List<String>> res = new ArrayList<>();
    boolean[] usedCol, used45, used135;

    public List<List<String>> solveNQueens(int n) {
        usedCol = new boolean[n]; // 保证不在同一列
        used45 = new boolean[2 * n + 1]; // 保证不在45度斜线内
        used135 = new boolean[2 * n + 1]; // 保证不在135度斜线内
        // 收集结果
        int[] board = new int[n];
        backtracking(board, n, 0);
        return res;
    }

    // 使用行来回溯
    private void backtracking(int[] board, int n, int row){
        if(row == n){
            // 解释结果
            List<String> path = new ArrayList<>();
            for(int i : board){
                char[] str = new char[n];
                Arrays.fill(str, '.');
                str[i] = 'Q';
                path.add(new String(str));
            }
            res.add(path);
            return;
        }

        for(int col = 0; col < n; col++){
            if(usedCol[col] || used45[row + col] || used135[n - 1 - col + row]){ // 不在同一列和同一斜线上
                continue;
            }
            board[row] = col;
            usedCol[col] = true;
            used45[row + col] = true;
            used135[n - 1 - col + row] = true;
            backtracking(board, n, row + 1);
            usedCol[col] = false;
            used45[row + col] = false;
            used135[n - 1 - col + row] = false;
        }
    }
}

栈

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack {
    // 成对保存每个元素，前者为栈中元素，后者为对应的前缀最小值
    private final Deque<int[]> stack = new ArrayDeque<>();

    public MinStack() {
        stack.push(new int[]{0, Integer.MAX_VALUE});
    }
    
    public void push(int val) {
        stack.push(new int[]{val, Math.min(getMin(), val)});
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek()[0];
    }
    
    public int getMin() {
        return stack.peek()[1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int num = 0;
        LinkedList<Integer> stack_num = new LinkedList<>();
        LinkedList<String> stack_char = new LinkedList<>();
        for(char c : s.toCharArray()){
            if(c == '['){ // 入栈
                stack_num.add(num); // 栈顶数字用于翻倍res
                stack_char.add(res.toString()); // 栈底元素为空
                num = 0;
                res = new StringBuilder();
            } else if(c == ']'){ // 出栈
                StringBuilder cur_res = new StringBuilder();
                int cur_num = stack_num.removeLast();
                for(int i = 0; i < cur_num; i++){
                    cur_res.append(res);
                }
                res = new StringBuilder(stack_char.removeLast() + cur_res);
            } else if(c >= '0' && c <= '9'){ // 数字
                num = num * 10 + Integer.parseInt(c + "");
            } else { // 字母
                res.append(c);
            }
        }
        return res.toString();
    }
}
力扣 > hot100
#leetcode #hot100
hot100整理
http://example.com/2025/06/25/hot100整理/
作者
jietiDdd
发布于
2025年6月25日
许可协议