todo
标签： todo
3040.相同分数的最大操作数目II
目标
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
- 选择 nums 中最前面两个元素并且删除它们。
- 选择 nums 中最后两个元素并且删除它们。
- 选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
- 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
- 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
由于 nums 为空，我们无法继续进行任何操作。示例 2：
输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
- 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
至多进行 2 次操作。说明：
- 2 <= nums.length <= 2000
- 1 <= nums[i] <= 1000
思路
比 相同分数的最大操作数目I 增加了两种操作，可以删除最后两个元素或者一前一后两个元素。
我的思路是使用回溯算法，为了防止环的形成，使用自定义hash函数 (long) start << 16 | end; 记录已经搜索过的区间，并存入哈希表。
勉强通过了，看了官网题解，说是要用记忆搜索。网友还给出了递推的解法。//todo
代码
/**
* @date 2024-06-08 20:03
*/
public class MaxOperations3040 {
private Set<Long> set;
public int maxOperations(int[] nums) {
int res = 0;
int n = nums.length;
set = new HashSet<>();
set.add(n - 1L);
res = dfs(nums, 2, n - 1, nums[0] + nums[1], 1);
res = Math.max(res, dfs(nums, 0, n - 3, nums[n - 2] + nums[n - 1], 1));
res = Math.max(res, dfs(nums, 1, n - 2, nums[0] + nums[n - 1], 1));
return res;
}
public int dfs(int[] nums, int start, int end, int target, int ops) {
int res = ops;
long key = (long) start << 16 | end;
if (set.contains(key) || start >= end || res == nums.length / 2) {
return res;
}
set.add(key);
if (start < nums.length - 1 && nums[start] + nums[start + 1] == target) {
res = dfs(nums, start + 2, end, target, ops + 1);
}
if (end >= 1 && nums[end] + nums[end - 1] == target) {
res = Math.max(res, dfs(nums, start, end - 2, target, ops + 1));
}
if (end >= 0 && start < nums.length && nums[start] + nums[end] == target) {
res = Math.max(res, dfs(nums, start + 1, end - 1, target, ops + 1));
}
return res;
}
}
性能
2981.找出出现至少三次的最长特殊子字符串I
目标
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1：
输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。示例 2：
输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。示例 3：
输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。说明：
- 3 <= s.length <= 50
- s 仅由小写英文字母组成。
思路
这道题要我们求给定字符串中至少出现三次的由相同字符组成的子串的最大长度。下面分情况讨论：
- 如果特殊子串是连续的，那么取最大子串长度-2。例如：
aaaa有以下符合条件的特殊子串(aa)aa、a(aa)a和aa(aa)，至少出现三次的最长特殊子字符串长度为2。 - 如果特殊子串个数为2：
- 如果这两个子串长度相同，取长度-1。例如：
aaaaaa有以下符合条件的特殊子串(aa)aa(aa)(aa)aa(aa)，出现了4次，最长特殊子串长度为2。 - 如果这两个子串长度不同，取
max(last -2 , secondTolast)。例如：aaaaaaaaa有以下符合条件的特殊子串(aaa)(aaa)aa(aaa)，出现了3次，最长特殊子串长度为3。
- 如果这两个子串长度相同，取长度-1。例如：
- 如果特殊子串个数大于2，取
max(last -2 , thirdTolast)。例如：aaaaaaaa有以下符合条件的特殊子串(aa)(aa)aa(aa)(aa)aa(aa)，出现了5次，最长特殊子串长度为3。
代码
/**
* @date 2024-05-29 8:42
*/
public class MaximumLength2981 {
public int maximumLength(String s) {
int res = -1;
Map<Character, List<Integer>> map = new HashMap<>(26);
for (int i = 'a'; i <= 'z'; i++) {
map.put((char) i, new ArrayList<>());
}
int n = s.length();
char last = s.charAt(0);
int cnt = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == last) {
cnt++;
} else {
map.get(last).add(cnt);
cnt = 1;
last = c;
}
if (i == n - 1) {
map.get(c).add(cnt);
}
}
for (Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
List<Integer> occurrence = entry.getValue();
int size = occurrence.size();
Collections.sort(occurrence);
if (size >= 2) {
Integer secondToLastOccurrence = occurrence.get(size - 2);
Integer lastOccurrence = occurrence.get(size - 1);
if (lastOccurrence - secondToLastOccurrence >= 1) {
res = Math.max(res, Math.max(secondToLastOccurrence, lastOccurrence - 2));
} else {
res = Math.max(res, lastOccurrence - 1);
}
if (size >= 3) {
res = Math.max(res, Math.max(occurrence.get(size - 3), occurrence.get(size - 1) - 2));
}
} else if (size == 1) {
res = Math.max(res, occurrence.get(0) - 2);
}
}
return res == 0 ? -1 : res;
}
}性能
// todo 性能优化
1738.找出第K大的异或坐标值
目标
给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。示例 2：
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。示例 3：
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。示例 4：
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。说明：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
0 <= matrix[i][j] <= 10^6- 1 <= k <= m * n
思路
求二维矩阵 matrix 的第k大的异或坐标值，元素 matrix[i][j] 的异或坐标值等于对matrix[0][0] ~ matrix[i][j]矩阵中的所有值进行异或运算。
我们可以先分别对每一行按列进行异或运算，然后再针对每一列按行进行异或运算。然后将它们放入优先队列，再取第k大的值即可。
官网题解用到了二维前缀和 + 排序/快速选择。// todo
代码
/**
* @date 2024-05-26 19:07
*/
public class KthLargestValue11738 {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = matrix[i][0];
}
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] ^ matrix[i][j];
}
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] ^= dp[i - 1][j];
q.offer(dp[i][j]);
}
}
for (int i = 0; i < n; i++) {
q.offer(dp[0][i]);
}
int res = 0;
while (k > 0) {
res = q.poll();
k--;
}
return res;
}
}
性能
2903.找出满足差值条件的下标I
目标
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。
你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：
- abs(i - j) >= indexDifference 且
- abs(nums[i] - nums[j]) >= valueDifference
返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。
注意：i 和 j 可能 相等 。
示例 1：
输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。示例 2：
输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。
因此，[0,0] 是一个符合题目要求的答案。
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。 示例 3：
输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。说明：
- 1 <= n == nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= indexDifference <= 100
- 0 <= valueDifference <= 50
思路
给我们一个数组，找出其中下标之差大于等于indexDifference，并且值值差大于等于valueDifference的下标，如果不存在返回[-1, -1]。
按照题意我们循环 [0, length)，将 [i + indexDifference, length) 的元素分别与 i 进行比较。
题目给定的数据范围比较小，可以使用暴力解法。数据范围变大后这个方法可能会超时，参考 2905.找出满足差值条件的下标 II。
题解给出了一次遍历的题解，只需记录前面的最大与最小值。// todo
代码
/**
* @date 2024-05-25 20:14
*/
public class FindIndices2903 {
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int r = i + indexDifference;
while (r < n && Math.abs(nums[i] - nums[r]) < valueDifference) {
r++;
}
if (r < n) {
return new int[]{i, r};
}
}
return new int[]{-1, -1};
}
}
性能
1673.找出最具竞争力的子序列
自己写的超时了，看题解需要使用单调栈 //todo
2831.找出最长等值子数组
目标
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
示例 1：
输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。示例 2：
输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。
删除后，nums 等于 [1, 1, 1, 1] 。
数组自身就是等值子数组，长度等于 4 。
可以证明无法创建更长的等值子数组。说明：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= nums.length
- 0 <= k <= nums.length
思路
给定一个数组 nums 和一个正整数k，最多可以删除数组中k个元素，问数组中最长的等值子数组有多长，所谓等值子数组就是数组中的值完全相同。
直接的想法是记录每个相同元素的下标index，然后计算它们之间的距离 gap，使用滑动窗口来计算最多可以消除的 gap 数量。
注意不能优先消除序列中距离小的 gap，也就是说只能按照顺序去消除，否则可能会截断等值子数组。
刚开始使用哈希表记录相同元素的下标序列，结果提示超出内存限制，后来改用数组解决了问题。
Map在不断添加元素时可能需要进行扩容，每次扩容都需要重新分配更大的内存空间。但我直接指定初始大小还是超出限制。
原来用了两个哈希表，indexMap 与 gapMap，后来 indexMap 改成了 List[]，gapMap 则直接在循环中计算并添加到 ArrayList 中。
注意这不是一个固定大小的窗口，如果按照固定大小的窗口去实现还是会超时。
代码
/**
* @date 2024-05-23 0:11
*/
public class LongestEqualSubarray2831 {
public int longestEqualSubarray_v1(List<Integer> nums, int k) {
if (nums.size() == 0) {
return 0;
}
int res = 0;
List<Integer>[] indexMap = new List[100001];
for (int i = 0; i < nums.size(); i++) {
int val = nums.get(i);
if (indexMap[val] == null) {
indexMap[val] = new ArrayList<>();
}
indexMap[val].add(i);
}
for (List<Integer> index : indexMap) {
if (index == null) {
continue;
}
int i = 0;
ArrayList<Integer> gaps = new ArrayList<>();
for (int j = 1; j < index.size(); j++) {
gaps.add(index.get(j) - index.get(i++) - 1);
}
int cnt = k;
int gapNums = 0;
int left = 0;
int right = 0;
while (right < gaps.size()) {
while (cnt >= 0 && right < gaps.size()) {
cnt -= gaps.get(right);
if (cnt >= 0) {
right++;
}
}
gapNums = Math.max(gapNums, right - left);
while (left < gaps.size() && cnt < 0) {
cnt += gaps.get(left);
left++;
}
right++;
}
res = Math.max(res, gapNums + 1);
}
return res;
}
}性能
又是勉强通过。//todo 性能分析与优化
1553.吃掉N个橘子的最少天数
有思路但是今天只剩下几十分钟了，有机会再做吧。
下面的代码超时了。// 5.13更新：这种贪心策略是不对的，不能优先选第三种策略。同时，最后一行的返回值minDays(n - 1)等于从0~n每一个值都要递归一遍，不可取。最后还要使用记忆化搜索。
/**
* @date 2024-05-12 23:11
*/
public class MinDays1553 {
@Deprecated
public int minDays(int n) {
int res = 0;
if (n <= 0) {
return 0;
}
if (n % 3 == 0) {
res = minDays(n - 2 * (n / 3)) + 1;
} else if (n % 2 == 0) {
res = minDays(n - n / 2) + 1;
} else {
return minDays(n - 1) + 1;
}
return Math.min(res, minDays(n - 1) + 1);
}
}
2391.收集垃圾的最少总时间
目标
给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。
请你返回收拾完所有垃圾需要花费的 最少 总分钟数。
示例 1：
输入：garbage = ["G","P","GP","GG"], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。示例 2：
输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。说明：
- 2 <= garbage.length <= 10^5
- garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
- 1 <= garbage[i].length <= 10
- travel.length == garbage.length - 1
- 1 <= travel[i] <= 100
思路
暴力解法，计算每个房子的垃圾数以及回收各种垃圾需要到达的最远距离。
官网题解给出了一次遍历的解法。没时间看了。// todo
代码
/**
* @date 2024-05-11 8:37
*/
public class GarbageCollection2391 {
public int garbageCollection(String[] garbage, int[] travel) {
int res = 0;
int n = garbage.length;
int[] m = new int[n];
int[] p = new int[n];
int[] g = new int[n];
int[] t = new int[n-1];
t[0] = travel[0];
for (int i = 1; i < travel.length; i++) {
t[i] = t[i - 1] + travel[i];
}
for (char c : garbage[0].toCharArray()) {
if (c == 'M') {
m[0]++;
} else if (c == 'P') {
p[0]++;
} else if (c == 'G') {
g[0]++;
}
}
int mEnd = 0;
int pEnd = 0;
int gEnd = 0;
for (int i = 1; i < n; i++) {
char[] chars = garbage[i].toCharArray();
for (char c : chars) {
if (c == 'M') {
m[i]++;
} else if (c == 'P') {
p[i]++;
} else if (c == 'G') {
g[i]++;
}
}
m[i] += m[i - 1];
p[i] += p[i - 1];
g[i] += g[i - 1];
if (m[i] != m[i - 1]) {
mEnd = i;
}
if (p[i] != p[i - 1]) {
pEnd = i;
}
if (g[i] != g[i - 1]) {
gEnd = i;
}
}
res += m[mEnd] + p[pEnd] + g[gEnd];
if (mEnd > 0) {
res += t[mEnd - 1];
}
if (pEnd > 0) {
res += t[pEnd - 1];
}
if (gEnd > 0) {
res += t[gEnd - 1];
}
return res;
}
}
性能
741.摘樱桃
这道题今天没时间做了