力扣20-有效的括号&力扣22-括号生成

举报
WuShF 发表于 2023/02/28 23:42:31 2023/02/28
【摘要】 力扣20-有效的括号&力扣22-括号生成

有效的括号

原题链接:https://leetcode.cn/problems/valid-parentheses/

题目描述

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

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

示例 1:

输入:s = “()”
输出:true

示例 2:

输入:s = “()[]{}”
输出:true

示例 3:

输入:s = “(]”
输出:false

栈容器

对于一个字符串,比如"([{}[)",我们需要从一端开始读入数据,同时将新读入的数据和已有数据对比,判断是否符合条件,即左右括号是否对应。
如果相同,则弹出已经存储的对应字符。如果不同,则存储起来,将末尾元素用于下次对比。

  1. 先读入'(',储存起来。
  2. 然后读入'[',目前存储的最后一个元素是'(',判断不相等,继续循环。
  3. 然后读入'{',目前存储的最后一个元素是'[',判断不相等,继续循环。
  4. 然后读入'}',目前存储的最后一个元素是'{',判断符合条件,弹出元素,继续循环。
  5. 然后读入'[',目前存储的最后一个元素是'[',返回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
image.png

其他方法

❌使用循环抠掉中间

如果字符串符合条件,那么居中位置一定是"()""[]""{}",将这部分抠去后的新字符串的中心位置,也一定是这几个字符串。
但如果字符串一侧也有"()""[]""{}",如"{(){}[]}"则容易被误判,不建议使用

✔️双指针对比

由于输入类型是字符串,我们可以使用双指针的方法取值对比,比较简单,在此不放代码。

括号生成

原题链接:https://leetcode.cn/problems/generate-parentheses/

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

递归裁剪

递归比较考验思维,我们可以具几个简单的例子来理清代码思路。
如果n=2,我们使用穷举法,有两情况 :"(())""()()"
显然,我们需要监控的量很多:左括号数量、右括号数量、结果字符串等,无法使用return一次性返回并接收。
因此,我们使用引用的方法,将结果字符串等相关变量声明在函数外,使用引用的方法读取或修改。
生成的括号是有效的,因此我们需要先插入左括号'('

  1. 结果字符串为"("
  2. 分两种情况,都需要执行:追加左括号'('或追加右括号')'
  3. 追加完左括号后,结果字符串为"((",接下来递归分别追加两次右括号')'
  4. 回到第二步的第二种情况,追加完右括号后的结果字符串为"()"
  5. 重复第一步和第二步,得到结果字符串"()()"

对于结束条件的判定

由于我们输入的是“生成括号的对数”,因此,输入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
image.png

好好学习,天天向上🚀

这次的比较简短,但挺费脑子的(对我这个萌新是这样的😢)。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。