LeetCode周赛325，反向思考专场，你有逆向思维吗？
LeetCode周赛325，反向思考专场，你有逆向思维吗？
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天是周一，我们照惯例来聊聊昨天的LeetCode周赛。
昨天是LeetCode周赛第325场，由西门子赞助，前30名可以获得精美礼品。
这一场赛题的质量不错，难度梯度非常好，很有层次。并且思维题居多，没有侧重某种算法或数据结构的考察。
当然这种场次往往意味着难度比较大，我在做的时候也不太顺利，评论区里很多大佬也有类似的感受。
到目标字符串的最短距离
给你一个下标从 0 开始的 环形 字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。
- 形式上，
words[i]的下一个元素是words[(i + 1) % n]，而words[i]的前一个元素是words[(i - 1 + n) % n]，其中n是words的长度。
从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。
返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。
题解
模拟题，比较容易想到，最多移动n次就可以遍历完整个数组里的元素。所以我们只需要枚举一下移动的次数，再使用两个变量分别记录往左和往右移动i步之后的下标即可。
class Solution {
public:
int closetTarget(vector<string>& words, string target, int startIndex) {
int l = startIndex-1, r = startIndex+1;
int n = words.size();
for (int i = 0; i < n; i++) {
l = (l+1) % n;
r = (r-1+n) % n;
if (words[l] == target || words[r] == target) return i;
}
return -1;
}
};
每种字符至少取 K 个
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
题解
滑动窗口或者是两指针问题。
首先，如果整个字符串中的abc数量不足k个，那么肯定无解。假设存在一个一般解，取s[:l]以及s[r:]之后满足题意。我们很容易找到当r=n时，也就是右侧不取，全部从左侧获取时的l。
之后考虑将l往左移动，来寻找更优的情况。当l往左移动时，区间s[l:]内的元素减少，为了能够满足题意，我们必须要将r也往左移动，这样才能补充字符，从而才有可能满足题意。那么我们剩下要做的就是将l一直往左移动，直到s[l:]为空，此时左侧不取，所有字符都从右侧获得。如此我们就遍历完了所有可能构成答案的情况，维护最值即可。
class Solution {
public:
int takeCharacters(string s, int k) {
if (k == 0) return 0;
int a = 0, b = 0, c = 0;
int n = s.length();
int l = 0;
// 找到最小的l，使得s[l:]满足题意
bool flag = false;
for (l = 0; l < n; l++) {
if (s[l] == 'a') a++;
if (s[l] == 'b') b++;
if (s[l] == 'c') c++;
if (a >= k && b >= k && c >= k) {
flag = true;
break;
}
}
if (!flag) return -1;
int r = n;
int ret = l+1;
// l向左移动
while (l >= 0) {
if (s[l] == 'a') a--;
if (s[l] == 'b') b--;
if (s[l] == 'c') c--;
l--;
// r也向左移动
while (l < r && (a < k || b < k || c < k)) {
r--;
if (s[r] == 'a') a++;
if (s[r] == 'b') b++;
if (s[r] == 'c') c++;
}
if (a >= k && b >= k && c >= k)
ret = min(ret, l+1+n-r);
}
return ret;
}
};
做题时要特别注意下标和循环条件，很容易出错。
礼盒的最大甜蜜度
给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
题解
比较容易想到我们可以先将元素去重和排序，如果去重之后的元素数量不足k个，那么肯定答案是0，说明最后取出的k个数里一定有重复，那么答案一定是0。
去重和排序之后，我们要做的就是找到一个最大的值m，使得我们可以找到k个数，它们所有相邻两数的差值大于等于m。两两差值的最小值一定出现在相邻的元素上，所以我们只需要考虑元素相邻的差值即可。
但问题是即使是去重之后，剩下的元素数量依然可能是1e5这个量级，我们怎么样找到这个最大的m呢？
这里要用到一个技巧，就是反向求解，二分答案。
算法问题的复杂度其实分为两种，一种是求解的复杂度一种是验证的复杂度。在本题当中，我们求解的复杂度很高，但验证的复杂度则相对较低。我们要验证在差值m的情况下是否能够找到k个元素只需要用贪心的方法遍历一次即可。但我们要直接求解这个最大的m则比较棘手，没什么好的突破口。
因此我们可以反向来做，通过二分法来搜索符合题意的最大边界。在搜索边界的问题当中，一般情况下不使用闭区间，而是以半开半闭区间为主，这里我们选择左闭右开区间。
查看下方代码，获得更多细节。
class Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
set<int> st;
for (auto x: price) st.insert(x);
vector<int> vt;
// 去重
for (auto it: st) vt.push_back(it);
if (vt.size() < k) return 0;
// 左闭右开区间，所以右侧要+1
int l = 0, r = (vt.back() - vt[0]) / (k-1) + 1;
int n = vt.size();
while (l+1 < r) {
int m = (l + r) >> 1;
// 从vt[0]开始，每找到比last大m的元素就更新
int cnt = 1, last = vt[0];
for (int i = 1; i < n; i++) {
if (vt[i] >= last + m) {
cnt++;
last = vt[i];
}
}
// cnt >= k，说明满足题意
if (cnt >= k) l = m;
else r = m;
}
return l;
}
};
好分区的数目
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对
取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
题解
又是一道逆向思考的问题，在数据范围很小的情况下，我们要求解元素和对应的情况总数非常简单，只需要使用动态规划即可。
但在本题当中，数据的范围非常大，元素最大为1e9，对应的总和最大为1e12，不论是空间还是时间复杂度我们都无法承受。数据范围是本题的难点，其实也是本题的关键线索。k和元素的数量都相对较小，最多只有1000。那我们完全可以反向求解，找到所有不满足题意的情况，将其从情况总数减去即可。
本题当中对于划分没有任何限制，那么理论上来说将n个元素分成两组，每个元素都有两个选择，因此一共有
种。
我们使用dp[i][j]维护使用了前i个元素的情况下，总和是j的情况总数。显然对于所有小于等于j的x，有dp[i][j] += dp[i-1][j-x]。我们不需要考虑所有的总和，只需要考虑k以内的情况即可。由于总和固定，我们确定了一个分组的情况，另外一个分组也随之确定，情况总数相等。
最后在计算答案的时候要注意，我们假设所有元素的总和是s，对于s - j < k的情况，即两个分组总和都小于k的情况，我们只计算一次。而对于s - j >= k的情况，再减去的时候需要乘2。因为我们只遍历k以内的情况，对于前者，j和s-j都会遍历到，因此只需要计算一次。而对于后者，s-j是遍历不到的，又dp[n][j] == dp[n][s-j]，所以我们要减去双倍。
这道题需要对动态规划比较熟悉，并且能够想到反向求解，计算的时候还要注意很多细节，老实讲并不容易。做完之后我感觉收获还是挺大的，非常锻炼人，值得一试。
class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
typedef long long ll;
typedef pair<ll, ll> pll;
ll Mod = 1e9 + 7;
ll ret = 1;
ll s = 0;
int n = nums.size();
ll dp[n+1][k+1];
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int x = nums[i-1];
for (int j = 0; j < k; j++) {
dp[i][j] = dp[i-1][j];
if (j >= x) {
dp[i][j] = (dp[i][j] + dp[i-1][j-x]) % Mod;
}
}
s += x;
ret = ret * 2 % Mod;
}
for (int i = 0; i < k; i++) {
ll dif = s - i;
if (dif >= k) {
ret -= (dp[n][i] * 2 % Mod);
ret = (ret + Mod) % Mod;
}else {
ret -= dp[n][i];
ret = (ret + Mod) % Mod;
}
}
return ret;
}
};
腾讯云开发者
