算法刷题记录——LeetCode篇(11.1) [第1001~1010题]

更新时间：2025-03-29

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

1001. 网格照明

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [row_i, col_i] 表示 打开 位于 grid[row_i][col_i] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [row_j, col_j] 。对于第 j 个查询，如果单元格 [row_j, col_j] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[row_j][col_j] 上及相邻 8 个方向上（与单元格 grid[row_i][col_i] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]

解释：

• 最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。
• 第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。
• 第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

提示：

• 1 <= n <= 10^9
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == 2
• 0 <= row_i, col_i < n
• queries[j].length == 2
• 0 <= row_j, col_j < n

---

方法：哈希表

1. 数据结构选择：使用四个哈希表分别记录每行、每列、主对角线和副对角线上的灯的数量。同时，使用一个集合来记录所有打开的灯的位置，避免重复处理。
2. 预处理阶段：遍历所有灯的位置，去重后更新对应的行、列、对角线哈希表。
3. 查询处理：对于每个查询点，检查其所在行、列、对角线是否有灯。如果有，则结果为1，否则为0。之后，关闭该点及其周围8个格子内的所有灯，并更新相应的哈希表。

代码实现(Java)：

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> rowCounts = new HashMap<>();
        Map<Integer, Integer> colCounts = new HashMap<>();
        Map<Integer, Integer> diag1Counts = new HashMap<>();
        Map<Integer, Integer> diag2Counts = new HashMap<>();
        Set<Long> lampSet = new HashSet<>();

        for (int[] lamp : lamps) {
            int x = lamp[0];
            int y = lamp[1];
            long key = (long) x * n + y;
            if (lampSet.add(key)) {
                rowCounts.put(x, rowCounts.getOrDefault(x, 0) + 1);
                colCounts.put(y, colCounts.getOrDefault(y, 0) + 1);
                int d1 = x - y;
                diag1Counts.put(d1, diag1Counts.getOrDefault(d1, 0) + 1);
                int d2 = x + y;
                diag2Counts.put(d2, diag2Counts.getOrDefault(d2, 0) + 1);
            }
        }

        int[] ans = new int[queries.length];
        int idx = 0;
        for (int[] query : queries) {
            int x = query[0];
            int y = query[1];
            boolean illuminated = rowCounts.getOrDefault(x, 0) > 0
                    || colCounts.getOrDefault(y, 0) > 0
                    || diag1Counts.getOrDefault(x - y, 0) > 0
                    || diag2Counts.getOrDefault(x + y, 0) > 0;
            ans[idx++] = illuminated ? 1 : 0;

            for (int dx = x - 1; dx <= x + 1; dx++) {
                for (int dy = y - 1; dy <= y + 1; dy++) {
                    if (dx >= 0 && dx < n && dy >= 0 && dy < n) {
                        long key = (long) dx * n + dy;
                        if (lampSet.contains(key)) {
                            lampSet.remove(key);
                          
                            decreaseCount(rowCounts, dx);
                            decreaseCount(colCounts, dy);
                          
                            int d1 = dx - dy;
                            decreaseCount(diag1Counts, d1);
                          
                            int d2 = dx + dy;
                            decreaseCount(diag2Counts, d2);
                        }
                    }
                }
            }
        }
        return ans;
    }

    private void decreaseCount(Map<Integer, Integer> map, int key) {
        int count = map.get(key);
        if (count == 1) {
            map.remove(key);
        } else {
            map.put(key, count - 1);
        }
    }
}

复杂度分析

• 时间复杂度：预处理阶段为O(L)，其中L是灯的数量；每个查询处理时间为O(1)（哈希表操作平均O(1)），总查询时间为O(Q)，其中Q是查询的数量。整体时间复杂度为O(L + Q)。
• 空间复杂度：O(L)，用于存储灯的位置和四个哈希表。

---

1002. 查找共用字符

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2：

输入：words = ["cool","lock","cook"]
输出：["c","o"]

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 由小写英文字母组成

