LeetCode-第467场周赛-第13天
目录
LeetCode 第467场周赛 第13天
1. 3683 完成一个任务的最早时间(遍历)
链接：
题解：
题解
时间复杂度O(n)：
- 求最早完成的任务，任务完成时间 = si + ti，遍历取最小值既可
代码：
class Solution {
public int earliestTime(int[][] tasks) {
int sum = Integer.MAX_VALUE;
for (int[] task: tasks) {
sum = Math.min(sum, task[0] + task[1]);
}
return sum;
}
}2. 3684 至多 K 个不同元素的最大和（排序 + 遍历）
链接：
题解：
题解
时间复杂度O(nlogn):
- K个不同元素的最大和，肯定是从最大值开始取，过滤掉重复数字既可
- 先排序，保证列表有序，从最大值开始遍历，用Pre表示上一次出现的数字，进行过滤重复数字
代码：
class Solution {
public int[] maxKDistinct(int[] nums, int k) {
Arrays.sort(nums);
int pre = Integer.MAX_VALUE;
int count = 0;
List<Integer> ans = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; --i) {
if (pre == nums[i]) {
continue;
}
ans.add(nums[i]);
pre = nums[i];
count ++;
if (count >= k) {
break;
}
}
return ans.stream().mapToInt(i -> i).toArray();
}
}3. 3685 含上限元素的子序列和（单调栈）
链接：
题解：
题解
时间复杂度O(n^2 + nk):
- 针对nums[i]替换为min(x, nums[i])，在排序的情况下，实际上有规律的，被替换的数字只会越来越大（例如：1 2 3 4，替换第一次是 1 x x x，第二次 1 2 x x，第三次是1 2 3 x）
- 如果给一个列表，求是否能组成和等于k，其实就是一个基础的01背包问题（没学过的小伙伴可以了解一下）
- 01背包，f[i][j] 代表 前i个数，组成的数字j是否存在，存在f[i][j]=true，不存在f[i][j]=false；转换方程式：
f[i][j] |= f[i - 1][j - nums[i]]，初始化f[0][0] = true（没选数字的时候能组成数字0）根据01背包能在O(nk)复杂度下求出能否组成某一个值。再枚举有n个可选的x，那么枚举n，判断是否存在前缀部分和为k-nx的既可- 核心内容：边做01背包，边枚举替换情况（因为01背包也是要从前往后遍历的，而替换x也是随着x增大，替换的起点往后移动）
代码：
class Solution {
private boolean check(int target, int x, int size, boolean[] numExists) {
// 枚举有n个x
for (int i = 0; i <= size; ++ i) {
if (i * x > target) {
break;
}
if (numExists[target - i * x]) {
return true;
}
}
return false;
}
public boolean[] subsequenceSumAfterCapping(int[] nums, int k) {
Arrays.sort(nums);
int len = nums.length;
boolean[] numExists = new boolean[k + 1];
numExists[0] = true;
boolean[] ans = new boolean[len];
// 处理全部都被替换成x的情况
for (int i = 1; i < nums[0]; ++ i) {
ans[i - 1] = check(k, i, len, numExists);
}
for (int i = 0; i < len; ++ i) {
for (int j = k; j >= nums[i]; -- j) {
// 01背包
numExists[j] |= numExists[j - nums[i]];
}
// 枚举现阶段x的所有可能
int r = i == len - 1 ? len + 1 : nums[i + 1];
for (int j = nums[i]; j < r; ++ j) {
ans[j - 1] = check(k, j, len - i - 1, numExists);
}
}
return ans;
}
}3. 3686 稳定子序列的数量（DP）
链接：
题解：
题解
时间复杂度O(n)：
- 要求不存在
三个元素奇偶性相同(子序列)，那么针对列表中每个数字的选择，都需要知道前两个数字的奇偶性，所以需要记录前两个数字的奇偶性。而这里奇偶，可以用0、1表示，假设0代表奇，1代表偶，那么00（奇奇）、01(奇偶)、10(偶奇)、11(偶偶)，二进制对应的分别0、1、2、3- 对于每个数字而言，无非就两种操作，
选或者不选- 由上可知，可以用
f[i][j]（i < n | j < 4）表示遍历到i下标的数字，子序列最后两个数字奇偶的数量状态转移方程式：
如果不选择nums[i]：f[i][j] = f[i - 1][j]
如果选择nums[i]且nums[i]是奇数：f[i][0] += f[i - 1][2]；f[i][2] += f[i - 1][1] + f[i - 1][3]
如果选择nums[i]且nums[i]是偶数：f[i][3] += f[i - 1][1]；f[i][1] += f[i - 1][0] + f[i - 1][2]初始化：
nums[i]是奇数：f[i][2] = 1（2的二进制是10(偶奇)，这里已经出现了奇偶两种状态，所以不会影响nums[i+1]的选择，反正f[i][0]会影响）
nums[i]是偶数：f[i][1] = 1（1的二进制是01(奇偶)，这里已经出现了奇偶两种状态，所以不会影响nums[i+1]的选择，贩子f[i][3]会影响）
代码：
class Solution {
public int countStableSubsequences(int[] nums) {
int len = nums.length;
int[][] f = new int[len][4];
int mod = 1000000007;
for (int i = 0; i < len; ++ i) {
if (nums[i] % 2 == 1) {
f[i][2] = 1;
} else {
f[i][1] = 1;
}
}
for (int i = 1; i < len; ++ i) {
for (int j = 0; j < 4; ++ j) {
f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
}
if (nums[i] % 2 == 1) {
f[i][0] = (f[i][0] + f[i - 1][2]) % mod;
f[i][2] = ((f[i][2] + f[i - 1][1]) % mod + f[i - 1][3]) % mod;
} else {
f[i][1] = ((f[i][1] + f[i - 1][0]) % mod + f[i - 1][2]) % mod;
f[i][3] = (f[i][3] + f[i - 1][1]) % mod;
}
}
return (((f[len - 1][0] + f[len - 1][1]) % mod + f[len - 1][2]) % mod + f[len - 1][3]) % mod;
}
}如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！