惊呆了，LeetCode居然挂了……LeetCode周赛第281场解析
惊呆了，LeetCode居然挂了……LeetCode周赛第281场解析
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
不知道大家参加了上周日的LeetCode周赛没有，发生了一件活久见的事，LeetCode官网居然挂了，不仅是中国区挂了，而是全站都挂了，国际服的竞赛也进不去了……过了好久才恢复。
原本那天有些失眠状态不是很好，加上网站又挂了，所以老梁就没参加。题目是事后补的，所以晚了一天。
好了，咱们废话不多说，来看题吧。
统计各位数之和为偶数的整数个数
难度：零星
给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。
正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
解法
题目范围很小，题意也简单，典型的热身题，对于这样的题目秒切是基本要求。
我们就按照题意实现功能即可，首先实现一个函数用来计算一个整数的各个位数的加和，然后判断一下是否为偶数即可。
代码如下：
class Solution {
public:
bool check(int x) {
int s = 0;
while (x > 0) {
s += x % 10;
x /= 10;
}
return s % 2 == 0;
}
int countEven(int num) {
int cnt = 0;
for (int i = 1; i <= num; i++) cnt += check(i);
return cnt;
}
};
合并零之间的节点
难度：☆至☆☆
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
解法
模拟题，在链表上实现合并节点的功能。
功能本身并不难，对于熟悉链表的同学来说基本没有难度，如果不太熟悉链表，调试可能会有点麻烦。因此难度设置在1到2星之间。
我们很容易可以想到，可以维护一个累加的和以及下一次应该插入的位置。每次遇到0时即进行合并操作，需要注意，累加的和也有可能出现0的情况，需要针对这种情况进行判断，否则会出错。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode* pnt = head->next;
// 维护上一次累加之后的位置
ListNode* last = head;
// 维护累加和
int cnt = 0;
while (pnt->next != nullptr) {
if (pnt->val == 0) {
// 当和不为0时插入新节点
if (cnt != 0) {
last->next = new ListNode(cnt);
last = last->next;
}
// 累加和置0
cnt = 0;
}else {
cnt += pnt->val;
}
pnt = pnt->next;
}
if (cnt != 0) last->next = new ListNode(cnt);
return head->next;
}
};
构造限制重复的字符串
难度：☆☆至☆☆☆
给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。
解法
典型的贪心问题，要使得构造之后的字符串字典序尽量大，那么需要尽量将大的字符放在前面。很容易想到我们可以统计每个字母出现的次数，然后倒序构造字符串。
对于当前最大的字母x来说，可能会出现两种情况。情况一：x出现的次数小于等于repeatLimit，这种情况直接操作，放入所有的x。情况二：x出现的次数大于repeatLimit，此时我们最多连续放入repeatLimit个x。
放入之后并没有结束，我们只需要再插入一个字符又可以接着放入x。但这里涉及一个问题，我们不能保证一定可以找到这样的字符。比如极端情况zzzzzzzzzz，我们就找不到可以用来分隔的字符。所以我们还需要通过枚举来寻找，如果找不到直接退出循环。
整个逻辑稍稍有些复杂，代码会不太那么好写，需要好好整理一下思路再进行编码。
代码如下：
class Solution {
public:
string repeatLimitedString(string s, int rep) {
vector<int> chs(30, 0);
// 统计每个字母出现的次数
for (auto & c: s) chs[c - 'a']++;
vector<pair<int, int>> vt;
// 统计归纳，整理成<字母，出现次数>的格式，并按照字母排序
for (int i = 0; i < 26; i++)
if (chs[i] > 0) vt.push_back(make_pair(i, chs[i]));
string ret = "";
while (vt.size() > 0) {
int p = vt.size() - 1;
int num = min(vt[p].second, rep);
// 判断出现次数是否超过限制
bool full_cap = vt[p].second > rep;
// 尽可能多地放入字符
for (int i = 0; i < num; i++) {
ret.push_back(vt[p].first + 'a');
vt[p].second--;
}
// 如果所有次数已经用完，pop_back
if (vt[p].second == 0) {
vt.pop_back();
}
// 出现次数大于limit，寻找分隔字符
if (full_cap) {
bool flag = false;
for (int i = p-1; i > -1; i--) {
if (vt[i].second > 0) {
flag = true;
vt[i].second--;
ret.push_back('a' + vt[i].first);
break;
}
}
if (!flag) break;
}
}
return ret;
}
};
统计可以被k整除的下标对数目
难度：☆☆☆☆
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：
- 0 <= i < j <= n - 1 且
- nums[i] * nums[j] 能被 k 整除。
解法
注意一下数据范围，1e5，表明不能接受复杂度超过O(n\log n) 的解法，所以暴力的方法一定会超时，我们一定要想办法进行优化。
仔细分析可以发现，我们可以求出nums数组中每一个和k的最大公约数，因为除了最大公约数之外的因子我们并不关心，不会对答案产生影响。所以首先我们可以进行一重转化，将nums数组中的每一个变成它和k的最大公约数。
求解最大公约数可以使用辗转相除法，我们在之前的文章当中介绍过，只需要一行代码就可以实现：
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
求完最大公约数之后， 我们进一步可以想到，对于k的某个约数x而言，如果我们希望它乘上y能够整除k，y必然包含k/x这个因数。由于这里的y是某个数和k的最大公约数，那么我们可以知道y一定也是k的因子。对于任何正整数而言，它的因子都是有限的，并且量级不会超过O(\log n) 。所以我们可以想到可以枚举k的所有因子，统计每一个因子出现的次数。
对于因子m而言，我们首先可以求出和它相乘可以整除k的最小因子l，l=\frac k m 。接着我们遍历所有k的因子，找到能够整除l的因子，它的数量即是可以和m构成答案的数量。但这里需要注意，a和b构成答案，同样b和a也可以，因此要考虑重复的情况。我们不妨限制a和b存在a <= b的大小关系，可以保证不会重复。
其次，当a和b相等时，a不能和a自己构成答案，所以我们需要去掉这种情况。
只要能够想到通过辗转相除法计算最大公约数，剩下的逻辑并不太复杂，只不过要保证计算数量不会重复也不会遗漏，稍稍有一些麻烦，因此难度上多给了一个星。
代码如下：
class Solution {
public:
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
long long countPairs(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> mods(n, 0);
// 求出每个数和k的最大公约数，可以知道，这个结果一定小于等于k
for (int i = 0; i < n; i++) nums[i] = gcd(nums[i], k);
vector<long long> infs;
// 求出所有k的约数，注意，约数不能有重复，需要特判完全平方数
for (int i = 1; i*i <= k; i++) {
if (k % i == 0) {
infs.push_back(i);
if (k / i != i) infs.push_back(k / i);
}
}
map<int, int> mp;
// 统计每个因子出现的次数
for (int i = 0; i < n; i++) mp[nums[i]]++;
long long ret = 0;
// 遍历每一个因子
for (auto m: infs) {
// 计算能够整除k最少需要的乘积
long long left = k / m;
for (auto i: infs) {
// 保证i大于等于m，从而去重
if (i < m) continue;
if (i % left == 0) {
// 如果i=m，需要去掉自己和自己匹配的情况
if (i == m) ret += (long long)mp[i] * (long long)(mp[i] - 1) / (long long)2;
// 否则直接两个数量相乘
else ret += (long long)mp[i] * (long long)mp[m];
}
}
}
return ret;
}
};
最后，我们来看下复杂度，其中辗转相除法的复杂度是O(1) 。我们枚举k的约数用了
，最后使用双重循环枚举了k的因子，由于k的因子数量不超过O(\log k) （没有详细证明），所以双重循环的复杂度最多是O(\log^2 k) ，整合在一起复杂度是O(n) ，所以整个算法是非常快的。
这一次的比赛总体来说难度还可以，最后一题稍稍有点侧重数学，需要一点数论知识，不知道辗转相除法的同学估计做不出来。这也不能怪，本身算法当中也是包含数论的。
好了，关于这次的比赛就先聊到这里，感谢大家的阅读。