LeetCode竞赛67：题目解析与高效解题策略分享

在算法竞赛的世界里，LeetCode 的 Biweekly Contest 是一场备受瞩目的盛事。它不仅考验着参赛者的编程能力，更挑战着他们的算法思维和问题解决技巧。本文将深入剖析 LeetCode Biweekly Contest 67 的前三道题目，为你提供详细的解题思路、代码示例和高效的解题策略。无论你是 LeetCode 新手还是经验丰富的算法爱好者，相信都能从中受益匪浅，提升你的算法水平和竞赛能力。本次分享着重于LeetCode竞赛解题技巧、算法优化策略以及提高竞赛效率，务必深入理解。

LeetCode 竞赛 67 关键知识点

子序列查找： 掌握在数组中寻找特定长度且具有最大和的子序列的方法。

排序算法应用： 灵活运用排序算法解决实际问题，并注意排序可能带来的负面影响。

滑动窗口技巧： 理解滑动窗口算法，并将其应用于寻找连续递增或递减序列。

坐标几何知识： 运用坐标几何中的距离公式判断圆之间的位置关系，解决炸弹引爆问题。

深度优先搜索 (DFS)： 利用 DFS 探索图结构，寻找最大连通区域。

LeetCode Biweekly Contest 67 题目详细解析

题目一：寻找长度为 K 的最大和子序列

题目描述：给定一个整数数组 nums 和一个整数 k。你需要找到 nums 的一个长度为 k 的子序列，使得该子序列的和最大。

☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜

返回这个子序列。

解题思路：

要找到长度为 k 的最大和子序列，一个直观的想法是：首先对数组进行排序，然后选取最大的 k 个元素。但是，这样做会破坏子序列的原始顺序，不符合题目要求。

为了解决这个问题，我们需要在排序前记录每个元素的原始索引。可以使用一个pair或者一个vector of pairs来存储元素及其索引。排序后，选取最大的 k 个元素，并根据它们原始的索引进行排序，恢复原始顺序。

算法步骤：

1. 创建一个 vector>，存储 nums 中的元素及其索引。
2. 根据元素的值对 vector 进行排序。（注意需要使用合适的排序函数保证结果的正确性）
3. 选取排序后 vector 中最大的 k 个元素。
4. 创建一个新的 vector，存储选取的 k 个元素。
5. 根据原始索引对新的 vector 进行排序。
6. 返回排序后的 vector。

代码示例 (C++)：

class Solution {
public:
    vector maxSubsequence(vector& nums, int k) {
        int n = nums.size();
        vector> a(n);
        for (int i = 0; i < n; i++) {
            a[i].first = nums[i];
            a[i].second = i;
        }
        sort(a.begin(), a.end(), [](const auto& x, const auto& y) {
            return x.first > y.first; // 降序排序
        });

        vector> b(k);
        for (int i = 0; i < k; i++) {
            b[i].first = a[i].first;
            b[i].second = a[i].second;
        }
        sort(b.begin(), b.end(), [](const auto& x, const auto& y) {
            return x.second < y.second; // 升序排序，按索引
        });

        vector c(k);
        for (int i = 0; i < k; i++) {
            c[i] = b[i].first;
        }
        return c;
    }
};

关键词：子序列、排序、索引、最大和、LeetCode竞赛

题目二：寻找抢银行的好日子

题目描述：你是一名计划抢银行的盗贼。给定一个 0 索引的整数数组 security，其中 security[i] 是第 i 天的银行保安数量。日子从 0 开始编号。你还得到一个整数 time。第 i 天是一个好日子去抢银行，如果：

1. 至少有 time 天在第 i 天之前，且保安数量是非递增的。
2. 至少有 time 天在第 i 天之后，且保安数量是非递减的。

请返回所有好日子的索引列表。

解题思路：

本题的核心是找到满足特定递增和递减条件的日子。一种有效的方法是使用滑动窗口。

我们可以维护两个数组：left 和 right。left[i] 表示从第 0 天到第 i 天，保安数量非递增的天数。right[i] 表示从第 n-1 天到第 i 天，保安数量非递减的天数。

然后，遍历数组，检查每一天是否满足 left[i] >= time 且 right[i] >= time。如果满足，则该天是一个好日子。

算法步骤：

1. 创建两个数组 left 和 right，大小为 security.length。
2. 计算 left 数组：从第 1 天开始，如果 security[i] ，则 left[i] = left[i-1] + 1，否则 left[i] = 1。（注意递增还是递减的判断依据）
3. 计算 right 数组：从第 n-2 天开始，如果 security[i] ，则 right[i] = right[i+1] + 1，否则 right[i] = 1。
4. 创建一个结果数组 result。
5. 遍历 security 数组，对于每一天 i，如果 left[i] >= time 且 right[i] >= time，则将 i 添加到 result 中。
6. 返回 result。

