Leetcode - 132双周赛

目录

一、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);elsef[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];}
}