算法打卡第11天

36.有效的括号

（力扣20题）

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

• 1 <= s.length <= 104

• s 仅由括号 '()[]{}' 组成

• 括号匹配是使用栈解决的经典问题。

Linux系统，系统是如何知道进入了目录呢 ，也是栈的应用

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

• 解题思路

1. 初步判断：如果字符串长度为奇数，直接返回false，因为合法的括号字符串长度必须是偶数。
2. 初始化栈：定义一个栈st，用于存储右括号。
3. 遍历字符串：
   • 遇到左括号（(、[、{），将对应的右括号（)、]、}）压入栈中。
   • 遇到右括号时，检查栈是否为空或栈顶元素是否与当前右括号匹配。如果不匹配或栈为空，返回false；否则弹出栈顶元素。
4. 最终判断：遍历结束后，检查栈是否为空。如果栈为空，说明所有左括号都找到了对应的右括号，返回true；否则返回false。

这种方法利用了栈的“后进先出”特性，确保每个左括号都能找到对应的右括号，从而高效地判断括号字符串是否合法

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

#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. 1 <= s.length <= 105
2. s 仅由小写英文字母组成。

• 解题思路

本题目标是移除字符串中连续重复的字符。我们利用栈的特性来解决这个问题。遍历字符串的每个字符，如果栈为空或当前字符与栈顶字符不相等，则将当前字符压入栈；如果当前字符与栈顶字符相等，则弹出栈顶字符，从而移除这对重复字符。遍历结束后，栈中剩下的字符即为移除重复后的结果。由于栈是后进先出的，我们需要将结果字符串反转，最终返回处理后的字符串。

代码

#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;}
};