有效的括号
原题链接：https://leetcode.cn/problems/valid-parentheses/
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
栈容器
对于一个字符串，比如"([{}[)"，我们需要从一端开始读入数据，同时将新读入的数据和已有数据对比，判断是否符合条件，即左右括号是否对应。
如果相同，则弹出已经存储的对应字符。如果不同，则存储起来，将末尾元素用于下次对比。
- 先读入
'('，储存起来。 - 然后读入
'['，目前存储的最后一个元素是'('，判断不相等，继续循环。 - 然后读入
'{'，目前存储的最后一个元素是'['，判断不相等，继续循环。 - 然后读入
'}'，目前存储的最后一个元素是'{'，判断符合条件，弹出元素，继续循环。 - 然后读入
'['，目前存储的最后一个元素是'['，返回false。
我们每次需要存取的，只是容器的末尾元素，因此，我们使用栈容器存储读取到的字符。
每次判断是否符合条件，需要判断两个不同的量：左括号和右括号，为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
上代码
代码中有一些需要注意的地方：
- 直接使用哈希表自带的统计方法判断是否存在，不存在时返回0，不执行if语句。
- 返回值为
left.empty()，当遍历完后，容器中仍有元素残留，表面左括号和右括号未一一对应，不为空，返回0。
class Solution {
public:
bool isValid(string s) {
stack<char>left;
unordered_map<char, char>right = {
{')','('},
{']','['},
{'}','{'}
};
for (int i = 0; i < s.size(); i++)
{
if (right.count(s[i]))
{
if (left.empty() || left.top() != right[s[i]])
{
return false;
}
left.pop();
}
else
left.push(s[i]);
}
return left.empty();
}
};运行结果
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了75.89%的用户
通过测试用例：92 / 92
其他方法
❌使用循环抠掉中间
如果字符串符合条件，那么居中位置一定是"()"或"[]"或"{}"，将这部分抠去后的新字符串的中心位置，也一定是这几个字符串。
但如果字符串一侧也有"()"或"[]"或"{}"，如"{(){}[]}"则容易被误判，不建议使用
✔️双指针对比
由于输入类型是字符串，我们可以使用双指针的方法取值对比，比较简单，在此不放代码。
括号生成
原题链接：https://leetcode.cn/problems/generate-parentheses/
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
- 1 <= n <= 8
递归裁剪
递归比较考验思维，我们可以具几个简单的例子来理清代码思路。
如果n=2，我们使用穷举法，有两情况 ："(())"和"()()"。
显然，我们需要监控的量很多：左括号数量、右括号数量、结果字符串等，无法使用return一次性返回并接收。
因此，我们使用引用的方法，将结果字符串等相关变量声明在函数外，使用引用的方法读取或修改。
生成的括号是有效的，因此我们需要先插入左括号'('：
- 结果字符串为
"("。 - 分两种情况，都需要执行：追加左括号
'('或追加右括号')'。 - 追加完左括号后，结果字符串为
"(("，接下来递归分别追加两次右括号')'。 - 回到第二步的第二种情况，追加完右括号后的结果字符串为
"()"。 - 重复第一步和第二步，得到结果字符串
"()()"。
对于结束条件的判定
由于我们输入的是“生成括号的对数”，因此，输入n，结果字符串长度为2n（一对括号包含左右括号共两个字符）。
对于左括号，它追加的执行条件为count(left)<n。
对于右括号，当存在多余的左括号时就可以尝试追加，因此执行条件为count(right)<count(left)。
对于递归结束条件，即字符串达到题目允许的最大长度时返回，最大长度为2n。
上代码
class Solution {
void backtrack(vector<string>& ans, string& cur, int left, int right, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (left < n) {
cur.push_back('(');
backtrack(ans, cur, left + 1, right, n);
cur.pop_back();
}
if (right < left) {
cur.push_back(')');
backtrack(ans, cur, left, right + 1, n);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};运行结果
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：11.2 MB, 在所有 C++ 提交中击败了67.69%的用户
通过测试用例：8 / 8
好好学习，天天向上🚀
这次的比较简短，但挺费脑子的（对我这个萌新是这样的😢）。
