LeetCode周赛302,这也太卷了,20分钟ak也只有300名……

大家好,我是梁唐。

今天是周一,我们来聊聊昨天的LeetCode周赛。

昨天是LeetCode周赛的第302场,由千挂科技赞助。进入前100名的可以获得简历内推机会。

这个要求实在是有一些离谱,老梁赛后看了一下,要想要进入前100名,需要在13分钟之内不能有任何错误的前提下ak才行……

我是20分钟ak的,由于不小心错了两次,赛后直接排到300多名了……可见这次比赛确实简单,几乎完全变成了竞速场,另外就是太卷了,能十几分钟ak的,几乎可以断定一定是acm或者是oi的专业选手。

给大家看看评论区里的吐槽:

好了,下面我们来看题吧。

数组能形成多少数对

给你一个下标从 0 开始的整数数组 nums 。在一步操作中,你可以执行以下步骤:

  • nums 选出 两个 相等的 整数
  • nums 中移除这两个整数,形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案,其中 answer[0] 是形成的数对数目,answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

题解

这题的数据范围太小,基本上怎么玩都可以。可以用map对数进行聚合,也可以像我一样排序之后操作。

纯水题,没难度。

  1. class Solution {
  2. public:
  3. vector<int> numberOfPairs(vector<int>& nums) {
  4. vector<int> ret;
  5. sort(nums.begin(), nums.end());
  6. int p = 0, l = 0;
  7. int i = 0;
  8. while (i < nums.size()) {
  9. if (i+1 < nums.size() && nums[i] == nums[i+1]) {
  10. p++;
  11. i += 2;
  12. }else {
  13. l++;
  14. i++;
  15. }
  16. }
  17. ret.push_back(p);
  18. ret.push_back(l);
  19. return ret;
  20. }
  21. };

数位和相等数对的最大和

给你一个下标从 0 开始的数组 nums ,数组中的元素都是 整数。请你选出两个下标 iji != j),且 nums[i] 的数位和 与 nums[j] 的数位和相等。

请你找出所有满足条件的下标 ij ,找出并返回 nums[i] + nums[j] 可以得到的 最大值

题解

上一题的变体,需要我们先算出每一个数字的数位和,然后根据数位和进行聚合。看起来似乎有些麻烦,聚合之后还要排序选出两个最大的。这样做当然也可以。

但实际上我们要算的是两个数构成的最大值,也就是说是最大值和次大值的和。我们只需要通过map存储数位和对应的最大值即可,然后用当前值和map中的最大值更新答案。原理很简单,在遍历的过程当中,无非两种情况,一种是先遇到次大值再遇到最大值。这种情况在遇到最大值时,map中的是次大值,相加就是答案。如果是先遇到最大值再遇到次大值则相反,map中的是最大值,当前值是次大值,相加也是答案。

所以我们可以不必那么麻烦将数位和对应的所有值都存下来再排序,只需要保存一个最大值即可。更多细节可以参考代码。

  1. class Solution {
  2. public:
  3. int maximumSum(vector<int>& nums) {
  4. int ret = -1;
  5. map<int, int> mp;
  6. // 计算数位和
  7. auto sum_digits = [&](int x) -> int{
  8. int ret = 0;
  9. while (x > 0) {
  10. ret += x % 10;
  11. x /= 10;
  12. }
  13. return ret;
  14. };
  15. for (auto x : nums) {
  16. int d = sum_digits(x);
  17. // 如果已经在map中
  18. if (mp.count(d)) {
  19. // 将map中的最大值与当前值相加
  20. ret = max(ret, x + mp[d]);
  21. // 更新map
  22. mp[d] = max(mp[d], x);
  23. }else mp[d] = x;
  24. }
  25. return ret;
  26. }
  27. };

裁剪数字后查询第 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的话代码非常简单。

  1. class Solution:
  2. def smallestTrimmedNumbers(self, nums: List[str], query: List[List[int]]) -> List[int]:
  3. ret = []
  4. for n, l in query:
  5. cur = sorted([(int(num[-l:]), i) for i, num in enumerate(nums)])
  6. ret.append(cur[n-1][1])
  7. return ret

用C++也一样:

  1. class Solution {
  2. public:
  3. vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
  4. int n = nums.size();
  5. int m = queries.size();
  6. int len = nums[0].length();
  7. typedef pair<string, int> pii;
  8. vector<int> ret;
  9. for (int i = 0; i < m; i++) {
  10. int idx = queries[i][0], l = queries[i][1];
  11. vector<pii> cur;
  12. for (int j = 0; j < n; j++) {
  13. string &s = nums[j];
  14. string v = s.substr(len - l);
  15. cur.emplace_back(v, j);
  16. }
  17. sort(cur.begin(), cur.end());
  18. ret.push_back(cur[idx-1].second);
  19. }
  20. return ret;
  21. }
  22. };

使数组可以被整除的最少删除次数

给你两个正整数数组 numsnumsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素,返回 -1

如果 y % x == 0 ,那么我们说整数 x 整除 y

题解

数学题,我们要删除A数组中的一部分元素,使得A中最小的元素可以整除B数组中所有元素。

由于A和B数组的长度可能很大,所以我们必须要进行优化,直接暴力枚举肯定是不行的。怎么优化呢?这里涉及到一个数论知识,如果一个数x可以同时整除a和b,那么x也能整除a和b的最大公约数。推广这个结论,我们可以先求出B数组中所有元素的最大公约数,然后再将A数组排序,从小到大找到可以整除它的元素即可。

求最大公约数可以使用辗转相除法,其实也不用写,在C++当中替我们实现了最大公约数的算法,叫做gcd。我们直接使用就行。

  1. class Solution {
  2. public:
  3. int minOperations(vector<int>& nums, vector<int>& divide) {
  4. int m = divide[0];
  5. for (auto x: divide) m = gcd(m, x);
  6. sort(nums.begin(), nums.end());
  7. int ret = 0;
  8. for (auto x: nums) {
  9. if (m % x == 0) break;
  10. ret ++;
  11. }
  12. return ret == nums.size() ? -1 : ret;
  13. }
  14. };

到这里这几道题就算是讲完了,想必大家也能发现,这一场比赛的题目无论是编码量还是难度都比较小,实打实的手速场。高情商一点发言就是对新手比较友好,思维门槛较低。

好了,关于这一场比赛就聊到这里吧,感谢大家的阅读,我们周日赛场上见。


原文连接:https://juejin.cn/post/7121894620593651742

相关推荐

翟佳:高可用、强一致、低延迟——BookKeeper的存储实现

管正雄:基于预训练模型、智能运维的QA生成算法落地

814. 二叉树剪枝 : 简单递归运用题

【综合笔试题】难度 3.5\u002F5,多解法热门二叉树笔试题

【java刷算法】牛客—剑指offer3栈、数组、递归、二分法的初步练习

leetcode 2342. Max Sum of a Pair With Equal Sum of Digits (python)

22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

随机数索引(一题双解)【Leetcode每日(4.25)一题】C++

1260. 二维网格迁移 : 简单构造模拟题

坚持用C++刷牛客题(剑指offer专题)

日拱一卒,麻省理工教你信息安全和密码学

C语言——三种方式实现学生信息管理

快速排序及优化

萌新也能看懂的KMP算法

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

素数算法(Prime Num Algorithm)

必须收藏!双目立体匹配算法:Patch Match Stereo实用详解教程

有哪些高质量的自学网站?

731. 我的日程安排表 II : 线段树(动态开点)的两种方式

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……