目录
相同分数的最大操作数目 I
原题链接
题目描述
接口描述
思路分析
代码详解
3039. 进行操作使字符串为空
原题链接
题目描述
接口描述
思路分析
代码详解
相同分数的最大操作数目 II
原题链接
题目描述
接口描述
思路分析
代码详解
100205. 修改数组后最大化数组中的连续元素数目
原题链接
题目描述
接口描述
思路分析
代码详解
相同分数的最大操作数目 I
原题链接
相同分数的最大操作数目 I - 力扣 (LeetCode) 竞赛
题目描述
给你一个整数数组
nums，如果nums至少 包含2个元素，你可以执行以下操作：
- 选择
nums中的前两个元素并将它们删除。一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,4,5] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。 - 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。 由于只剩下 1 个元素，我们无法继续进行任何操作。示例 2：
输入：nums = [3,2,6,1,4] 输出：1 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。
接口描述
class Solution {
public:int maxOperations(vector<int>& nums) {}
};思路分析
直接模拟即可，时间复杂度O(N)
代码详解
class Solution {
public:int maxOperations(vector<int>& nums) {int ret = 0;for(int i = 0, t = -1, n = nums.size(); i < n - 1; i += 2){if(~t && nums[i] + nums[i + 1] != t) return ret;ret++, t = nums[i] + nums[i + 1];}return ret;}
};3039. 进行操作使字符串为空
原题链接
3039. 进行操作使字符串为空
题目描述
给你一个字符串
s。请你进行以下操作直到
s为 空 ：
- 每次操作 依次 遍历
'a'到'z'，如果当前字符出现在s中，那么删除出现位置 最早 的该字符。请你返回进行 最后 一次操作 之前 的字符串
s。示例 1：
输入：s = "aabcbbca" 输出："ba" 解释：我们进行以下操作： - 删除 s = "aabcbbca" 中加粗加斜字符，得到字符串 s = "abbca" 。 - 删除 s = "abbca" 中加粗加斜字符，得到字符串 s = "ba" 。 - 删除 s = "ba" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "ba" 。示例 2：
输入：s = "abcd" 输出："abcd" 解释：我们进行以下操作： - 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "abcd" 。
接口描述
class Solution {
public:string lastNonEmptyString(string s) {}
};思路分析
哈希计数+模拟
统计字符集的数目，然后每轮对剩余字符减一，当最大字符数目为1时，我们break，此时剩余的字符就是要返回的字符，其顺序和在s中最后出现位置的相对顺序相同
时间复杂度O(N)，空间复杂度O(U)，U为字符集大小
代码详解
class Solution
{
public:string lastNonEmptyString(string s){int last[26]{0}, n = s.size(), ma = 0;unordered_map<char, int> mp;string ret;for (int i = 0; i < n; i++)last[s[i] - 'a'] = i, mp[s[i]]++;for (auto p : mp)ma = max(ma, p.second);while (mp.size() && ma > 1){string del;ma = 0;for (auto& p : mp){if (!(--p.second))del.push_back(p.first);elsema = max(ma, p.second);}for(auto x : del) mp.erase(x);}for (auto p : mp){ret.push_back(p.first);}sort(ret.begin(), ret.end(), [&](char x, char y){return last[x-'a'] < last[y-'a'];});return ret;}
};
相同分数的最大操作数目 II
原题链接
相同分数的最大操作数目 II - 力扣 (LeetCode) 竞赛
题目描述
给你一个整数数组
nums，如果nums至少 包含2个元素，你可以执行以下操作中的 任意 一个：
- 选择
nums中最前面两个元素并且删除它们。- 选择
nums中最后两个元素并且删除它们。- 选择
nums中第一个和最后一个元素并且删除它们。一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4] 输出：3 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。 - 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。 - 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。 由于 nums 为空，我们无法继续进行任何操作。示例 2：
输入：nums = [3,2,6,1,4] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 - 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。 至多进行 2 次操作。
接口描述
class Solution
{
public:int f[2005][2005];int maxOperations(vector<int> &nums){}
};思路分析
区间DP
从数据范围上看应该用O(N^2)的算法，而题目所给操作都是在数组边界上进行，则很容易想到区间dp
首先要明白最大操作次数对应的每次操作的元素和k只有三种情况：nums[0] + nums[1], nums[n - 1] + nums[n - 2], nums[0] + nums[n - 1]
定义状态f[l][r]为最大操作次数对应的每次操作的元素和为k时的最大操作次数
那么转移方程有三，分别对应三种操作：
if (nums[l] + nums[l + 1] == k)
res = max(res, dfs(l + 2, r) + 1);
if (nums[l] + nums[r] == k)
res = max(res, dfs(l + 1, r - 1) + 1);
if (nums[r - 1] + nums[r] == k)
res = max(res, dfs(l, r - 2) + 1);
我们进行三次区间DP即可
时间复杂度O(N^2)，空间复杂度O(N^2)
代码详解
class Solution
{
public:int f[2005][2005];int maxOperations(vector<int> &nums){int ret = 0, n = nums.size();for (auto k : {nums[0] + nums[1], nums[n - 1] + nums[n - 2], nums[0] + nums[n - 1]}){memset(f, -1, sizeof(f));function<int(int, int)> dfs = [&](int l, int r){if (l >= r)return 0;if (~f[l][r])return f[l][r];int res = 0;if (nums[l] + nums[l + 1] == k)res = max(res, dfs(l + 2, r) + 1);if (nums[l] + nums[r] == k)res = max(res, dfs(l + 1, r - 1) + 1);if (nums[r - 1] + nums[r] == k)res = max(res, dfs(l, r - 2) + 1);return f[l][r] = res;};ret = max(ret, dfs(0, n - 1));}return ret;}
};
100205. 修改数组后最大化数组中的连续元素数目
原题链接
修改数组后最大化数组中的连续元素数目 - 力扣 (LeetCode) 竞赛
题目描述
给你一个下标从 0 开始只包含 正 整数的数组
nums。一开始，你可以将数组中 任意数量 元素增加 至多
1。修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，
[3, 4, 5]是连续的，但是[3, 4, 6]和[1, 1, 2, 3]不是连续的。请你返回 最多 可以选出的元素数目。
示例 1：
输入：nums = [2,1,5,1,1] 输出：3 解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。 我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。 最多可以得到 3 个连续元素。示例 2：
输入：nums = [1,4,7,10] 输出：1 解释：我们可以选择的最多元素数目是 1 。提示：
1 <= nums.length <= 1051 <= nums[i] <= 106
接口描述
class Solution
{
public:int maxSelectedElements(vector<int> &nums){}
};思路分析
最长连续子序列变形
如果给你一个序列，求最长连续子序列，那么一次遍历就能得到
那么现在给你一个乱序的nums，并且允许你将某些数字加1，让你求最长连续子序列，又该如何呢？
首先我们将nums升序排序，然后注意到数组长度范围1e5而数据范围只有1e6，这是本题的关键
那么我们可以统计记录nums的最小值l和最大值r，然后记录每个数字出现次数cnt[x]
对于cnt[x]>1的数字，我们直接拿出一个变成x+1，因为这样只会让连续序列更长（注意维护r，因为这一点导致我没有AC，有几个样例没过QAQ）
然后我们一次遍历得到最长连续子序列即可，不过有所不同，我们注意到有一些cnt[x]=1的数字+1也是有可能让最长连续子序列变长的，所以求解步骤如下：
- 枚举i，从l遍历到r，当前最长连续子序列长度为s，s的最长可操作后缀长度为pre
- 如果i存在，那么s++，否则s = pre，pre=0（因为当前序列断了，我们把前面能右移的后缀拿过来）
- 如果i在nums中存在并且未进行+1操作，那么pre++，否则pre=0
- 维护ret即可
时间复杂度O(nlogn)，空间复杂度O(n)
代码详解
class Solution
{
public:int cnt[1000005];int maxSelectedElements(vector<int> &nums){memset(cnt, 0, sizeof cnt);bitset<1000005> vis;unordered_set<int> mp(nums.begin(), nums.end());sort(nums.begin(), nums.end());int l = nums[0], r = nums.back(), ret = 1;for (auto x : nums)cnt[x]++;for (auto x : nums)if (cnt[x] > 1)cnt[x + 1]++, cnt[x]--, vis[x] = 1, r = max(r , x + 1);for (int i = l, pre = 0, s = 0; i <= r; i++){if(cnt[i]) s++;else{s = pre, pre = 0;continue;}if (mp.count(i) && !vis[i]) pre++;else pre = 0;ret = max(ret , s);}return ret;}
};
