网站建设名头,正规网站备案信息表,中国建设银行官网站企业网银下载,wordpress 设置缓存Leetcode 第 124 场双周赛题解 Leetcode 第 124 场双周赛题解题目1#xff1a;3038. 相同分数的最大操作数目 I思路代码复杂度分析 题目2#xff1a;3039. 进行操作使字符串为空思路代码复杂度分析 题目3#xff1a;3040. 相同分数的最大操作数目 II思路代码复杂度分析 题目… Leetcode 第 124 场双周赛题解 Leetcode 第 124 场双周赛题解题目13038. 相同分数的最大操作数目 I思路代码复杂度分析 题目23039. 进行操作使字符串为空思路代码复杂度分析 题目33040. 相同分数的最大操作数目 II思路代码复杂度分析 题目43041. 修改数组后最大化数组中的连续元素数目思路代码复杂度分析 Leetcode 第 124 场双周赛题解
题目13038. 相同分数的最大操作数目 I
思路
设 score nums[0] nums[1]count 1。
从 i2 开始遍历数组如果 nums[i] nums[i 1] scorecount若不等或数字不够跳出。
返回 count。
代码
/** lc appleetcode.cn id3038 langcpp** [3038] 相同分数的最大操作数目 I*/// lc codestart
class Solution
{
public:int maxOperations(vectorint nums){if (nums.size() 2)return 0;int count 1;int score nums[0] nums[1];int n nums.size(), i 2;while (i 1 n){if (nums[i] nums[i 1] score){count;i 2;}elsebreak;}return count;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
题目23039. 进行操作使字符串为空
思路
操作的定义每次操作依次遍历 ‘a’ 到 ‘z’如果当前字符出现在 s 中那么删除出现位置最早的该字符如果存在的话。
最后一次操作之前的字符串 s 是出现次数最多的字符可能不止一个按最后出现位置下标从小到大排列的结果。
我们用一个哈希表 cnt 记录各字符的出现次数一个数组 lastIndex 记录每个字符最后一次出现的位置下标。
设 max_cnt *max_element(cnt.begin(), cnt.end())用一个数组 idx 记录 cnt 中元素值等于 max_cnt 的对应位置下标则 idx 里存储的就是答案字符串的字符在原字符串的最后一次出现的位置下标。
答案 ans 的长度就是数组 idx 的元素个数。
对 idx 进行增序排序遍历数组 idx则 ans[i] 即为 s[idx[i]]。
最后返回 ans。
代码
/** lc appleetcode.cn id3039 langcpp** [3039] 进行操作使字符串为空*/// lc codestart// 哈希 排序class Solution
{
public:string lastNonEmptyString(string s){if (s.empty())return ;vectorint cnt(26, 0); // 字符的出现次数vectorint lastIndex(26, -1); // 字符的最后下标for (int i 0; i s.length(); i){char c s[i];cnt[c - a];lastIndex[c - a] i;}int max_cnt *max_element(cnt.begin(), cnt.end());vectorint idx;for (int i 0; i 26; i){if (cnt[i] max_cnt)idx.push_back(lastIndex[i]);}sort(idx.begin(), idx.end());string ans(idx.size(), 0);for (int i 0; i idx.size(); i)ans[i] s[idx[i]];return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n∣Σ∣log∣Σ∣)其中 其中 n 为字符串s 的长度∣Σ∣ 为字符集合的大小本题中字符均为小写字母所以 ∣Σ∣26。
空间复杂度O(∣Σ∣)其中 ∣Σ∣ 为字符集合的大小本题中字符均为小写字母所以 ∣Σ∣26。
题目33040. 相同分数的最大操作数目 II
思路
区间 DP。
题解区间 DP 的套路Python/Java/C/Go
注意使用记忆化搜索不然会超时。
代码
/** lc appleetcode.cn id3040 langcpp** [3040] 相同分数的最大操作数目 II*/// lc codestart// 区间 DPclass Solution
{
public:int maxOperations(vectorint nums){if (nums.size() 2)return 0;int n nums.size();int memo[n][n];auto helper [](int i, int j, int target) - int{memset(memo, -1, sizeof(memo));functionint(int, int) dfs [](int i, int j) - int{if (i j)return 0;int res memo[i][j]; // 注意这里是引用if (res ! -1)return res;res 0;if (nums[i] nums[i 1] target)res max(res, dfs(i 2, j) 1);if (nums[j - 1] nums[j] target)res max(res, dfs(i, j - 2) 1);if (nums[i] nums[j] target)res max(res, dfs(i 1, j - 1) 1);return res;};return dfs(i, j);};// 最前面两个int res1 helper(2, n - 1, nums[0] nums[1]);// 最后两个int res2 helper(0, n - 3, nums[n - 2] nums[n - 1]);// 第一个和最后一个int res3 helper(1, n - 2, nums[0] nums[n - 1]);int ans max({res1, res2, res3}) 1; // 加上第一次操作return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n2)其中 n 为数组 nums 的长度。
空间复杂度O(n2)其中 n 为数组 nums 的长度。
题目43041. 修改数组后最大化数组中的连续元素数目
思路
子序列 DP。
题解本题最简单写法Python/Java/C/Go
代码
/** lc appleetcode.cn id3041 langcpp** [3041] 修改数组后最大化数组中的连续元素数目*/// lc codestart// 子序列 DPclass Solution
{
public:int maxSelectedElements(vectorint nums){if (nums.empty())return 0;// dp[i]: 以 i 结尾的连续递增序列的最大长度vectorint dp(1e6 1, 0);sort(nums.begin(), nums.end());// 状态转移for (int x : nums){dp[x 1] dp[x] 1;dp[x] dp[x - 1] 1;}return *max_element(dp.begin(), dp.end());}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 为数组 nums 的长度。
空间复杂度O(N)数据范围 N1e6。