---

方法：数组

1. 统计初始频率：使用第一个字符串的字符频率初始化最小频率数组。
2. 更新最小频率：遍历后续每个字符串，统计当前字符串的字符频率，并与当前最小频率比较，取较小值更新最小频率。
3. 生成结果：根据最终的最小频率数组，将每个字符按次数添加到结果列表中。

代码实现(Java)：

class Solution {
    public List<String> commonChars(String[] words) {
        int[] minFreq = new int[26];
        // 初始化第一个单词的字符频率
        for (char c : words[0].toCharArray()) {
            minFreq[c - 'a']++;
        }
      
        // 遍历后续单词，更新最小频率
        for (int i = 1; i < words.length; i++) {
            int[] currentFreq = new int[26];
            for (char c : words[i].toCharArray()) {
                currentFreq[c - 'a']++;
            }
            // 比较并更新最小频率
            for (int j = 0; j < 26; j++) {
                minFreq[j] = Math.min(minFreq[j], currentFreq[j]);
            }
        }
      
        // 生成结果列表
        List<String> result = new ArrayList<>();
        for (int j = 0; j < 26; j++) {
            if (minFreq[j] > 0) {
                for (int k = 0; k < minFreq[j]; k++) {
                    result.add(String.valueOf((char) ('a' + j)));
                }
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：O(NM + N26)，其中 N 是字符串数组的长度，M 是每个字符串的平均长度。遍历每个字符串的字符需要 O(NM) 时间，更新频率数组需要 O(N26) 时间。
• 空间复杂度：O(26)，使用固定大小的数组存储字符频率，额外空间为常数级。

---

1003. 检查替换后的词是否有效

给你一个字符串 s ，请你判断它是否 有效 。
字符串 s 有效 需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：

• 将字符串 "abc" 插入到 t 中的任意位置。形式上，t 变为 tleft + "abc" + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为 空 。

如果字符串 s 有效，则返回 true；否则，返回 false。

示例 1：

输入：s = "aabcbc"
输出：true

解释：
“” -> “abc” -> “aabcbc”
因此，“aabcbc” 有效。

示例 2：

输入：s = "abcabcababcc"
输出：true

解释：
“” -> “abc” -> “abcabc” -> “abcabcabc” -> “abcabcababcc”
因此，“abcabcababcc” 有效。

示例 3：

输入：s = "abccba"
输出：false

解释：
执行操作无法得到 “abccba” 。

提示：

• 1 <= s.length <= 2 * 10^4
• s 由字母 'a'、'b' 和 'c' 组成

---

方法：栈

要判断字符串是否可以通过不断插入“abc”生成，可以采用栈的方法。每次将字符压入栈后，检查栈顶三个字符是否构成“abc”，若是则弹出这三个字符。最后栈为空则说明字符串有效。

代码实现(Java)：

class Solution {
    public boolean isValid(String s) {
        StringBuilder stack = new StringBuilder();
        for (char c : s.toCharArray()) {
            stack.append(c);
            int len = stack.length();
            if (len >= 3 && stack.substring(len - 3, len).equals("abc")) {
                stack.setLength(len - 3);
            }
        }
        return stack.length() == 0;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中n是字符串长度。每个字符最多被压入和弹出一次。
• 空间复杂度：O(n)，最坏情况下栈存储整个字符串。

---

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6

解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10

解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

---

方法：滑动窗口

为了找到允许翻转最多k个0后，连续1的最大长度，可以使用滑动窗口（双指针）方法。核心思路是维护一个窗口，窗口内最多包含k个0。当窗口内0的数量超过k时，移动左指针缩小窗口，直到满足条件。在此过程中记录窗口的最大长度。

代码实现(Java)：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0; // 窗口左边界
        int maxLen = 0; // 最大长度
        int zeroCount = 0; // 窗口内0的计数
      
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            // 当0的数量超过k时，移动左指针直到0的数量不超过k
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            // 更新最大窗口长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
      
        return maxLen;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中n是数组的长度。每个元素最多被访问两次（右指针和左指针各一次）。
• 空间复杂度：O(1)，仅使用常数级的额外空间。

---

1005. K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5

解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6

解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13

解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 10^4

---

方法：贪心法

优先翻转绝对值较大的负数，以最大化每次翻转带来的增益。若剩余的翻转次数为奇数次，则对绝对值最小的元素进行一次翻转，以最小化损失。

代码实现(Java)：

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 将数组转换为Integer数组以便使用自定义排序
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i];
        }
        // 按绝对值降序排序
        Arrays.sort(arr, (a, b) -> Math.abs(b) - Math.abs(a));
      
        // 处理所有可能的负数值，优先翻转绝对值大的负数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0 && k > 0) {
                arr[i] = -arr[i];
                k--;
            }
        }
      
        // 剩余奇数次翻转时，翻转绝对值最小的元素一次
        if (k % 2 == 1) {
            arr[arr.length - 1] = -arr[arr.length - 1];
        }
      
        // 计算总和
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：O(n log n)，其中n是数组长度。排序的时间复杂度为O(n log n)，后续遍历和计算总和的时间复杂度为O(n)。
• 空间复杂度：O(n)，用于存储转换后的Integer数组。

---

1006. 笨阶乘

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是 地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：

输入：4
输出：7

解释：7 = 4 * 3 / 2 + 1

示例 2：

输入：10
输出：12

解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

提示：

• 1 <= N <= 10000
• -2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数）

---

方法：栈

1. 初始化栈：第一个元素为N。
2. 遍历处理每个数：从N-1到1，根据当前操作符（乘、除、加、减循环）进行处理。
3. 处理乘除：立即计算栈顶元素与当前数的结果，并将结果压入栈。
4. 处理加减：将当前数以正数或负数形式压入栈。
5. 求和：最后将栈中所有元素相加得到最终结果。

代码实现(Java)：

class Solution {
    public int clumsy(int N) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(N);
      
        for (int i = 1; i <= N - 1; i++) {
            int current = N - i;
            int opIndex = (i - 1) % 4;
          
            switch (opIndex) {
                case 0: // 乘法
                    stack.push(stack.pop() * current);
                    break;
                case 1: // 除法
                    stack.push(stack.pop() / current);
                    break;
                case 2: // 加法
                    stack.push(current);
                    break;
                case 3: // 减法（以负数形式入栈）
                    stack.push(-current);
                    break;
            }
        }
      
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：O(N)，每个数被处理一次，且每个操作的时间复杂度为O(1)。
• 空间复杂度：O(N)，栈在最坏情况下需要存储所有数（例如全为加减操作时）。

---

1007. 行相等的最少多米诺旋转

在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。

返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

示例 1：

输入：tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
输出：2

示例 2：

输入：tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
输出：-1

解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。

提示：

• 2 <= tops.length <= 2 * 10^4
• bottoms.length == tops.length
• 1 <= tops[i], bottoms[i] <= 6

---

方法思路

1. 候选数字确定：遍历1到6的每个数字，检查其是否可能成为目标数字。即，对于每个数字x，必须满足每个骨牌的顶部或底部至少有一个是x。
2. 旋转次数计算：对于每个候选数字x，分别计算将顶部全变为x和底部全变为x所需的旋转次数，取较小值。
3. 结果选择：在所有候选数字中找到最小旋转次数，若无有效候选则返回-1。

代码实现(Java)：

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int minRot = Integer.MAX_VALUE;
        for (int x = 1; x <= 6; x++) {
            boolean valid = true;
            int topRot = 0, bottomRot = 0;
            for (int i = 0; i < tops.length; i++) {
                int t = tops[i], b = bottoms[i];
                if (t != x && b != x) {
                    valid = false;
                    break;
                }
                if (t != x) topRot++;
                if (b != x) bottomRot++;
            }
            if (valid) {
                minRot = Math.min(minRot, Math.min(topRot, bottomRot));
            }
        }
        return minRot == Integer.MAX_VALUE ? -1 : minRot;
    }
}

复杂度分析

• 时间复杂度：O(6*N)，其中N是数组长度。每个候选数字遍历数组一次。
• 空间复杂度：O(1)，仅使用常数空间存储变量。

---

1008. 前序遍历构造二叉搜索树

给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2:

输入: preorder = [1,3]
输出: [1,null,3]

提示：

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• preorder 中的值 互不相同

---

方法思路

利用前序遍历和二叉搜索树的特性。前序遍历的第一个元素是根节点，后续元素中比根小的属于左子树，比根大的属于右子树。通过递归方式，结合上下界来确定每个节点的左右子树。

代码实现(Java)：

class Solution {
    private int[] preorder;
    private int index;

    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        this.index = 0;
        return build(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode build(int lower, int upper) {
        if (index >= preorder.length) return null;
        int val = preorder[index];
        if (val < lower || val > upper) return null;
        TreeNode root = new TreeNode(val);
        index++;
        root.left = build(lower, val);
        root.right = build(val, upper);
        return root;
    }
}

复杂度分析

• 时间复杂度：O(N)，每个节点仅被访问一次。
• 空间复杂度：O(N)，递归栈的深度在最坏情况下为树的高度，当树退化为链表时达到O(N)。

---

1009. 十进制整数的反码

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

输入：5
输出：2

解释：5 的二进制表示为 “101”，其二进制反码为 “010”，也就是十进制中的 2 。
示例 2：

输入：7
输出：0

解释：7 的二进制表示为 “111”，其二进制反码为 “000”，也就是十进制中的 0 。

示例 3：

输入：10
输出：5

解释：10 的二进制表示为 “1010”，其二进制反码为 “0101”，也就是十进制中的 5 。

提示：

• 0 <= N < 10^9
• 本题与 476：https://leetcode-cn.com/problems/number-complement/ 相同

---

方法思路

要计算十进制整数的反码，需将原数的二进制每一位取反。由于二进制位数可能不同，需构造一个掩码，确保所有有效位取反。

1. 处理特殊情况：当输入为0时，直接返回1。
2. 计算二进制位数：使用 Integer.numberOfLeadingZeros 方法确定最高有效位的位置，进而得到位数。
3. 构造掩码：生成与二进制位数相同长度的全1掩码。
4. 异或运算：将原数与掩码异或，得到反码对应的十进制数。

代码实现(Java)：

class Solution {
    public int bitwiseComplement(int N) {
        if (N == 0) {
            return 1;
        }
        int leadingZeros = Integer.numberOfLeadingZeros(N);
        int k = 32 - leadingZeros;
        int mask = (1 << k) - 1;
        return mask ^ N;
    }
}

复杂度分析

• 时间复杂度：O(1)，位运算和基本算术操作均为常数时间。
• 空间复杂度：O(1)，仅使用固定空间存储变量。

---

1010. 总持续时间可被 60 整除的歌曲

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。

示例 1：

输入：time = [30,20,150,100,40]
输出：3

解释：这三对的总持续时间可被 60 整除：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60

示例 2：

输入：time = [60,60,60]
输出：3

解释：所有三对的总持续时间都是 120，可以被 60 整除。

提示：

• 1 <= time.length <= 6 * 10^4
• 1 <= time[i] <= 500

---

方法思路

要找到数组中满足总持续时间能被60整除的歌曲对，可以利用余数的性质。两个数的余数之和为60或0时，它们的总和是60的倍数。通过统计每个余数的出现次数，快速查找符合条件的配对。

代码实现(Java)：

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] count = new int[60];
        int res = 0;
        for (int t : time) {
            int remainder = t % 60;
            int complement = (60 - remainder) % 60;
            res += count[complement];
            count[remainder]++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N)，仅需遍历数组一次。
• 空间复杂度：O(1)，使用固定大小的数组存储余数统计。

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。