作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,我是梁唐。
春节假期刚刚过去,不知道大家在这个假期当中有没有刷题参加LeetCode周赛呢?
这一次我们来剖析一下前两天刚刚结束的LeetCode第71场双周赛,这场比赛老梁由于在朋友家做客没能参加,只好赛后第一时间补上了。
好了,咱们废话不多说,一起来看题吧。
给你一个四位 正 整数 num 。请你使用 num 中的 数位 ,将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ,且 num 中 所有 数位都必须使用。
请你返回可以得到的 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 重新排列,使得以下条件均成立:
请你返回重新排列 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;
}
};
常见的微波炉可以设置加热时间,且加热时间满足以下条件:
你可以 最多 输入 4 个数字 来设置加热时间。如果你输入的位数不足 4 位,微波炉会自动加 前缀 0 来补足 4 位。微波炉会将设置好的四位数中,前 两位当作分钟数,后 两位当作秒数。它们所表示的总时间就是加热时间。比方说:
给你整数 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 个元素将会被分成两个 相同大小 的部分。
两部分和的 差值 记为 sumfirst - sumsecond 。
请你返回删除 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;
}
};
这次的第四题有一点巧妙,还需要对优先队列比较熟悉,能够熟练地推导各种情况下的转换和条件,还是很考验人的。
但这样的题目做的过程也是比较爽的,有一点抽丝剥茧层层逼近的感觉,这也是算法和比赛的魅力吧。
好了,关于这次的周赛就聊这么多,感谢大家的阅读,祝大家新春愉快。