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对数进行聚合，也可以像我一样排序之后操作。

纯水题，没难度。

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;
    }
};

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

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