LeetCode 第 45 场双周赛题解
t1：5657. 唯一元素的和（简单）
给你一个整数数组 nums 。数组中唯一元素是那些只出现「恰好一次」的元素。
请你返回 nums 中唯一元素的「和」。
示例 1：
输入：nums = [1,2,3,2]
输出：4
解释：唯一元素为 [1,3] ，和为 4 。
示例 2：
输入：nums = [1,1,1,1,1]
输出：0
解释：没有唯一元素，和为 0 。
示例 3 ：
输入：nums = [1,2,3,4,5]
输出：15
解释：唯一元素为 [1,2,3,4,5] ，和为 15 。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
朴素解法
一道模拟题，直接使用「哈希表」或者「数组」来存元素出现次数即可。
对于一些给定了元素数据范围的题目，建议使用数据来进行统计，这样对于 Java 语言来说，代码会短些。
对于没有给定元素数据范围，或者数据范围很大的，则使用哈希表。
代码：
class Solution {
public int sumOfUnique(int[] nums) {
int[] cnt = new int[110];
for (int i : nums) cnt[i]++;
int ans = 0;
for (int i = 0; i < 110; i++) {
if (cnt[i] == 1) ans += i;
}
return ans;
}
}
- 时间复杂度：
- 空间复杂度：
t2：5658. 任意子数组和的绝对值的最大值（中等）
给你一个整数数组 nums 。
一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的和的绝对值为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
请你找出 nums 中「和的绝对值」最大的任意子数组（可能为空），并返回该最大值 。
abs(x) 定义如下：
- 如果
x是负整数，那么abs(x) = -x。 - 如果
x是非负整数，那么abs(x) = x。
示例 1：
输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，
为 abs(2+3) = abs(5) = 5 。
示例 2：
输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，
为 abs(-5+1-4) = abs(-8) = 8 。
提示：
1 <= nums.length <= 10 ^ 5-10 ^ 4 <= nums[i] <= 10 ^ 4
前缀和解法
题目要我们求连续一段的子数组的和，很自然就能想到前缀和。
当我们有了前缀和数组 sum 之后，需要求任意一段子数组 [i,j] 的和可以直接通过 sum[j] - sum[i - 1] 得出。
要使得 abs(sum[j] - sum[i - 1]) 最大，其实有这么几种情况：
- 找到前缀和数组中的最大值减去最小值，得到一个最大正数（前提是最大值出现在最小值的后面，并且最小值是个负数，否则应该直接取最大值作为答案）
- 找到前缀和的最小值减去最大值，得到一个最小负数（前提是最小值出现在最大值的后面，而且最大值是一个正数，否则直接取最小值作为答案）。
也就是说最终答案只与前缀和数组中的最大值和最小值相关，而且最大值可能会出现在最小值前面或者后面。
因此我们可以边循环边做更新答案：
class Solution {
public int maxAbsoluteSum(int[] nums) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
int max = 0, min = 0, ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, Math.abs(sum[i] - min));
ans = Math.max(ans, Math.abs(sum[i] - max));
max = Math.max(max, sum[i]);
min = Math.min(min, sum[i]);
}
return ans;
}
}
- 时间复杂度：
- 空间复杂度：
t3：5659. 删除字符串两端相同字符后的最短长度（中等）
给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，
你可以执行下面这个操作（5 个步骤）任意次：
- 选择字符串
s一个「非空」的前缀，这个前缀的所有字符都相同 - 选择字符串
s一个「非空」的后缀，这个后缀的所有字符都相同 - 前缀和后缀在字符串中任意位置都不能有交集
- 前缀和后缀包含的所有字符都要相同
- 同时删除前缀和后缀
请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度
示例 1：
输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。
示例 2：
输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，
得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，
得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，
得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，
得到 s = "" 。
示例 3：
输入：s = "aabccabba"
输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，
得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，
得到 s = "cca" 。
提示：
1 <= s.length <= 105s 只包含字符 'a'，'b' 和 'c'
双指针 + 贪心解法
因为只有「前缀」和「后缀」必须是相同的字母才能删除。
因此我们每次都将「前缀」和「后缀」所有的相同字符的连续一段删除。
否则删除过程就可能会因为下一个字符不同而停止，最终得到的就不是最短的答案
代码：
class Solution {
public int minimumLength(String s) {
int n = s.length();
char[] cs = s.toCharArray();
int ans = n;
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (cs[i] != cs[j]) break;
while (i + 1 < j && cs[i + 1] == cs[i]) i++;
while (j - 1 > i && cs[j - 1] == cs[j]) j--;
ans = Math.max(0, j - i - 1);
}
return ans;
}
}
- 时间复杂度：
- 空间复杂度：
t4：5660. 最多可以参加的会议数目 II（困难）
给你一个 events 数组。
其中 events[i] = [startDay[i], endDay[i], value[i] 。
表示第 i 个会议在 startDay[i] 天开始，第 endDay[i] 天结束，如果你参加这个会议，你能得到价值 value[i]。
同时给你一个整数 k 表示你能参加的最多会议数目。
你同一时间只能参加一个会议。 如果你选择参加某个会议，那么你必须「完整」地参加完这个会议。
会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值「最大和」。
示例 1：
输入：events = [[1,2,4],[3,4,3],[2,3,1]],
k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，
得到总价值和为 4 + 3 = 7 。
示例 2：
输入：events = [[1,2,4],[3,4,3],[2,3,10]],
k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。
你不需要参加满 k 个会议。
示例 3：
输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]],
k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，
所以选择价值最大的 3 个会议。
提示：
1 <= k <= events.length1 <= k * events.length <= 10 ^ 61 <= startDayi <= endDayi <= 10 ^ 91 <= valuei <= 10 ^ 6
基本思路
定义 f[i][j] 为考虑前 i 个时间，选择不超过 j 的最大价值
对于每件时间，都有选择与不选两种选择，不选有 f[i][j] = f[i - 1][j]。
选择的话，则要找到第 i 件事件之前，与第 i 件事件不冲突的事件，记为 last，则有 f[i][j] = f[last][j - 1]。
两者取一个 max，则是 f[i][j] 的值。
分析到这里，因为我们要找 last，我们需要先对 events 的结束时间排序，然后找从右往左找，找到第一个满足 结束时间 小于 当前事件的开始时间 的事件，就是 last
而找 last 的过程，可以直接循环找，也可以通过二分来找，都能过。
动态规划解法
不通过「二分」来找 last 的 DP 解法：
class Solution {
public int maxValue(int[][] es, int k) {
int n = es.length;
Arrays.sort(es, (a, b)->a[1]-b[1]);
// f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
int[][] f = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
int[] ev = es[i - 1];
int s = ev[0], e = ev[1], v = ev[2];
// 找到第 i 件事件之前，与第 i 件事件不冲突的事件
// 对于当前事件而言，冲突与否，与 j 无关
int last = 0;
for (int p = i - 1; p >= 1; p--) {
int[] prev = es[p - 1];
if (prev[1] < s) {
last = p;
break;
}
}
for (int j = 1; j <= k; j++) {
f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);
}
}
return f[n][k];
}
}
- 时间复杂度：排序复杂度为
，循环 n 个事件，每次循环需要往回找一个事件，复杂度为
，并更新 k 个状态，复杂度为
，因此转移的复杂度为
；总的复杂度为
- 空间复杂度：
二分 + 动态规划解法
通过「二分」来找 last 的 DP 解法：
class Solution {
public int maxValue(int[][] es, int k) {
int n = es.length;
Arrays.sort(es, (a, b)->a[1]-b[1]);
// f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
int[][] f = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
int[] ev = es[i - 1];
int s = ev[0], e = ev[1], v = ev[2];
// 通过「二分」，找到第 i 件事件之前，与第 i 件事件不冲突的事件
// 对于当前事件而言，冲突与否，与 j 无关
int l = 1, r = i - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
int[] prev = es[mid - 1];
if (prev[1] < s) {
l = mid;
} else {
r = mid - 1;
}
}
int last = (r > 0 && es[r - 1][1] < s) ? r : 0;
for (int j = 1; j <= k; j++) {
f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);
}
}
return f[n][k];
}
}
- 时间复杂度：排序复杂度为
，循环 n 个事件，每次循环需要往回找一个事件，复杂度为
，并更新 k 个状态，复杂度为
，因此转移的复杂度为
；总的复杂度为
- 空间复杂度：
最后
这是 2021/02/06 的 LeetCode 第 45 场双周赛的比赛题解。
整体偏简单，没有冷门的内容，都是考察一些比较常见的模型。
对于竞赛生来说就是手速场，LeetCode 的排名是不分语言的，所以 C++ 还是有较大的优势。
最近两天也是比较累，本来今天打算不更新的了。
看了一下双周赛的题目，还挺简单，也属于笔试面试的常见题目，就做了一下，写了题解发上来。
看情况明天会把今天周赛的题解发上来。大家晚安 ~
腾讯云开发者
