有效的括号-B站笔试题

数据结构和算法

发布于 2024-10-11 13:11:30

790

发布于 2024-10-11 13:11:30

文章被收录于专栏：数据结构和算法

在LeetCode的题解区看到这样一个评论，说这道题是 B站的笔试题，并且还不止一个人在 B站的笔试题中遇到。

其实这道题比较简单，直接使用一个栈即可解决，学会之后下次去面试的时候就能应对了，我们来看下。

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

有效字符串需满足：

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

示例 1：

输入：s = "()" 输出：true

示例 2：

输入：s = "()[]{}" 输出：true

示例 3：

输入：s = "(]" 输出：false

问题分析

这题是让判断字符串 s 是否有效，因为字符串 s 只包含 '()[]{}' ，我们可以使用一个栈来解决，如果遇到右括号，比如 ')'，']'，'}' ，就把与它们对应的左括号添加到栈中，如果遇到左括号，比如 '('，'['，'{' ，栈顶元素就出栈，然后判断和出栈的元素是否匹配，如果不匹配或者栈为空，直接返回 false ，来看下代码。

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();// 创建一个栈
        char[] chars = s.toCharArray();// 字符串 s 转换成字符数组
        for (char ch : chars) {// 遍历字符数组
            //如果是左括号，就把他们对应的右括号压栈
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '{') {
                stack.push('}');
            } else if (ch == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != ch) {
                return false;
            }
        }
        // 如果是有效的，左括号和右括号必须匹配，栈为空，否则就无效。
        return stack.isEmpty();
    }

你点的每个赞，我都认真当成了喜欢

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-10-31，如有侵权请联系 cloudcommunity@tencent.com 删除

面试