给你一个整数数组 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 <= 100
1 <= 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;
}
}
给你一个整数数组 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;
}
}
给你一个只包含字符 '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 <= 105
s 只包含字符 '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;
}
}
给你一个 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.length
1 <= k * events.length <= 10 ^ 6
1 <= startDayi <= endDayi <= 10 ^ 9
1 <= 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++ 还是有较大的优势。
最近两天也是比较累,本来今天打算不更新的了。
看了一下双周赛的题目,还挺简单,也属于笔试面试的常见题目,就做了一下,写了题解发上来。
看情况明天会把今天周赛的题解发上来。大家晚安 ~