LeetCode71场双周赛，新年冲冲冲！
LeetCode71场双周赛，新年冲冲冲！
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
春节假期刚刚过去，不知道大家在这个假期当中有没有刷题参加LeetCode周赛呢？
这一次我们来剖析一下前两天刚刚结束的LeetCode第71场双周赛，这场比赛老梁由于在朋友家做客没能参加，只好赛后第一时间补上了。
好了，咱们废话不多说，一起来看题吧。
第一题
给你一个四位 正 整数 num 。请你使用 num 中的 数位 ，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中 所有 数位都必须使用。
- 比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93]，[23, 92]，[223, 9] 和 [2, 329] 。
请你返回可以得到的 new1 和 new2 的 最小和。
解法
虽然题目当中允许我们使用数字自由组合，但很明显由于需要相加之后的和最小，那么显然将其转化成两个两位数相加最合适。
想到将数字组合成两个两位数相加之后，我们进一步可以想到，要使和最小要尽量让这两个两位数也尽量小。这里我们可以用贪心的思想，将小的数作为十位，大的数作为百位。
AC代码：
class Solution {
public:
int minimumSum(int num) {
vector<int> ns;
// 将num的四位数字拆分出来
for (int i = 0; i < 4; i++) {
int x = num % 10;
ns.push_back(x);
num /= 10;
}
sort(ns.begin(), ns.end());
return ns[0] * 10 + ns[3] + ns[1] * 10 + ns[2];
}
};
第二题
给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：
- 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
- 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
- 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
- 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。对于小于 pivot 的元素，如果 i < j 且 nums[i] < pivot 和 nums[j] < pivot 都成立，那么 pi < pj 也成立。类似的，对于大于 pivot 的元素，如果 i < j 且 nums[i] > pivot 和 nums[j] > pivot 都成立，那么 pi < pj 。
请你返回重新排列 nums 数组后的结果数组。
解法
很容易联想到快排，但快排不能保证等于pivot的数字夹在中间，因此考虑其他解法。
由于题目要求保证重新排序之后的相对位置不变，不难想到我们可以使用三个数组分别存储小于、等于和大于pivot的数字。然后再将这三个数组合并即可。
AC代码：
class Solution {
public:
vector<int> pivotArray(vector<int>& nums, int pivot) {
// left存储小于pivot，mid存储等于pivot，right存储大于pivot的数
vector<int> left, right, mid;
for (auto &x : nums) {
if (x < pivot) left.push_back(x);
else if (x == pivot) mid.push_back(x);
else right.push_back(x);
}
// 将三个数组归并
vector<int> ret;
for (auto &x : left) ret.push_back(x);
for (auto &x : mid) ret.push_back(x);
for (auto &x : right) ret.push_back(x);
return ret;
}
};
第三题
常见的微波炉可以设置加热时间，且加热时间满足以下条件：
- 至少为 1 秒钟。
- 至多为 99 分 99 秒。
你可以 最多 输入 4 个数字 来设置加热时间。如果你输入的位数不足 4 位，微波炉会自动加 前缀 0 来补足 4 位。微波炉会将设置好的四位数中，前 两位当作分钟数，后 两位当作秒数。它们所表示的总时间就是加热时间。比方说：
- 你输入 9 5 4 （三个数字），被自动补足为 0954 ，并表示 9 分 54 秒。
- 你输入 0 0 0 8 （四个数字），表示 0 分 8 秒。
- 你输入 8 0 9 0 ，表示 80 分 90 秒。
- 你输入 8 1 3 0 ，表示 81 分 30 秒。
给你整数 startAt ，moveCost ，pushCost 和 targetSeconds 。一开始，你的手指在数字 startAt 处。将手指移到 任何其他数字 ，需要花费 moveCost 的单位代价。每 输入你手指所在位置的数字一次，需要花费 pushCost 的单位代价。
要设置 targetSeconds 秒的加热时间，可能会有多种设置方法。你想要知道这些方法中，总代价最小为多少。
请你能返回设置 targetSeconds 秒钟加热时间需要花费的最少代价。
请记住，虽然微波炉的秒数最多可以设置到 99 秒，但一分钟等于 60 秒。
解法
这题难度并不大，但trick很多，很容易出错。
有几个隐藏的条件需要注意，由于前导零会自动填充，所以一定是自动填充比手动填充更优，因为手动填0会有开销。其次秒数显示最大值是99，所以60到99秒之间的时间有两种表示方法，一种是以秒数形式表示，如88秒。另外一种是以分秒的形式表示，如1分22秒。第三个隐藏条件是分钟数同样有上限，最多99分钟，所以对于99分99秒这样的时间，不能转换成100分39秒。
所以我们综合一下思路，会发现对于x分钟y秒的时间来说，如果y在60到99之间，那么我们有两种方案，即x分y秒和x+1分和y-60秒。我们只需要判断一下这两种方案的优劣即可。
在编码时需要注意一些细节，如分钟表示时无须考虑前导零，但秒钟表示时需要考虑前导零的情况。如3分0秒，我们需要输入300，即秒钟一定要表示成两位。另外需要注意99分99秒这样的极端情况。
class Solution {
public:
void get_num(vector<int>& nums, int t, bool zero=false) {
// 将t的每一位数字拆分加入nums中，zero表示是否要考虑前导零
vector<int> cur;
while (t > 0) {
cur.push_back(t % 10);
t /= 10;
}
// 插入前导零，保证一定有两位
if (zero) while (cur.size() < 2) cur.push_back(0);
reverse(cur.begin(), cur.end());
for (auto &x : cur) nums.push_back(x);
}
int push_num(vector<int>& nums, int p, int move, int push) {
// 获得输入nums的花费
int ret = 0;
for (auto &x: nums) {
if (x != p) {
p = x;
ret += move;
}
ret += push;
}
return ret;
}
int minCostSetTime(int startAt, int moveCost, int pushCost, int target) {
// 将目标时间转换成分钟和秒数
int minute = target / 60, seconds = target % 60;
int ret = INT_MAX;
// 如果秒数小于40，那么可以表示minute-1:seconds+60的形式
if (seconds < 40 && minute > 0) {
int s = seconds + 60;
int m = minute - 1;
vector<int> nums;
get_num(nums, m);
get_num(nums, s, m > 0 && s < 10);
ret = push_num(nums, startAt, moveCost, pushCost);
}
// 过滤100分钟0秒这种极端情况
if (minute < 100) {
vector<int> nums;
get_num(nums, minute);
get_num(nums, seconds, minute > 0 && seconds < 10);
ret = min(ret, push_num(nums, startAt, moveCost, pushCost));
}
return ret;
}
};
第四题
给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。
你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。
- 前面 n 个元素属于第一部分，它们的和记为 sumfirst 。
- 后面 n 个元素属于第二部分，它们的和记为 sumsecond 。
两部分和的 差值 记为 sumfirst - sumsecond 。
- 比方说，sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。
- 再比方，sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。
请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。
思路
首先观察一下数据范围会发现n的最大范围是1e5，所以排除暴力求解。
接着我们仔细分析一下题意，会发现在删除n个数字之后，直接均分数组，也就是说剩下元素的相对顺序不变。我们可以将删除n个元素均分数组的操作转换成将长度为3n的数组，拆分成n+k和2n-k两个部分，其中0 \le k \le n ，然后在左侧部分删除k个元素，在右侧部分删除n-k个元素。
由于我们要用左侧数组的和减去右侧数组，并且要使得求出的差值最小。那么很容易想到在左侧数组当中我们删除前k大的元素，而右侧数组删除前n-k小的元素。然后我们枚举所有的k，即可找到答案。
但这个方案依然存在时间复杂度过大的问题，因为枚举所有的k意味着前k大和前n-k小都要重新计算，所以我们要针对这种情况做出优化。比较容易想到，我们可以迭代操作。
假设我们已经搞定了k时的情况，当枚举k+1时，对于左侧部分来说，额外读入了一个新的元素nums[k+1]，并且要删除前k+1大的元素。由于枚举k时我们已经删除了k个元素，我们只需要在此基础上再删除一个最大值即可，很容易想到可以通过维护大顶堆的优先队列实现。
但对于右侧的部分来说，正序无法直接推导，但逆序遍历之后操作步骤和左侧部分一样。我们可以维护一个小顶堆同样操作即可。
AC代码：
class Solution {
public:
long long minimumDifference(vector<int>& nums) {
// 大顶堆，维护最大值
priority_queue<long long> maxque;
// 小顶堆，维护最小值
priority_queue<long long, vector<long long>, greater<long long>> minque;
int n = nums.size();
n /= 3;
// 由于要遍历两次，所以使用数组记录其中一次的结果
// arr存储的是左侧数组删除k个元素的和
vector<long long> arr(n+2, 0);
long long leftsum = 0, rightsum = 0;
// leftsum = sum(nums[:n]), rightsum = sum(nums[-n:])
for (int i = 0; i < n; i++) {
leftsum += nums[i];
maxque.push(nums[i]);
rightsum += nums[2*n + i];
minque.push(nums[2*n+i]);
}
long long cursum = leftsum;
for (int i = n; i < 2*n; i++) {
// 插入nums[i]，删除最大值
cursum += nums[i];
maxque.push(nums[i]);
cursum -= maxque.top();
maxque.pop();
arr[i-n] = cursum;
}
long long ret = 0x3f3f3f3f3f3f3f3f;
// 倒序遍历，求右侧数组的和
for (int i = 2*n-1; i >= n; i--) {
// 维护答案
ret = min(ret, arr[i-n] - rightsum);
// 插入nums[i]，删除最小值
rightsum += nums[i];
minque.push(nums[i]);
rightsum -= minque.top();
minque.pop();
}
// 单独处理k=0的情况
ret = min(ret, leftsum - rightsum);
return ret;
}
};
这次的第四题有一点巧妙，还需要对优先队列比较熟悉，能够熟练地推导各种情况下的转换和条件，还是很考验人的。
但这样的题目做的过程也是比较爽的，有一点抽丝剥茧层层逼近的感觉，这也是算法和比赛的魅力吧。
好了，关于这次的周赛就聊这么多，感谢大家的阅读，祝大家新春愉快。