相同分数的最大操作数目 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. 进行操作使字符串为空
原题链接
- 进行操作使字符串为空
题目描述
给你一个字符串
s。
请你进行以下操作直到
s为 空 ：
- 每次操作 依次 遍历
'a'到'z'，如果当前字符出现在s中，那么删除出现位置 最早 的该字符。请你返回进行 最后 一次操作 之前 的字符串* *
s
- *。
示例 1：
**输入：**s = "aabcbbca" **输出：**"ba" **解释：**我们进行以下操作： - 删除 s = "***a***a***bc***bbca" 中加粗加斜字符，得到字符串 s = "abbca" 。 - 删除 s = "***ab***b***c***a" 中加粗加斜字符，得到字符串 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);
else
ma = 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;
}
};
版权归原作者 EQUINOX1 所有， 如有侵权，请联系我们删除。