本次我们将深入探讨LeetCode第248周赛中的前三道题目，旨在帮助大家理解题目背后的算法思路，并掌握一些竞赛中常用的解题技巧。LeetCode作为程序员提升算法能力的重要平台，其周赛更是检验和提高编程水平的绝佳机会。通过对本次周赛题目的分析，我们将学习到如何将实际问题转化为算法模型，并运用合适的数据结构和算法进行高效求解。本文将从数组构建、怪物消除到好数计数，逐步剖析每道题目的解题思路和代码实现，希望能对大家的学习和竞赛有所帮助。希望大家可以通过这篇文章能够将LeetCode这种算法的学习模式运用到平时的开发工作中，将业务问题转化成模型问题，并加以解决。
LeetCode 248周赛关键知识点总结
掌握数组操作和构建技巧，提升代码编写能力。
学习如何将实际问题抽象成算法模型，并进行高效求解。
理解贪心算法在解决特定问题中的应用。
熟悉模运算在防止数据溢出中的作用。
掌握动态规划解决好数计数的策略。
提升调试代码和分析问题复杂度的能力。
了解LeetCode竞赛的规则和一些常用的竞赛技巧。
掌握如何利用数据结构和算法来优化代码性能。
LeetCode 248周赛题目解析
构建排列数组：简单数组操作的典范
☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 多模态理解力帮你轻松跨越从0到1的创作门槛☜☜☜
问题描述：给定一个从0开始索引的排列nums（长度为n），构建一个相同长度的数组ans，其中ans[i] = nums[nums[i]]，对于每个0
解题思路：这道题目非常直接，旨在考察对于数组基本操作的理解。我们只需要按照题目描述，遍历给定的nums数组，然后根据nums[i]的值作为索引，去nums数组中取出对应的元素，并将其赋值给ans数组的对应位置即可。这个过程可以用一个简单的循环实现。
代码实现：
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
};
代码解释： 这段C++代码首先获取输入数组nums的大小，然后创建一个大小相同的ans数组。接着，它使用一个for循环遍历nums数组，对于每个索引i，它将nums[nums[i]]的值赋给ans[i]。最后，返回构建好的ans数组。
复杂度分析：
- 时间复杂度：O(n)，其中n是数组nums的长度，因为我们需要遍历一次nums数组。
- 空间复杂度：O(n)，因为我们需要创建一个大小为n的额外数组ans来存储结果。
总结：构建排列数组这道题目，是一道基础的数组操作题目，难度较低。它的主要目的是考察对于数组索引和赋值操作的熟练程度。通过这道题目的练习，可以巩固对于数组基本概念的理解，并为解决更复杂的数组问题打下基础。
消灭怪物：贪心算法的应用
问题描述：你正在玩一款电子游戏，你需要在游戏中保护你的城市。你得到了一组n个怪物的信息。给你一个下标从0开始的整数数组dist，长度为n，其中dist[i]表示第i个怪物与你的城市的初始距离（单位：米）。怪物的速度是恒定的，每个怪物的速度由一个长度为n的整数数组speed给出，其中speed[i]表示第i个怪物每分钟移动的米数。你有一把武器，可以在每个整数分钟的开始时使用，包括第0分钟。你不能使用武器消灭处于移动过程中的怪物。你每分钟最多只能消灭一个怪物。如果一个怪物在你使用武器之前到达了城市，你就输掉了游戏。如果怪物正好在你开始使用武器的那个时刻到达城市，你也输掉了游戏。返回在不输掉游戏的情况下，你最多可以消灭的怪物数量。
解题思路：这道题目的关键在于使用贪心算法。我们需要计算每个怪物到达城市的时间，然后按照时间从小到大排序。每次选择到达时间最短的怪物进行消除，这样才能保证在有限的时间内尽可能多地消灭怪物。如果某个怪物无法在到达城市之前被消灭，那么游戏就失败了。
代码实现：
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = dist.size();
vector<double> t(n);
for (int i = 0; i < n; i++) {
t[i] = (double)dist[i] / speed[i];
}
sort(t.begin(), t.end());
int total = 0;
for (int i = 0; i < n; i++) {
if (t[i] > i) {
total++;
} else {
break;
}
}
return total;
}
};
代码解释：这段代码首先计算每个怪物到达城市的时间，并存储在t数组中。然后，使用sort函数对t数组进行排序，按照到达时间从小到大排列。接着，使用一个for循环遍历排序后的t数组，对于每个怪物，如果它的到达时间大于当前已经过去的时间i，则表示可以在怪物到达城市之前将其消灭，计数器total加1。如果某个怪物的到达时间小于等于当前已经过去的时间i，则表示无法在怪物到达城市之前将其消灭，游戏失败，循环结束。最后，返回消灭的怪物总数total。
复杂度分析：
- 时间复杂度：O(n log n)，其中n是怪物数量，主要是排序的时间复杂度。
- 空间复杂度：O(n)，因为我们需要创建一个大小为n的额外数组t来存储到达时间。
总结：消灭怪物这道题目，是一道典型的贪心算法题目，属于中等难度。它的主要目的是考察对于贪心算法的理解和应用能力。通过这道题目的练习，可以提升对于问题建模和算法选择的能力。
统计好数：组合数学与模运算
问题描述：如果一个数字字符串是好的，当且仅当该字符串长度为偶数，且偶数位置的数字是偶数，奇数位置的数字是质数（2, 3, 5, 7）。给你一个整数n，返回长度为n的好数字字符串的总数。答案可能很大，请返回它对10^9 + 7取模的结果。
解题思路：这道题目涉及到组合数学和模运算。因为偶数位置只能是偶数，所以每个偶数位置有5种选择（0, 2, 4, 6, 8）。奇数位置只能是质数，所以每个奇数位置有4种选择（2, 3, 5, 7）。因此，如果n是偶数，那么结果就是5的(n/2)次方乘以4的(n/2)次方。如果n是奇数，那么结果就是5的((n+1)/2)次方乘以4的((n-1)/2)次方。为了防止溢出，需要在每一步运算中进行模运算。
代码实现：
class Solution {
public:
#define ll long long
const int M = 1e9+7;
ll mod(ll x){
return ((x%M) + M) % M;
}
ll mul(ll a, ll b){
return mod(mod(a) * mod(b));
}
ll modPow(ll a, ll b){
ll ans = 1ll;
while(b>0){
if(b&1)ans = mul(ans, a);
a = mul(a, a);
b>>=1;
}
return ans;
}
int countGoodNumbers(long long n) {
ll ans = modPow(20ll, (n/2));
if(n%2) ans = mul(ans, 5);
return ans;
}
};
代码解释： 这段代码首先定义了一些辅助函数，包括mod（取模函数）、mul（模乘函数）和modPow（模幂函数）。countGoodNumbers函数首先计算n/2的模幂，然后如果n是奇数，则再乘以5。最后，返回计算结果。
复杂度分析：
- 时间复杂度：O(log n)，主要是模幂运算的时间复杂度。
- 空间复杂度：O(1)，只需要常数级别的额外空间。
总结：统计好数这道题目，是一道组合数学和模运算的题目，属于中等难度。它的主要目的是考察对于组合数学的理解和模运算的应用能力。通过这道题目的练习，可以提升对于数学问题的建模和算法设计的能力。
LeetCode竞赛技巧分享
竞赛准备与策略
LeetCode竞赛不仅考验算法能力，也考验临场发挥和解题策略。以下是一些建议：
- 熟悉平台规则： 了解竞赛的时间限制、提交次数限制等。
- 时间管理： 合理分配时间，先易后难，保证拿到尽可能多的分数。
- 代码调试： 掌握快速调试代码的技巧，例如使用合适的调试工具、编写测试用例等。
- 代码风格： 保持良好的代码风格，方便检查和修改。
- 冷静心态： 遇到难题不要慌张，冷静分析，尝试多种解法。
此外，还可以通过参加模拟赛、阅读题解、与其他参赛者交流等方式来提高竞赛水平。
LeetCode周赛的优缺点分析
? Pros提供了一个检验和提高编程水平的平台。
题目覆盖了各种数据结构和算法，可以帮助你全面提升算法能力。
竞赛氛围可以激发学习兴趣和动力。
可以结识更多志同道合的编程爱好者。
? Cons竞赛题目难度较高，需要长期积累和刻意练习。
时间限制较短，需要快速思考和编写代码。
竞赛结果会影响个人排名和声誉，可能会带来一定的压力。
常见问题解答
LeetCode周赛的难度如何？
LeetCode周赛的难度一般分为简单、中等和困难三个等级。简单题目主要考察基本的数据结构和算法，中等题目需要综合运用多种算法思想，困难题目则需要深入理解算法原理和灵活运用高级技巧。不同水平的选手都可以找到适合自己的题目。
如何提高LeetCode竞赛的水平？
提高LeetCode竞赛水平需要长期积累和刻意练习。一方面，需要系统学习各种数据结构和算法，例如数组、链表、树、图、排序、搜索、动态规划等。另一方面，需要多做题目，积累解题经验，并不断反思和总结。此外，还可以参加模拟赛、阅读题解、与其他参赛者交流等方式来提高竞赛水平。
相关问题拓展
LeetCode中还有哪些值得练习的算法题目？
LeetCode中有很多值得练习的算法题目，可以根据自己的水平和兴趣选择。以下是一些建议： 数组： 两数之和、三数之和、最大子数组和、旋转数组等。 链表： 反转链表、合并两个有序链表、删除链表的倒数第N个节点等。 树： 二叉树的遍历、二叉树的最大深度、二叉树的最近公共祖先等。 图： 图的遍历、最短路径算法、最小生成树算法等。 动态规划： 背包问题、最长公共子序列、编辑距离等。 通过对这些题目的练习，可以全面提升算法能力。