代码示例 (C++)：

class Solution {
public:
    vector goodDaysToRobBank(vector& security, int time) {
        int n = security.size();
        vector left(n, 1), right(n, 1);

        for (int i = 1; i < n; ++i) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (security[i] <= security[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

        vector ans;
        for (int i = 0; i < n; ++i) {
            if (left[i] >= time && right[i] >= time) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

关键词：抢银行、好日子、保安数量、非递增、非递减、滑动窗口、LeetCode竞赛

题目三：引爆最多数量的炸弹

题目描述：给你一份炸弹的清单。每个炸弹的范围由一个以炸弹为中心的正圆表示。炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri]。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围。

你可以选择引爆任意一个炸弹。当一个炸弹被引爆时，它会引爆爆炸范围内所有炸弹。引爆的炸弹可以进一步引爆在其爆炸范围内的炸弹。

给定炸弹清单 bombs，返回你可以引爆的最大炸弹数量。

解题思路：

本题的核心是图的遍历。每个炸弹可以看作图中的一个节点，如果炸弹 A 可以引爆炸弹 B，则在 A 和 B 之间存在一条有向边。我们需要找到一个节点，从该节点出发可以访问到的节点数量最多。

可以使用深度优先搜索 (DFS) 来遍历图。从每个节点出发，进行 DFS，记录可以访问到的节点数量。最终，选取可以访问到的节点数量最多的节点。

算法步骤：

1. 创建一个邻接表 adj，表示炸弹之间的引爆关系。adj[i] 存储了所有可以被第 i 个炸弹引爆的炸弹的索引。
2. 遍历 bombs 数组，计算每个炸弹的爆炸范围。对于任意两个炸弹 i 和 j，计算它们之间的距离 dist。如果 dist ，则将 j 添加到 adj[i] 中。
3. 创建一个函数 dfs(int start, vector& visited)，用于执行 DFS。该函数以起始节点 start 和访问标记数组 visited 作为参数。
4. 在 dfs 函数中，首先将 start 标记为已访问。然后，遍历 adj[start] 中的每个邻居节点 neighbor。如果 neighbor 尚未被访问，则递归调用 dfs(neighbor, visited)。
5. 在主函数中，创建一个变量 maxBombs，用于存储最大炸弹数量。遍历 bombs 数组，对于每个炸弹 i，创建一个访问标记数组 visited，并调用 dfs(i, visited)。计算 visited 中 true 的数量，更新 maxBombs。
6. 返回 maxBombs。

代码示例 (C++)：

class Solution {
public:
    int maximumDetonation(vector>& bombs) {
        int n = bombs.size();
        vector> adj(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                long long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
                long long x2 = bombs[j][0], y2 = bombs[j][1];
                long long dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                if (dist <= r1 * r1) {
                    adj[i].push_back(j);
                }
            }
        }

        auto dfs = [&](int start, vector& visited) {
            visited[start] = true;
            int count = 1;
            for (int neighbor : adj[start]) {
                if (!visited[neighbor]) {
                    count += dfs(neighbor, visited);
                }
            }
            return count;
        };

        int maxBombs = 0;
        for (int i = 0; i < n; ++i) {
            vector visited(n, false);
            maxBombs = max(maxBombs, dfs(i, visited));
        }
        return maxBombs;
    }
};

关键技术

• 距离公式：用于判断一个炸弹是否在另一个炸弹的爆炸范围内
• DFS

关键词：炸弹引爆、最大数量、坐标几何、深度优先搜索、LeetCode竞赛

如何有效利用 LeetCode 竞赛提升算法能力

赛前准备：磨刀不误砍柴工

在参加 LeetCode 竞赛前，充分的准备是成功的关键。你需要：

• 夯实基础知识： 扎实的算法和数据结构基础是解决问题的根本。你需要熟练掌握数组、链表、树、图等基本数据结构，以及排序、搜索、动态规划等常用算法。
• 熟悉 LeetCode 平台： 了解 LeetCode 的操作界面、代码提交方式和评判标准，避免因不熟悉平台而浪费时间。
• 练习历年真题： 研究 LeetCode 往期竞赛题目，熟悉题型和难度，掌握常见的解题思路和技巧。

比赛技巧：策略与执行

比赛过程中，合理的策略和高效的执行力至关重要：

• 时间管理： 合理分配时间，优先解决容易得分的题目。如果一道题目长时间没有思路，可以暂时跳过，先解决其他题目。
• 快速阅读理解： 迅速理解题目要求，明确输入输出格式，避免因理解错误而导致错误。
• 清晰的代码风格： 编写清晰、简洁的代码，提高代码的可读性和可维护性，方便调试和优化。
• 充分测试： 在提交代码前，使用 LeetCode 提供的测试用例进行充分测试，确保代码的正确性。

赛后总结：反思与提升

比赛结束后，认真总结经验教训，才能不断进步：

• 分析错误： 仔细分析未通过的测试用例，找出代码中的错误，并进行修改。
• 学习他人代码： 阅读 LeetCode 论坛中其他参赛者的代码，学习不同的解题思路和技巧。
• 总结经验： 总结本次比赛的经验教训，找出自己的不足之处，并在后续的练习中加以改进。

LeetCode 竞赛的优缺点分析

? Pros

提升算法和数据结构能力：LeetCode 竞赛提供了大量的题目，可以帮助你巩固和提升算法和数据结构的基础知识。

锻炼问题解决技巧：竞赛题目往往具有一定的难度和挑战性，可以锻炼你的问题解决技巧和分析能力。

提高编程速度和效率：在竞赛的压力下，你需要快速编写出高质量的代码，这可以帮助你提高编程速度和效率。

学习他人代码：通过阅读 LeetCode 论坛中其他参赛者的代码，你可以学习到不同的解题思路和技巧。

获得认可和机会：在 LeetCode 竞赛中取得好成绩，可以获得一定的认可，并可能获得一些工作机会。

? Cons

时间压力：竞赛需要在有限的时间内解决问题，这可能会带来很大的压力。

难度较高：竞赛题目往往具有一定的难度，对于新手来说可能会感到困难。

过于注重技巧：过度关注竞赛技巧可能会导致忽略基础知识的掌握。

可能产生焦虑：如果过度追求排名，可能会产生焦虑情绪，影响学习效果。

常见问题解答

如何在 LeetCode 竞赛中快速阅读并理解题目？

快速阅读和理解 LeetCode 竞赛题目需要一定的技巧： 快速扫描： 首先快速扫描题目，了解题目的类型和大概内容。 关注关键词： 关注题目中的关键词，例如数组、链表、树、图、排序、搜索等，快速定位题目的考察点。 理解输入输出： 仔细阅读输入输出格式的要求，确保代码的输入输出与题目要求一致。 示例分析： 结合题目提供的示例，理解题目的具体要求。通过分析示例，可以更好地理解题目的细节和约束条件。 此外，多做题，积累经验，也能有效提高阅读和理解题目的速度。

如何优化 LeetCode 代码以提高效率？

优化 LeetCode 代码以提高效率，可以从以下几个方面入手： 选择合适的算法和数据结构： 不同的算法和数据结构适用于不同的场景。在解决问题时，需要选择最合适的算法和数据结构，以提高代码的效率。 减少时间复杂度： 优化代码的时间复杂度，避免使用时间复杂度过高的算法。例如，尽量避免使用嵌套循环，可以使用哈希表等数据结构来降低时间复杂度。 减少空间复杂度： 优化代码的空间复杂度，尽量减少内存的使用。例如，可以使用原地算法，减少额外内存的分配。 使用位运算： 在某些情况下，使用位运算可以提高代码的效率。 代码优化： 对代码进行优化，例如减少函数调用、避免重复计算等。

相关问题拓展

LeetCode 竞赛中常用的数据结构和算法有哪些？

LeetCode 竞赛中常用的数据结构和算法非常广泛，掌握它们是取得好成绩的基础： 数据结构： 数组 (Array)：最基本的数据结构，用于存储相同类型的元素。 链表 (Linked List)：一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。 栈 (Stack)：一种后进先出 (LIFO) 的数据结构。 队列 (Queue)：一种先进先出 (FIFO) 的数据结构。 哈希表 (Hash Table)：一种使用哈希函数将键映射到值的数据结构，用于快速查找。 树 (Tree)：一种分层数据结构，用于存储具有层次关系的数据。 图 (Graph)：一种由节点和边组成的数据结构，用于存储具有复杂关系的数据。 算法： 排序算法 (Sorting Algorithms)：用于将数据按照特定顺序排列，例如冒泡排序、选择排序、插入排序、归并排序、快速排序等。 搜索算法 (Searching Algorithms)：用于在数据集中查找特定元素，例如线性搜索、二分搜索等。 动态规划 (Dynamic Programming)：一种将复杂问题分解为子问题，并逐步求解的算法设计方法。 贪心算法 (Greedy Algorithms)：一种在每一步选择局部最优解，以期望达到全局最优解的算法设计方法。 回溯算法 (Backtracking Algorithms)：一种通过尝试所有可能的解来解决问题的算法设计方法。 图算法 (Graph Algorithms)：用于解决图相关的问题，例如深度优先搜索 (DFS)、广度优先搜索 (BFS)、最短路径算法、最小生成树算法等。 需要根据具体题目选择合适的数据结构和算法，才能高效地解决问题。 关键词：数据结构、算法、排序算法、搜索算法、动态规划、LeetCode竞赛