网站怎么做用户体验,做网站图片要求,wordpress 时光轴代码,百度小程序在哪里打开目录
一、3174. 清除数字
二、3175. 找到连续赢 K 场比赛的第一位玩家
三、3176. 求出最长好子序列 I
四、3177. 求出最长好子序列 II 一、3174. 清除数字 本题可以使用栈来模拟#xff0c;遇到数字弹出栈顶元素#xff0c;遇到字母入栈。 代码如下#xff1a;
//使用字…目录
一、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;Dequeint[] que new ArrayDeque();for(int i0; in; 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 i1; iskills.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[i1] 的数不能超过 k 个我们还需要上一次选择的下标 j以及 seq[i] ! seq[i1] 的次数 k。所以可以定义 dfs(ijk)前一个数为nums[j]时[in-1]的中取出最大子序列且该子序列 seq[i] ! seq[i1] 的次数不超过 k。 但是这么写记忆化时需要三个参数会导致时间复杂度过大如何优化呢可以发现上面是从前往后遍历所以枚举时需要一个参数来告诉它起始点是什么。但是如果反过来遍历就可以直接省去这个参数因为我们是从 j - 1往前遍历重新定义 dfs(jk)后一个数为nums[j]时[0j-1]的中取出最大子序列且该子序列 seq[i] ! seq[i1] 的次数不超过 k。 代码如下
class Solution {public int maximumLength(int[] nums, int k) {int n nums.length;memo new int[n1][k1];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 i0; ij; i){if(jnums.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[n1][k1];int ans 0;MapInteger, 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 j1; jn; j){for(int a1; ak; a){ for(int i0; ij; 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] xf[x][j] Math.max(f[x][j]f[x][j]1)nums[k] ! xf[x][j] Math.max(f[x][j]f[nums[k]][j-1]1) 上述写法可以合并 f[x][j] Math.max(f[x][j]1f[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) {MapInteger, 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];}
}
