LeetCode 第 227 场周赛题解
LeetCode 第 227 场周赛题解
t1：1752. 检查数组是否经排序和轮转得到（简单）
给你一个数组 nums 。
nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false。
源数组中可能存在「重复项」。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
示例 1：
输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
示例 2：
输入：nums = [2,1,3,4]
输出：false
解释：源数组无法经轮转得到 nums 。
示例 3：
输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。
示例 4：
输入：nums = [1,1,1]
输出：true
解释：[1,1,1] 为有序的源数组。
轮转任意个位置都可以得到 nums 。
示例 5：
输入：nums = [2,1]
输出：true
解释：[1,2] 为有序的源数组。
可以轮转 x = 5 个位置，使新数组从值为 2 的元素开始：[2,1] 。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
朴素解法
一道模拟题，而且数据范围只有 100，怎么做都可以。
先通过一次循环，找到旋转点，此时旋转点的两侧数组都是单调递增。
分别判断两段是否单调递增即可。
PS. 如果找到结尾都没有旋转点，说明旋转点是下标为 0 的位置。
class Solution {
public boolean check(int[] nums) {
int n = nums.length;
int idx = 0;
while (idx + 1 < n && nums[idx] <= nums[idx + 1]) idx++;
int cur = idx + 1 < n ? nums[idx + 1] : nums[0];
for (int i = idx + 1; i < n; i++) {
if (nums[i] >= cur) {
cur = nums[i];
} else {
return false;
}
}
for (int i = 0; i <= idx; i++) {
if (nums[i] >= cur) {
cur = nums[i];
} else {
return false;
}
}
return true;
}
}
- 时间复杂度：
- 空间复杂度：
t2：1753. 移除石子的最大得分（中等）
你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c的 三堆石子。
每回合你都要从两个「不同的非空堆」中取出一颗石子，并在得分上加 1 分。
当存在「两个或更多」的空堆时，游戏停止。
给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
示例 1：
输入：a = 2, b = 4, c = 6
输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
- 从第一和第三堆取，石子状态现在是 (1, 4, 5)
- 从第一和第三堆取，石子状态现在是 (0, 4, 4)
- 从第二和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：6 分 。
示例 2：
输入：a = 4, b = 4, c = 6
输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：
- 从第一和第二堆取，石子状态现在是 (3, 3, 6)
- 从第一和第三堆取，石子状态现在是 (2, 3, 5)
- 从第一和第三堆取，石子状态现在是 (1, 3, 4)
- 从第一和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：7 分 。
示例 3：
输入：a = 1, b = 8, c = 8
输出：8
解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。
注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。
提示：
1 <= a, b, c <= 105
贪心解法
见到这道题的几个样例之后，我大概猜了一个做法：先确保 a <= b <= c 的顺序，然后把 a 搞成 0，同时尽量配平 b 和 c。
代码
class Solution {
public int maximumScore(int a, int b, int c) {
int sum = a + b + c;
int min = Math.min(Math.min(a, b), c);
int max = Math.max(Math.max(a, b), c);
return getScore(min, sum - min - max, max);
}
int getScore(int a, int b, int c) {
int ans = 0;
// 第一步消除
int cnt = Math.min(c - b, a);
c -= cnt;
a -= cnt;
ans += cnt;
// 第二步消除
if (a > 0) {
int l = a / 2, r = a - l;
b -= l;
c -= r;
ans += l;
ans += r;
}
// 最终消除
cnt = Math.min(b, c);
ans += cnt;
return ans;
}
}
- 时间复杂度：
- 空间复杂度：
分析
由于人为确保了 a <= b <= c，当我们执行「第一步消除」之后，有两种情况：
a = 0：已经达到a = 0的目的，而且a的数量贡献在「使b和c均衡」上，这时候直接将b和c取一个 min（使其其中一个变为空堆），整个过程结束。a != 0：这时候b和c是相等的，而且a仍然是三者最小的堆（b没有发生过消除，仍然有b >= a；a和c发生了相同数量的消除，仍然有c >= a）。这时候将a均分给b和c（第二步消除），使得a = 0，b和c保持均衡。再将b和c取一个 min（使其其中一个变为空堆），整个过程结束。
t3：1754. 构造字典序最大的合并字符串（中等）
给你两个字符串 word1 和 word2 。
你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择「下面选项之一」继续操作：
- 如果
word1非空，将word1中的第一个字符附加到merge的末尾，并将其从word1中移除 例如，word1= "abc" 且merge= "dv" ，在执行此选项操作之后，word1= "bc" ，同时merge= "dva" - 如果
word2非空，将word2中的第一个字符附加到merge的末尾，并将其从word2中移除。 例如，word2= "abc" 且merge= "" ，在执行此选项操作之后，word2= "bc" ，同时merge= "a"
返回你可以构造的字典序「最大」的合并字符串 merge 。
长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字符串 b 更大。
例如，"abcd" 按字典序比 "abcc" 更大，因为两个字符串出现不同的第一个位置是第四个字符，而 d 在字母表中的出现顺序位于 c 之后。
示例 1：
输入：word1 = "cabaa", word2 = "bcaaa"
输出："cbcabaaaaa"
解释：构造字典序最大的合并字符串，可行的一种方法如下所示：
- 从 word1 中取第一个字符：merge = "c"，word1 = "abaa"，word2 = "bcaaa"
- 从 word2 中取第一个字符：merge = "cb"，word1 = "abaa"，word2 = "caaa"
- 从 word2 中取第一个字符：merge = "cbc"，word1 = "abaa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbca"，word1 = "baa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbcab"，word1 = "aa"，word2 = "aaa"
- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾
示例 2：
输入：word1 = "abcabc", word2 = "abdcaba"
输出："abdcabcabcaba"
提示：
- `1 <= word1.length, ，最终得到的就不是最短的答案
否则删除过程就可能会因为下一个字符不同而停止 class Solution { 代码：```javaword2.length <= 3000`
word1和word2仅由小写英文组成
双指针 + 贪心解法
class Solution {
public String largestMerge(String w1, String w2) {
StringBuilder sb = new StringBuilder();
int n = w1.length(), m = w2.length();
char[] wo = w1.toCharArray(), wt = w2.toCharArray();
for (int i = 0, j = 0; i < n || j < m;) {
if (i >= n) {
sb.append(wt[j++]);
} else if (j >= m) {
sb.append(wo[i++]);
} else {
int c1 = 0, c2 = 0;
if (i < n) c1 = (int)(wo[i] - 'a');
if (j < m) c2 = (int)(wt[j] - 'a');
if (c1 != c2) {
if (c1 > c2) {
sb.append(wo[i++]);
} else {
sb.append(wt[j++]);
}
} else {
int t = i, k = j;
while (t < n && k < m && wo[t] == wt[k]) {
t++;
k++;
}
int l = t < n ? (int)(wo[t] - 'a') : 0;
int r = k < m ? (int)(wt[k] - 'a') : 0;
if (l > r) {
sb.append(wo[i++]);
} else {
sb.append(wt[j++]);
}
}
}
}
return sb.toString();
}
}
- 时间复杂度：
- 空间复杂度：
t4：1755. 最接近目标值的子序列和（困难）
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的「最小值」。
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
示例 1：
输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，
元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。
示例 2：
输入：nums = [7,-9,15,-2], goal = -5
输出：1
解释：选出子序列 [7,-9,-2] ，
元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。
示例 3：
输入：nums = [1,2,3], goal = -7
输出：7
提示：
1 <= nums.length <= 40-10^7 <= nums[i] <= 10^7-10^9 <= goal <= 10^9
基本思路
通常如果数据范围是 30 以内的话，我会直接写 DFS。
但这里的数据范围是 40，朴素的 DFS 是肯定会超时的。
「那么遇到会超时的 DFS 数据范围怎么办呢？」
我们可以将这个 DFS 过程分解成两段完成。
我们可以先对数组的前半部分进行 DFS 将答案存入列表 left 中；然后对数组的右半部分进行 DFS，将答案存入列表 right 中。
然后在 left 和 right 中分别找到 i1 和 i2，使得 abs(i1 + i2 - goal) 最小。
假设 left 的长度为 n，right 的长度为 m。
我们在确定 i1， 找 i2 的时候，要先对 right 进行排序，这样我们才能通过「二分」找 i2。
通过「二分」，我们找 i1 和 i2 的时间复杂度是
，而不是
。
这样我们就将数据范围为 40 的 DFS 变成了两次数据范围为 20 的 DFS。
将朴素的 DFS 分成两段 DFS 的做称为双向 DFS。
双向 DFS 是一个典型的「空间换时间」的方案。
class Solution {
public int minAbsDifference(int[] nums, int goal) {
int n = nums.length;
// 暴搜左边，将答案存入 left
List<Integer> left = new ArrayList<>();
dfs(nums, 0, n / 2, 0, left);
// 暴搜右边，将答案存入 right
List<Integer> right = new ArrayList<>();
dfs(nums, n / 2, n, 0, right);
int ans = Integer.MAX_VALUE;
// 排序，目的是方便我们「二分」
Collections.sort(right);
int m = right.size();
for (int i1 : left) {
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (right.get(mid) + i1 <= goal) {
l = mid;
} else {
r = mid - 1;
}
}
// 这时候 r 应该是满足「right.get(r) + i1 <= goal」性质的最靠近中心的下标
// 但不一定是使得 `i1 + i2 - goal` 最小的值，也有可能是其下一位
ans = Math.min(ans, Math.abs(i1 + right.get(r) - goal));
if (r + 1 < m) ans = Math.min(ans, Math.abs(i1 + right.get(r + 1) - goal));
}
return ans;
}
void dfs(int[] nums, int u, int n, int cur, List<Integer> list) {
if (u == n) {
list.add(cur);
return;
}
dfs(nums, u + 1, n, cur + nums[u], list);
dfs(nums, u + 1, n, cur, list);
}
}
- 时间复杂度：运算量大概在
（2 段数据量为 20 的 DFS），数量级在
。
- 空间复杂度：略
最后
这是 2021/02/07 的 LeetCode 第 227 场双周赛的比赛题解。
和昨天的双周赛类似，都是比较常规的题型，基本上匹配了笔试的难度。
但是这次贪心题偏多了一点，按到道理应该至少有一道 DP 题才对。
2021/02/14 补充
这份题解我是周赛的后一天（2021/02/08）就写出来了，因为周赛当天我写的是前一天的双周赛的题解，所以这个晚了一天。
结果写完之后忘记发出来了，今天是「第 228 场周赛」才发现，我也是服了自己 ~
:)
腾讯云开发者
