每日算法刷题Day52:7.24:leetcode 栈5道题，用时1h35min
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. 小行星碰撞(中等)
735. 小行星碰撞 - 力扣（LeetCode）
思想
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向右移动，当前向左移动才会撞，多次判断用whilewhile (!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. 有效的括号(简单)
20. 有效的括号 - 力扣（LeetCode）
思想
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;elsestk.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();elsestk.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;}
};