LeetCode周赛331，思维题训练场
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
不好意思昨天有点事情晚更了一天，我们照惯例来看看上周末的LeetCode周赛。
本次周赛是LeetCode第331场，本场仍然是LeetCode学习福利场。本场比赛的赛题质量不错，不涉及到高深的算法，更多的考验思维以及对于题意的理解。即使是初学者也能得到很好的锻炼。
老梁春节期间休息了一个月，现在再做题也有思维笨拙的感受。思维能力和肌肉一样，需要时长锻炼，大家不要懈怠呀。
从数量最多的堆取走礼物
给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在 k 秒后剩下的礼物数量。
题解
签到题，暴力也一样能通过。
也可以使用优先队列优化，将复杂度降低到
。
class Solution {
public:
long long pickGifts(vector<int>& gifts, int k) {
long long sm = 0;
for (int i = 0; i < k; i++) {
sort(gifts.begin(), gifts.end(), greater<>());
gifts[0] = sqrt(gifts[0]);
}
for (auto &x : gifts) sm += x;
return sm;
}
};
统计范围内的元音字符串数
给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。
每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。
返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。
注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。
题解
前缀和模板题，我们判断一下每个字符串是否符合题意，然后维护一个前缀和用来查询即可。
class Solution {
public:
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
int n = words.size();
vector<int> sm(n+2, 0);
set<char> v{'a', 'e', 'i', 'o', 'u'};
for (int i = 0; i < n; i++) {
string &s = words[i];
if (v.count(s[0]) && v.count(s.back())) {
sm[i+1]++;
}
sm[i+1] += sm[i];
}
vector<int> ret;
for (auto &vt: queries) {
int l = vt[0], r = vt[1]+1;
ret.push_back(sm[r] - sm[l]);
}
return ret;
}
};
打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力
题解
如果范围小的话，不难想到背包问题。本题当中k和n都比较大，直接dp的复杂度太大不能接受。
但除此之外又想不到什么好的办法，很多人到这里就卡住了。既然正面推导走不通，我们可以逆向思维。不方便直接求解，可以从反面思考，枚举答案来进行验证。
沿着这条线展开，可以想到小偷的偷窃能力和能够覆盖的房间数量之间是呈正比的。那么我们可以二分小偷的偷窃能力，也就是二分答案，然后来反向计算最多能覆盖的房间数，来验证是否能够满足题目要求。
由于题目限制了覆盖的房间不能相邻，所以我们要使用dp的思想，分别维护当前房间要不要覆盖两个状态。当我们移动到下一个房间时，我们可以通过上一个房间是否覆盖来求解得到当前状态的值。假设d1表示上一个房间覆盖能覆盖的最大房间数，d2表示不覆盖时最多覆盖的房间数。nd1表示当前房间覆盖对应的房间数，nd2表示当前房间不覆盖对应的房间数。
那么我们可以得到这么几条状态转移：
if m >= x: # 小偷能力值大于等于当前房间
nd1 = d2+1 # 上一个房间没覆盖，当前房间覆盖
nd2 = max(d1, d2) # 从上一个房间取最大值
else:
nd1 = 0 # 当前房间不能覆盖，所以是0
nd2 = max(d1, d2)
我们在二分法当中结合状态转移，就可以搞定了。我个人感觉比较大的阻碍是比较难逆向思考想到二分答案。
class Solution {
public:
int minCapability(vector<int>& nums, int k) {
int n = nums.size();
int l = 0, r = 0;
for (auto x: nums) r = max(r, x);
while (l+1 < r) {
int m = (l + r) >> 1;
int d1 = 0, d2 = 0;
for (auto x: nums) {
if (m >= x) {
int nd2 = max(d2, d1);
int nd1 = d2+1;
d1 = nd1;
d2 = nd2;
}else {
int nd2 = max(d1, d2);
int nd1 = 0;
d1 = nd1;
d2 = nd2;
}
}
if (max(d1, d2) >= k) r = m;
else l = m;
}
return r;
}
};
重排水果
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此，可以根据需要多次执行下述操作：
- 选中两个下标
i和j，并交换basket1中的第i个水果和basket2中的第j个水果。 - 交换的成本是
min(basket1i,basket2j)。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。
题解
这题前半部分比较简单，很容易想到我们可以把两个篮子里的所有水果统计在一起，将每种水果的数量除以2，就是最终每个果篮的情况。如果出现某一种水果数量是奇数，那么则说明无解，返回-1。
得到了最终情况之后，我们再和当前果篮里的水果进行比对，对比下来多余的水果就是需要交换出去的。到这里都很简单，我们只需要把需要交换出去的排序，选取值最小一半进行累加即可。因为只有两个果篮，所以每一个水果要交换去的目标是确定的。按照贪心的思路，一定是交换对面果篮中数值最大的那个，交换的成本就是当前水果的值（因为当前水果是排序之后值最小的一个，一定小于对面被交换的水果）。
但是这里面有一个trick，就是两个水果交换还有第二种可能。就是借助于全局值最小的水果进行。我们假设全局值最小的水果是M，需要交换的两个水果是A和B。如果AB直接交换，那么成本是min(A, B)。如果借助M，那么则是M分别和AB交换，成本是min(A, M) + min(B, M)，由于M是全局最小的水果，所以化简之后，代价是2M。
只要考虑上这种情况，本题就基本没有难度了。
class Solution {
public:
long long minCost(vector<int>& bk1, vector<int>& bk2) {
map<int, int> tot, t1, t2;
int mini = 0x3f3f3f3f;
for (auto x: bk1) tot[x]++, t1[x]++, mini = min(mini, x);
for (auto x: bk2) tot[x]++, t2[x]++, mini = min(mini, x);
for (auto &it: tot) if (it.second % 2) return -1;
vector<int> vt;
for (auto &it: t1) {
int k = it.first;
int m = tot[k] / 2;
if (it.second > m) {
it.second -= m;
for (int i = 0; i < it.second; i++) vt.push_back(k);
}
}
for (auto &it: t2) {
int k = it.first;
int m = tot[k] / 2;
if (it.second > m) {
it.second -= m;
for (int i = 0; i < it.second; i++) vt.push_back(k);
}
}
sort(vt.begin(), vt.end());
long long ret = 0;
for (int i = 0; i < vt.size() / 2; i++) {
ret += min(2 * mini, vt[i]);
}
return ret;
}
};
腾讯云开发者
