本文主要是介绍LeetCode --- 132双周赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目列表
3174. 清除数字
3175. 找到连续赢 K 场比赛的第一位玩家
3176. 求出最长好子序列 I
3177. 求出最长好子序列 II
一、清理数字
这题直接根据题目,进行模拟即可,大体的思路是遍历字符串,遇到字母就加入答案,遇到数字就去掉答案中的最后一个字母,最后返回答案(类似进栈出栈),代码如下
class Solution {
public:string clearDigits(string s) {string ans;for(auto e:s){if(isdigit(e)) ans.pop_back();else ans += e;}return ans;}
};
二、找到连续赢k场的比赛的第一个玩家
这题的关键在于赢了的玩家会留下来和其他的玩家进行比赛,这就意味了在他之前参加比赛的人的skill都要小于他
- 如果n个人比完了,其中没有人赢下k场比赛,那么第一个赢下k场比赛的玩家必然是skill最大的那个
- 我们还要考虑在skill最大的玩家还没出现之前,就已经有玩家赢得k场比赛的情况
具体代码如下
class Solution {
public:int findWinningPlayer(vector<int>& skills, int k) {int n = skills.size();int pos = 0, cnt = 0;for(int i = 1; i < n; i++){if(skills[pos] < skills[i])pos = i, cnt = 0;cnt++;if(cnt == k) return pos;}return pos;}
};
三、求出最长好子序列 I & II
题目要求好子序列的最长长度,是一个子序列相关的动态规划问题。
状态定义:
子序列dp问题一般有两种类型,相邻相关 和 相邻无关 (看子序列的相邻元素之间是否存在某种关系/限制),分别对应两种状态的定义套路:相邻相关:以i为结尾的子序列的______,相邻无关:前i个元素中______。
本题显然是相邻相关的子序列问题,状态定义为 dp[i][j] 表示以i为结尾的子序列中最多有j个满足相邻元素不相等的最长子序列长度
状态转移方程:
- 当nums[i] == nums[k]时,dp[i][j] = max(dp[i][j], dp[k][j] + 1)
- 当nums[i] != nums[k]时,dp[i][j] = max(dp[i][j], dp[k][j-1] + 1)
- 其中 k < i
初始化:考虑 j = 0 的情况,即最多有0个相邻元素相等的情况(等价于子序列中的元素全部相同),边遍历数组便统计数组出现次数即可。
代码如下
class Solution {
public:int maximumLength(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int> mp; // 记录相同元素的个数int ans = 0;vector<vector<int>> dp(n, vector<int>(k + 1));// 初始化for(int i = 0; i < n;i ++){dp[i][0] = ++mp[nums[i]];ans = max(ans, dp[i][0]);}for(int j = 1; j <= k; j++){dp[0][j] = dp[0][0];}for(int i = 1; i < n; i++){ // 枚举以哪个数字为结尾for(int j = 1; j <= k; j++){ // 枚举最多有j个相邻不相同的情况for(int p = 0; p < i; p ++){ // 从之前的状态进行转移if(nums[i] == nums[p]) dp[i][j] = max(dp[i][j], dp[p][j] + 1);else dp[i][j] = max(dp[i][j], dp[p][j-1] + 1);}}ans = max(ans, dp[i][k]); // 注意答案是所有以i为结尾的子序列最大长度的最大值}return ans;}
};
时间复杂度为O(kn^2),显然是过不了的第四问的,如何优化时间复杂度???我们需要将第三层for循环求max的时间缩短为O(1),如何做?
这里有一个技巧,我们可以将下标换成值,在去思考如何优化,即将状态定义改为 dp[x][j] 表示以x=nums[i]为结尾的最多有j个相邻不相同元素的子序列最大长度
转移方程:
- 当 x == nums[k] 时,dp[x][j] = max(dp[x][j], dp[x][j] + 1) = dp[x][j]+1
- 当 x != y 时,dp[x][j] = max(dp[x][j], dp[y][j-1] + 1)
- 其中 k < i
故 dp[x][j] = max(dp[x][j],dp[y][j-1]) + 1,其中y是不等于x的出现过的数,所以我们只要维护好dp[y][j-1]的最大值就能在O(1)的时间复杂度内求出答案,即我们只要维护好前一列的最大值即可,即维护一个数组mx[j] = max(dp[y][j-1]),这里我们不需要额外关心 y == x的情况,因为dp[x][j] >= dp[x][j-1],所以不会对答案产生影响
代码如下
class Solution {
public:int maximumLength(vector<int>& nums, int k) {unordered_map<int,vector<int>> dp;vector<int> mx(k+2);for(int x:nums){if(!dp.contains(x)) dp[x].resize(k+1);auto& f = dp[x];for(int j = k; j >= 0; j--){ // 这里得是从后往前遍历,正着遍历会覆盖掉之前的mx[j]f[j] = max(f[j], mx[j]) + 1;mx[j+1] = max(mx[j+1], f[j]);}}return mx[k+1];}
};
总结:上面两种状态定义的大致思路是一样的,只是从下标改为了数值,转移方程也很相似,但是在维护max时,因为状态的转移和数值有关,我们需要在下标和数值之间建立联系,但问题是这种联系不是一一对应的,导致我们很难通过数值关系找到合适的下标来进行操作,但是我们只要将状态的定义和数值直接挂钩,我们就能很轻松的发现维护max的方法。
这里大家可以记住这样的一个技巧:当我们需要对dp进行优化时,且状态的转移和数值有关,我们可以优先考虑是否能将状态参数改为数值
这篇关于LeetCode --- 132双周赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!