6. 2216. 美化数组的最少删除数(中等)
2216. 美化数组的最少删除数 - 力扣（LeetCode）
思想
1.给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length为偶数- 对所有满足
i % 2 == 0的下标i，nums[i] != nums[i + 1]均成立
注意，空数组同样认为是美丽数组。
你可以从nums中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使ums变为美丽数组所需删除的 最少 元素数目。
2.nums[i] != nums[i + 1]反映相邻元素，且要删除元素，且是顺序遍历，想到栈。根据栈的大小来判断放不放入当前元素，nums.length为偶数最终结束遍历再判断，决定是否要弹出最后一个元素。
代码
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size();
vector<int> stk;
for (int i = 0; i < n; ++i) {
// 奇数个数，最后一个为偶数下标
if ((int)stk.size() & 1) {
// 不满足条件不能放入
if (nums[i] == stk.back()) {
// 最后一个数，保证为偶数还要再删除一个元素
if (i == n - 1)
stk.pop_back();
}
// 满足条件可以放入
else {
stk.push_back(nums[i]);
}
}
// 偶数个数，最后一个为奇数下标
else {
// 最后一个数不能放，否则变为奇数
if (i < n - 1)
stk.push_back(nums[i]);
}
}
return n - (int)stk.size();
}
};
优化最后一个元素处理，遍历完再判断，不影响遍历
// 最后一个元素遍历结束再判断
if ((int)stk.size() & 1)
stk.pop_back();
7. 1209. 删除字符串中的所有相邻重复项II(中等，超时，学习)
1209. 删除字符串中的所有相邻重复项 II - 力扣（LeetCode）
思想
1.给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
2.连续相等k个相同的元素，可以把pair<字符,个数>当做栈的元素，通过判断个数来决定压栈还是出栈
代码
超时代码
class Solution {
public:
string removeDuplicates(string s, int k) {
int n=s.size();
string stk;
for(int i=0;i<n;++i){
if(stk.size()<k-1) stk.push_back(s[i]);
else{
bool tag=true;
for(int j=0;j<k-1;++j){
if(stk[stk.size()-1-j]!=s[i]){
tag=false;
break;
}
}
if(tag){
for(int j=0;j<k-1;++j) stk.pop_back();
}
else stk.push_back(s[i]);
}
}
return stk;
}
};
8. 735. 小行星碰撞(中等)
思想
1.给定一个整数数组 asteroids，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
2.碰撞就是邻项元素消除，只不过消除条件不一样
代码
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int n = asteroids.size();
vector<int> stk;
for (int i = 0; i < n; ++i) {
if (stk.empty())
stk.push_back(asteroids[i]);
else {
bool tag = true;
// 只有back向右移动，当前向左移动才会撞，多次判断用while
while (!stk.empty() && (stk.back() > 0 && asteroids[i] < 0)) {
if (abs(stk.back()) > abs(asteroids[i])) {
tag = false;
break;
} else if (abs(stk.back()) == abs(asteroids[i])) {
tag = false;
stk.pop_back();
break;
} else {
stk.pop_back();
}
}
if (tag)
stk.push_back(asteroids[i]);
}
}
return stk;
}
};
四.合法括号字符串(RBS)
1.套路
2.题目描述
3.学习经验
1. 20. 有效的括号(简单)
思想
1.给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
2,依然是邻项消除问题
代码
class Solution {
public:
bool isValid(string s) {
int n = s.size();
string stk;
for (int i = 0; i < n; ++i) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[')
stk.push_back(s[i]);
else {
if (stk.empty())
return false;
else {
if ((s[i] == ')' && stk.back() != '(') ||
(s[i] == '}' && stk.back() != '{') ||
(s[i] == ']' && stk.back() != '['))
return false;
else
stk.pop_back();
}
}
}
// 左括号也不能剩下
return stk.empty();
}
};
2. 921. 使括号有效的最少添加(中等)
921. 使括号有效的最少添加 - 力扣（LeetCode）
思想
1.只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串s，在每一次操作中，你都可以在字符串的任何位置插入一个括号 - 例如，如果
s = "()))"，你可以插入一个开始括号为"(()))"或结束括号为"())))"。
返回 为使结果字符串s有效而必须添加的最少括号数。
2.这题跟[[六.栈#5. 1003. 检查替换后的词是否有效(中等)]]一样，是()为模式匹配串，然后可以递归地删除，这题就是求重复删除()剩下的字符串的长度，就是要补的括号的个数
3.别人的另一种理解:
将「有效括号问题」转化为「分值有效性」的数学判定。
使用 score 代指处理过程中的得分，将 ( 记为 +1，将 ) 记为 -1。
一个有效的括号应当在整个过程中不出现负数，因此一旦 score 出现负数，我们需要马上增加 ( 来确保合法性；当整个 s 处理完后，还需要添加 socre 等同的 ) 来确保合法性。
代码
栈模拟:
class Solution {
public:
int minAddToMakeValid(string s) {
int n = s.size();
string stk;
for (int i = 0; i < n; ++i) {
if (s[i] == '(')
stk.push_back(s[i]);
else {
if (!stk.empty() && stk.back() == '(')
stk.pop_back();
else
stk.push_back(s[i]);
}
}
return stk.size();
}
};
分值有效性:
class Solution {
public:
int minAddToMakeValid(string s) {
int n = s.size();
int res = 0, score = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(')
++score;
else
--score;
// 右括号多
if (score < 0) {
score = 0;
++res;
}
}
// 把剩余左括号加上
return res + score;
}
};