LeetCode周赛283，第一名送iWatch，少年你参赛了吗？
LeetCode周赛283，第一名送iWatch，少年你参赛了吗？
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
老规矩我们来复盘一下第283场的leetcode周赛，赞助商是安贤量化。这次比赛的奖品非常丰富，看得出来是壕气公司。
这次的比赛题目质量也很不错，没有参赛的同学也非常推荐大家赛后练手。这一次由于老梁比赛前一晚熬了夜，所以发挥很差，直到赛前10分钟才做完。
好了，我们废话不多说，直接来看题吧。
Excel表格中某个范围内的单元格
Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：
<col>即单元格的列号c。用英文字母表中的 字母 标识。- 例如，第
1列用'A'表示，第2列用'B'表示，第3列用'C'表示，以此类推。
- 例如，第
<row>即单元格的行号r。第r行就用 整数r标识。
给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1> 表示 c1 列，<row1> 表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。
找出所有满足 r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。
题解
模拟题，由于行和列的范围都很小，列的范围是A-Z，而行的范围是1-9，位数都是确定的，因此直接两重循环遍历即可。
class Solution {
public:
vector<string> cellsInRange(string s) {
vector<string> ret;
for (int i = s[0]; i <= s[3]; i++) {
for (int j = s[1]; j <= s[4]; j++) {
string s {(char) i, (char) j};
ret.push_back(s);
}
}
return ret;
}
};
向数组中追加K个整数
给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
题解
这一题质量不错，不涉及高深算法，但挺考验思维。
我们观察一下数据范围之后会发现范围不小，尤其是K，范围很大有1e9。所以我们模拟的方法，真的去插入K个元素一定会超时。
既然依次插入元素会超时，那么很自然地可以想到批量插入。批量插入的方式也很简单，我们把nums数组排序。排序完了之后依次遍历，计算一下nums数组中相邻两个元素的空档，使用等差数列公式算一下空档当中的元素和即可。
例如第一个样例，排序之后是[1, 4, 10, 25, 25]。1和4中间的空档是[2, 3]，4和10中间的空档是[5, 9]，这些空档当中的元素都是连续可插入的。我们只需要维护一下，保证刚好插入K个即可。
class Solution {
public:
long long minimalKSum(vector<int>& nums, int k) {
long long ret = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
long long l = 1;
for (int i = 0; i < n; i++) {
// 如果已经插入了k个，退出循环
if (k == 0) break;
// 跳过重复元素
if (nums[i] <= l) {
l = nums[i]+1;
continue;
}
// min(nums[i]-1, k-1)，保证不会超过k个
long long r = min((long long) (nums[i]-1), l + (long long)k-1);
// 等差数列求和
ret += (l + r) * (r-l+1) / 2l;
k -= (r - l + 1);
l = nums[i]+1;
}
// 如果遍历结束仍有剩余
if (k > 0) ret += (l + l + k-1) * (long long) k / 2l;
return ret;
}
};
根据描述创建二叉树
给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
- 如果
isLefti == 1，那么childi就是parenti的左子节点。 - 如果
isLefti == 0，那么childi就是parenti的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
测试用例会保证可以构造出 有效 的二叉树。
解法
这是经典的数据结构题，题目当中给了树节点结构体的提示：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
有些同学可能没仔细看注释，所以不知道这题怎么做。因为我们编写的是算法片段，这是为了提示我们树节点的结构体构成。
读一下这段注释中的代码，会发现题目组很贴心地为我们创建了三种构造函数，我们可以很方便地使用。
我们只需要按照题目中的规定，一次遍历每一个节点，把节点之间的链接建立起来，最后返回根节点即可。不过这当中有一些细节需要注意，首先是节点的维护。当我们拿到了一个节点v，它的父节点是u。我们除了创建一个新的v节点之外，还需要找到u节点，将它的某一个子节点指向v。
所以我们得能找到v这个节点，比较妥当的方式是使用一个数据结构map，来存储节点编号和节点对象之间的关联。
这里又有一个小坑点，如果我们的map是定义在函数内部的话，那么map它是一个临时变量。在最后函数返回之后，map当中的元素将会被销毁。这会导致运行错误: heap-use-after-free，即堆内存在释放之后被使用，即使用前被释放。
要解决这个问题主要有两个办法，第一个办法是将这个map放在最外层，作为全局变量，那么它就不会在函数运行结束之后被自动释放。
第二个办法是，map当中存的不再是实例，而是new对象出来的指针。在C++当中，new方法创建的对象在堆内存当中，不会随着函数运行的结束而释放，需要手动通过delete来释放，因此也不会有这个问题。
另外一个小难点是最后返回的是根节点的地址，所以我们还需要找一下根节点。我这里用了比较笨的办法，即维护一个不是根节点的set，最后找到那个不在set中的节点即为根节点。
代码如下：
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& des) {
int n = des.size();
map<int, TreeNode*> mp;
vector<int> vec;
set<int> not_root;
for (int i = 0; i < n; i++) {
auto& vt = des[i];
int p = vt[0];
int v = vt[1];
int l = vt[2];
if (!mp.count(p)) mp[p] = new TreeNode(p);
if (!mp.count(v)) mp[v] = new TreeNode(v);
if (l) mp[p]->left = mp[v];
else mp[p]->right = mp[v];
vec.push_back(p);
vec.push_back(v);
not_root.insert(v);
}
int f = -1;
for (auto x: vec) {
if (!not_root.count(x)) f = x;
}
return mp[f];
}
};
替换数组中的非互质数
给你一个整数数组 nums 。请你对数组执行下述操作：
- 从
nums中找出 任意 两个 相邻 的 非互质 数。 - 如果不存在这样的数，终止 这一过程。
- 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
- 只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
题解
这题看起来很唬人，又是gcd，又是lcm的。
gcd我们之前分享过，一行代码就可以搞定：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
赛后我才知道，其实algorithm头文件当中已经包含了gcd这个函数，所以我们也没必要自己写， 直接调用库函数即可。gcd有了，lcm其实也很好求，a和b的lcm，其实就是a * b / gcd(a, b)。
这题麻烦的地方在于每找到两个gcd大于1的元素都要进行合并操作，就会改变数组中的元素数量。我们都知道修改数组中的元素数量是非常麻烦的，尤其是删除元素的时候，因为会需要移动数组中的其它元素，开销是
。再加上我们需要遍历寻找gcd大于1的相邻元素，又是
的开销，再加上我们要找到所有这样的组合，只遍历一次还不够，需要多遍历几次。所以这样算下来的时间复杂度是一个天文数字，几乎难以想象。
这题的突破口在哪里呢？在于题目中的一个提示：以任意顺序替换相邻的元素得到的结果是一样的。观察一下数据范围，发现数组的元素最多是1e5，在
的限制范围内。
比赛的时候时间很紧，想到了一个取巧的办法。就是采用类似归并的方法，将数组分成两个部分递归去执行合并操作。左右两个部分递归结束之后，再将它们合并到一起。分别从左往右和从右往左遍历一次，寻找可以合并的相邻元素。需要遍历两次的原因是可能一次的遍历不能穷举所有可能，例如：[4, 3, 7, 6, 14]，从左往右执行一次之后，会变成[12, 7, 42]，由于6和14的gcd大于1，并且它们的lcm 42和7的gcd不为1，所以还可以继续执行，因此要执行两次。
得益于Python对于数组切片的支持以及优化，使得整体的复杂度是
。同样的算法逻辑在C++当中就会超时，猜测可能是Python对于切片进行了优化。
class Solution:
def gcd(self, a, b):
return a if b == 0 else gcd(b, a % b)
def forward(self, nums):
n = len(nums)
ret = []
left = nums[0]
for i in range(1, n):
g = gcd(left, nums[i])
if g > 1:
left = left * nums[i] // g
else:
ret.append(left)
left = nums[i]
ret.append(left)
return ret
def dfs(self, vec):
n = len(vec)
if n <= 1:
return vec
m = n // 2
l, r = self.dfs(vec[:m]), self.dfs(vec[m: ])
nums = l + r
# 正向执行一次之后再反向执行一次
return self.forward(self.forward(nums)[::-1])[::-1]
def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
return self.dfs(nums)
赛后看了大佬的题解，发现本题还可以使用栈的方式了搞定，即默认只允许元素从右往左进行执行。每次读入新的元素即从末尾（栈顶）进行执行，如果gcd等于1，即入栈，否则出栈并修改栈顶元素为它们的lcm。
由于每个元素最多出栈一次，所以虽然有两重循环，但复杂度依然是
。
膜拜一下大佬的代码：
class Solution {
public:
vector<int> replaceNonCoprimes(vector<int>& nums) {
vector<int> ans;
for (int num : nums) {
ans.push_back(num);
int n = ans.size();
while (n >= 2 && gcd(ans[n - 2], ans[n - 1]) > 1) {
int r = ans.back();
ans.pop_back();
ans.back() *= r / gcd(ans.back(), r);
n--;
}
}
return ans;
}
};
到这里，关于本次周赛的题目就分析完了，感谢大家的阅读。
喜欢本文的话不要忘记三连~
腾讯云开发者
