当前位置：网站首页 > 技术文章 > 正文

算法之有效的括号（有效的括号 leetcode）

cac55 2024-10-29 13:14 10 浏览 0 评论

题目20："Valid Parentheses" (有效的括号)，给定一个只包括 '('，')'，'{'，'}'，'[' 和 ']' 的字符串，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

解题思路

要解决这个问题，我们可以使用栈来匹配括号。具体思路如下：

1. 创建一个空栈，用来存储左括号。

2. 遍历给定的字符串，对于每个字符：

3. 如果是左括号（'('，'{'，'['），则将其推入栈中。

4. 如果是右括号，则检查栈顶元素与当前字符是否匹配，若匹配则将栈顶元素出栈，继续遍历下一个字符；若不匹配，则返回false。

5. 若遍历结束后栈为空，则表示括号匹配完全，返回true；否则返回false。

算法实现

public class ValidParentheses {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();

        if(s == null || s.length() == 0) {
            return true;
        }
        // "([{}])"
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{') {
                char k = c == '(' ? ')' : c == '[' ? ']' : '}';
                stack.push(k);
            } else {
                if(stack.isEmpty()) {
                    return false;
                }
                char last = stack.pop();
                if(c != last) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }



    @Test
    public void test() {
        String s = "([{}])";

        boolean isValid = isValid2(s);

        assertTrue(isValid);

    }

时间复杂度分析

遍历字符串的时间复杂度为O(n)。

在每次遍历中，栈的操作包括压栈和弹栈，都是O(1)的时间复杂度。因此，整体时间复杂度为O(n)。

括号的用法

上一篇：小括号「」「」「」()()《》怎么打
下一篇：二年级数学~通过添加括号可以改变运算顺序，该如何去学习呢?

算法之有效的括号（有效的括号 leetcode）

解题思路

算法实现

时间复杂度分析

相关推荐

取消回复欢迎你发表评论:

爬虫项目:实现京东全网爬虫（python京东爬虫）

手机同时开百度导航和播放歌曲，如何实现导航声音大听歌声音小

UG软件各版本都支持哪些系统?（ug现在常用的版本）

一个小时多点，完成scrapy爬取官方网站新房的数据，50块到手

转载--HART 475手操器调试EJA变送器步骤

笔记本电脑鲁大师软件跑分你知道多少?可能你一直跑的都是假分

UG软件下载及安装教程，就是这么简单。

大华电脑客户端SmartPSS功能介绍（大华pss客户端操作教程）

origin如何绘制出漂亮的折线图?（origin怎样绘制折线图）

大华——快速配置工具(Configtool)使用方法

算法之有效的括号（有效的括号 leetcode）

解题思路

算法实现

时间复杂度分析

相关推荐

取消回复欢迎 你 发表评论:

爬虫项目:实现京东全网爬虫（python京东爬虫）

手机同时开百度导航和播放歌曲，如何实现导航声音大听歌声音小

UG软件各版本都支持哪些系统?（ug现在常用的版本）

一个小时多点，完成scrapy爬取官方网站新房的数据，50块到手

转载--HART 475手操器调试EJA变送器步骤

笔记本电脑鲁大师软件跑分你知道多少?可能你一直跑的都是假分

UG软件下载及安装教程，就是这么简单。

大华电脑客户端SmartPSS功能介绍（大华pss客户端操作教程）

origin如何绘制出漂亮的折线图?（origin怎样绘制折线图）

大华——快速配置工具(Configtool)使用方法

取消回复欢迎你发表评论: