lc2593
1.mask ll也会溢出 转vec bool
2.sort pii(nums,idx) 后标记自身 ＆左右
一次遍历即可
class Solution {
typedef long long ll;
public:
long long findScore(vector<int>& nums) {
ll ret = 0;
int n = nums.size();
if (n == 1) return nums[0];
vector<bool> mask(n, false);
// 1. 元素按“值+下标”排序
vector<pair<int, int>> arr;
for (int i = 0; i < n; ++i)
arr.emplace_back(nums[i], i);
sort(arr.begin(), arr.end());
// 2. 按排序处理，用mask标记
for (auto& [val, idx] : arr)
{
if (!mask[idx]) { // 当前元素未标记
ret += val;
mask[idx] = true; // 标记自身
if (idx > 0) mask[idx - 1] = true; // 标记左邻
if (idx < n - 1) mask[idx + 1] = true; // 标记右邻
}
}
return ret;
}
};
lc2155
presum预处理
class Solution {
public:
vector<int> maxScoreIndices(vector<int>& nums)
{
int n = nums.size();
vector<int> pre(n + 1);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i-1] + nums[i-1];
int max_s = 0;
vector<int> res;
for (int i = 0; i <= n; ++i) {
int l0 = i - pre[i];
int r1 = pre[n] - pre[i];
int s = l0 + r1;
if (s > max_s) {
max_s = s;
res = {i};
}
else if (s == max_s)
res.push_back(i);
}
return res;
}
};
lc2216
模拟栈
维护一个有效序列，遇到“偶数长度序列末尾元素和当前元素相同”的情况就替换末尾元素，最后保证序列是偶数长度
原数组长度减去有效长度得到最少删除次数
class Solution {
public:
int minDeletion(vector<int>& nums) {
vector<int> ans;
for (int num : nums) {
if (ans.size() > 0 &&num == ans.back() && ans.size() % 2 == 1)
continue;//ignore
else
ans.push_back(num);
}
int len = ans.size() % 2 == 0 ? ans.size() : ans.size() - 1;
return nums.size() - len;
}
};
lc2038
统计连续相同颜色的长度
class Solution {
public:
bool winnerOfGame(string colors)
{
int n = colors.size();
if (n < 3) return false;
int alice = 0, bob = 0;
int count = 1;
// 记录当前连续相同字符的长度
for (int i = 1; i < n; ++i) {
if (colors[i] == colors[i-1])
count++;//相等_计数
else
{ // 不等_统计上一段连续字符的可op
if (colors[i-1] == 'A')
alice += max(0, count - 2);
else
bob += max(0, count - 2);
count = 1;//重置
}
}
// 处理最后一段连续字符
if (colors.back() == 'A')
alice += max(0, count - 2);
else
bob += max(0, count - 2);
return alice > bob;
}
};
