目录
一、3174. 清除数字
二、3175. 找到连续赢 K 场比赛的第一位玩家
三、3176. 求出最长好子序列 I
四、3177. 求出最长好子序列 II
一、3174. 清除数字
本题可以使用栈来模拟，遇到数字弹出栈顶元素，遇到字母入栈。
代码如下：
//使用字符串模拟栈实现
class Solution {
public String clearDigits(String s) {
StringBuilder st = new StringBuilder();
for(char c : s.toCharArray()){
if(Character.isDigit(c)){
st.deleteCharAt(st.length()-1);
}else{
st.append(c);
}
}
return st.toString();
}
}
二、3175. 找到连续赢 K 场比赛的第一位玩家
本题可以使用双端队列模拟，但是要注意当 k >= n 时，直接返回最大值
代码如下：
class Solution {
public int findWinningPlayer(int[] s, int k) {
int n = s.length;
int mx = 0, idx = 0;
Deque<int[]> que = new ArrayDeque<>();
for(int i=0; i<n; i++){
que.addLast(new int[]{s[i], i});
if(mx < s[i]){
mx = s[i];
idx = i;
}
}
if(k >= n) return idx;
int t = k;
mx = que.poll()[0];
idx = 0;
while(t > 0){
int[] x = que.removeFirst();
if(x[0] > mx){
que.addLast(new int[]{mx, idx});
mx = x[0];
idx = x[1];
t = k-1;
}else{
que.addLast(x);
t--;
}
}
return idx;
}
}我们发现当循环大于 n 的时候，返回的结果一定是 max(skills)，所以我们只需要考虑在一个循环内能否找出连赢 k 场的玩家，可以使用一个变量 cnt 记录当前玩家的胜利次数，如果 cnt >= k，直接返回答案。否则返回 max(skills)
代码如下：
class Solution {
public int findWinningPlayer(int[] skills, int k) {
int idx = 0;
int cnt = 0;
for(int i=1; i<skills.length; i++){
if(skills[i] > skills[idx]){
idx = i;
cnt = 0;
}
cnt++;
if(cnt >= k) return idx;
}
return idx;
}
}三、3176. 求出最长好子序列 I
本题可以使用dfs枚举选哪个/选或不选来解决，这里讲解枚举选哪个的做法。先定义dfs，我们需要当前下标 i，根据题目子序列中 seq[i] != seq[i+1] 的数不能超过 k 个，我们还需要上一次选择的下标 j，以及 seq[i] != seq[i+1] 的次数 k。所以可以定义 dfs(i，j，k)：前一个数为nums[j]时，[i，n-1]的中取出最大子序列，且该子序列 seq[i] != seq[i+1] 的次数不超过 k。
但是这么写记忆化时需要三个参数，会导致时间复杂度过大，如何优化呢？可以发现上面是从前往后遍历，所以枚举时需要一个参数来告诉它起始点是什么。但是如果反过来遍历，就可以直接省去这个参数，因为我们是从 j - 1，往前遍历，重新定义 dfs(j，k)：后一个数为nums[j]时，[0，j-1]的中取出最大子序列，且该子序列 seq[i] != seq[i+1] 的次数不超过 k。
代码如下：
class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length;
memo = new int[n+1][k+1];
for(int[] row : memo)
Arrays.fill(row, -1);
return dfs(n,k,nums);
}
int[][] memo;
int dfs(int j, int k, int[] nums){
int res = 0;
if(memo[j][k] != -1) return memo[j][k];
for(int i=0; i<j; i++){
if(j==nums.length || nums[i] == nums[j])
res = Math.max(res, dfs(i, k, nums)+1);
else if(k > 0)
res = Math.max(res, dfs(i, k-1, nums)+1);
}
return memo[j][k] = res;
}
}递推写法
f[i][j]：以 i 为结尾的子序列中最多有 j 个满足相邻元素不相等的最长子序列长度
假设 k < i：
- nums[i] == nums[k]，f[i][j] = Math.max(f[i][j]，f[k][j]+1)
- nums[i] != nums[k]，f[i][j] = Math.max(f[i][j]，f[k][j]+1)
class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length;
int[][] f = new int[n+1][k+1];
int ans = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++){
f[i][0] = map.merge(nums[i], 1, Integer::sum);
ans = Math.max(ans, f[i][0]);
}
for(int j = 1; j <= k; j++){
f[0][j] = f[0][0];
}
for(int j=1; j<n; j++){
for(int a=1; a<=k; a++){
for(int i=0; i<j; i++){
if(nums[i]==nums[j])
f[j][a] = Math.max(f[j][a], f[i][a]+1);
else
f[j][a] = Math.max(f[j][a], f[i][a-1]+1);
}
}
ans = Math.max(ans, f[j][k]);
}
return ans;
}
}
四、3177. 求出最长好子序列 II
本题和上一题一样，但是数据范围更大，上述n^2*k的做法超时了，如何优化?？我们可以把f[i][j] 中的 i 转换成对应的 nums[i]，这时 f[x][j]：以 x (即nums[i]）结尾的子序列中最多有 j 个满足相邻元素不相等的最长子序列长度。
假设 k < i：
- nums[k] == x，f[x][j] = Math.max(f[x][j]，f[x][j]+1)
- nums[k] != x，f[x][j] = Math.max(f[x][j]，f[nums[k]][j-1]+1)
上述写法可以合并 f[x][j] = Math.max(f[x][j]+1，f[nums[k]][j-1]+1)，我们可以额外维护一个mx[j] = max(f[nums[k]][j-1])就可以在O(1)时间算出f[x][j]
public class Solution {
public int maximumLength(int[] nums, int k) {
Map<Integer, int[]> fs = new HashMap<>();
int[] mx = new int[k + 2];
for (int x : nums) {
int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
for (int j = k; j >= 0; j--) {
f[j] = Math.max(f[j], mx[j]) + 1;
mx[j + 1] = Math.max(mx[j + 1], f[j]);//同01背包，防止覆盖还需使用的值
}
}
return mx[k + 1];
}
}
