作者 | 梁唐
出品 | 公众号: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;
}
};
给你一个下标从 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;
}
};
到这里这几道题就算是讲完了,想必大家也能发现,这一场比赛的题目无论是编码量还是难度都比较小,实打实的手速场。高情商一点发言就是对新手比较友好,思维门槛较低。
好了,关于这一场比赛就聊到这里吧, 喜欢本文的话不要忘记三连~