LeetCode周赛302，这也太卷了，20分钟ak也只有300名……
LeetCode周赛302，这也太卷了，20分钟ak也只有300名……
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
第302场的LeetCode周赛，由千挂科技赞助。进入前100名的可以获得简历内推机会。
这个要求实在是有一些离谱，老梁赛后看了一下，要想要进入前100名，需要在13分钟之内不能有任何错误的前提下ak才行……
我是20分钟ak的，由于不小心错了两次，赛后直接排到300多名了……可见这次比赛确实简单，几乎完全变成了竞速场，另外就是太卷了，能十几分钟ak的，几乎可以断定一定是acm或者是oi的专业选手。
给大家看看评论区里的吐槽：
好了，下面我们来看题吧。
数组能形成多少数对
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：
- 从
nums选出 两个 相等的 整数 - 从
nums中移除这两个整数，形成一个 数对
请你在 nums 上多次执行此操作直到无法继续执行。
返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。
题解
这题的数据范围太小，基本上怎么玩都可以。可以用map对数进行聚合，也可以像我一样排序之后操作。
纯水题，没难度。
class Solution {
public:
vector<int> numberOfPairs(vector<int>& nums) {
vector<int> ret;
sort(nums.begin(), nums.end());
int p = 0, l = 0;
int i = 0;
while (i < nums.size()) {
if (i+1 < nums.size() && nums[i] == nums[i+1]) {
p++;
i += 2;
}else {
l++;
i++;
}
}
ret.push_back(p);
ret.push_back(l);
return ret;
}
};
数位和相等数对的最大和
给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。
题解
上一题的变体，需要我们先算出每一个数字的数位和，然后根据数位和进行聚合。看起来似乎有些麻烦，聚合之后还要排序选出两个最大的。这样做当然也可以。
但实际上我们要算的是两个数构成的最大值，也就是说是最大值和次大值的和。我们只需要通过map存储数位和对应的最大值即可，然后用当前值和map中的最大值更新答案。原理很简单，在遍历的过程当中，无非两种情况，一种是先遇到次大值再遇到最大值。这种情况在遇到最大值时，map中的是次大值，相加就是答案。如果是先遇到最大值再遇到次大值则相反，map中的是最大值，当前值是次大值，相加也是答案。
所以我们可以不必那么麻烦将数位和对应的所有值都存下来再排序，只需要保存一个最大值即可。更多细节可以参考代码。
class Solution {
public:
int maximumSum(vector<int>& nums) {
int ret = -1;
map<int, int> mp;
// 计算数位和
auto sum_digits = [&](int x) -> int{
int ret = 0;
while (x > 0) {
ret += x % 10;
x /= 10;
}
return ret;
};
for (auto x : nums) {
int d = sum_digits(x);
// 如果已经在map中
if (mp.count(d)) {
// 将map中的最大值与当前值相加
ret = max(ret, x + mp[d]);
// 更新map
mp[d] = max(mp[d], x);
}else mp[d] = x;
}
return ret;
}
};
裁剪数字后查询第 K 小的数字
给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。
再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：
- 将
nums中每个数字 裁剪 到剩下 最右边trimi个数位。 - 在裁剪过后的数字中，找到
nums中第ki小数字对应的 下标 。如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。 - 将
nums中每个数字恢复到原本字符串。
请你返回一个长度与 queries 相等的数组 answer，其中 answer[i]是第 i 次查询的结果。
提示：
- 裁剪到剩下
x个数位的意思是不断删除最左边的数位，直到剩下x个数位。 nums中的字符串可能会有前导 0 。
题解
这题的题目比较长，有一点点弯弯绕，但实际上题目难度并不大，而且数据范围很小，基本上随便玩都行。
所以我们直接按照题意来进行模拟，由于涉及到字符串转换和切片，所以使用Python的话代码非常简单。
class Solution:
def smallestTrimmedNumbers(self, nums: List[str], query: List[List[int]]) -> List[int]:
ret = []
for n, l in query:
cur = sorted([(int(num[-l:]), i) for i, num in enumerate(nums)])
ret.append(cur[n-1][1])
return ret
用C++也一样：
class Solution {
public:
vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int m = queries.size();
int len = nums[0].length();
typedef pair<string, int> pii;
vector<int> ret;
for (int i = 0; i < m; i++) {
int idx = queries[i][0], l = queries[i][1];
vector<pii> cur;
for (int j = 0; j < n; j++) {
string &s = nums[j];
string v = s.substr(len - l);
cur.emplace_back(v, j);
}
sort(cur.begin(), cur.end());
ret.push_back(cur[idx-1].second);
}
return ret;
}
};
使数组可以被整除的最少删除次数
给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。
请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。
如果 y % x == 0 ，那么我们说整数 x 整除 y 。
题解
数学题，我们要删除A数组中的一部分元素，使得A中最小的元素可以整除B数组中所有元素。
由于A和B数组的长度可能很大，所以我们必须要进行优化，直接暴力枚举肯定是不行的。怎么优化呢？这里涉及到一个数论知识，如果一个数x可以同时整除a和b，那么x也能整除a和b的最大公约数。推广这个结论，我们可以先求出B数组中所有元素的最大公约数，然后再将A数组排序，从小到大找到可以整除它的元素即可。
求最大公约数可以使用辗转相除法，其实也不用写，在C++当中替我们实现了最大公约数的算法，叫做gcd。我们直接使用就行。
class Solution {
public:
int minOperations(vector<int>& nums, vector<int>& divide) {
int m = divide[0];
for (auto x: divide) m = gcd(m, x);
sort(nums.begin(), nums.end());
int ret = 0;
for (auto x: nums) {
if (m % x == 0) break;
ret ++;
}
return ret == nums.size() ? -1 : ret;
}
};
到这里这几道题就算是讲完了，想必大家也能发现，这一场比赛的题目无论是编码量还是难度都比较小，实打实的手速场。高情商一点发言就是对新手比较友好，思维门槛较低。
好了，关于这一场比赛就聊到这里吧， 喜欢本文的话不要忘记三连~
腾讯云开发者
