算法打卡第11天
36.有效的括号
（力扣20题）
示例 1：
**输入：**s = “()”
**输出：**true
示例 2：
**输入：**s = “()[]{}”
**输出：**true
示例 3：
**输入：**s = “(]”
**输出：**false
示例 4：
**输入：**s = “([])”
**输出：**true
提示：
-
1 <= s.length <= 104 -
s仅由括号'()[]{}'组成 -
括号匹配是使用栈解决的经典问题。
Linux系统，系统是如何知道进入了目录呢 ，也是栈的应用
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
- 解题思路
- 初步判断：如果字符串长度为奇数，直接返回
false，因为合法的括号字符串长度必须是偶数。 - 初始化栈：定义一个栈
st，用于存储右括号。 - 遍历字符串：
- 遇到左括号（
(、[、{），将对应的右括号（)、]、}）压入栈中。 - 遇到右括号时，检查栈是否为空或栈顶元素是否与当前右括号匹配。如果不匹配或栈为空，返回
false；否则弹出栈顶元素。
- 遇到左括号（
- 最终判断：遍历结束后，检查栈是否为空。如果栈为空，说明所有左括号都找到了对应的右括号，返回
true；否则返回false。
这种方法利用了栈的“后进先出”特性，确保每个左括号都能找到对应的右括号，从而高效地判断括号字符串是否合法
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
#include <iostream>
#include <stack>
using namespace std;
class Solution
{
public:bool isValid(string s){// 如果s的长度为奇数，一定不符合要求if (s.size() % 2 != 0){return false;}// 定义栈stack<char> st;for (int i = 0; i < s.size(); i++){// 处理左括号if (s[i] == '('){st.push(')');}else if (s[i] == '['){st.push(']');}else if (s[i] == '{'){st.push('}');}// 第三种情况：遍历字符串匹配的过程中，没有遍历完栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。else if(st.empty() || st.top() != s[i] ){return false;}// 匹配到了弹出匹配的else st.pop();}// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return truereturn st.empty();}
};
37.删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= s.length <= 105s仅由小写英文字母组成。
- 解题思路
本题目标是移除字符串中连续重复的字符。我们利用栈的特性来解决这个问题。遍历字符串的每个字符，如果栈为空或当前字符与栈顶字符不相等，则将当前字符压入栈；如果当前字符与栈顶字符相等，则弹出栈顶字符，从而移除这对重复字符。遍历结束后，栈中剩下的字符即为移除重复后的结果。由于栈是后进先出的，我们需要将结果字符串反转，最终返回处理后的字符串。
代码
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
class Solution
{
public:string removeDuplicates(string s) {stack<char> st;for(char S: s){// // 如果栈为空，或者当前字符s与栈顶字符不相等if(st.empty() || S != st.top()){st.push(S);}// 弹出栈顶字符（即移除重复的字符）else{st.pop();} }// 定义一个空字符串，用于存储最终结果string result = "";// 将栈中元素放到result字符串汇总while(!st.empty()){result += st.top();st.pop();}// 反转字符串reverse(result.begin(), result.end());return result;}
};