Leetcode 20题 有效的括号(Valid Parentheses) Java语言求解

2020年1月31日21:33:06算法 LeetCode评论311阅读模式

Leetcode 20题 有效的括号(Valid Parentheses) Java语言求解

题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。文章源自随机的未知-https://sjdwz.com/11117.html

有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。文章源自随机的未知-https://sjdwz.com/11117.html

做法

使用栈来进行辅助求解。
1、创建一个空栈;
2、使用循环对字符串进行遍历转3,遍历完毕退出循环转7;
3、如果当前字符为'('、'{'、'['则进栈,转2;
4、如果当前字符为')'、'}'、']',转5;
5、如果栈为空,则返回false,匹配不成功,结束程序;栈不空,转6;
6、弹出栈顶元素,如果栈顶元素不是与当前遍历到的字符相匹配的括号,则返回false,匹配不成功,结束程序;否则转2;
7、如果栈为空,则匹配成功,返回true,程序结束;否则返回false,匹配不成功,程序结束。文章源自随机的未知-https://sjdwz.com/11117.html

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack_match = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
                stack_match.push(s.charAt(i));
            }else if(s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
                if(stack_match.isEmpty())
                    return false;
                char current = stack_match.pop();

                if(current == '(' && s.charAt(i)!=')')
                    return false;
                if(current == '[' && s.charAt(i)!=']')
                    return false;
                if(current == '{' && s.charAt(i)!='}')
                    return false;
            }
        }
        if(stack_match.isEmpty())
            return true;
        return false;
    }
}

案例说明

案例1:“( )”
1、创建空栈;
2、对字符串进行遍历;
3、第一个元素是”(” 进栈;当前栈中元素有”(”;
4、第二个元素是”)”,栈非空,弹出栈顶元素;栈顶元素为”(”,与”)”可以匹配;
5、字符串遍历完毕,栈空,返回true文章源自随机的未知-https://sjdwz.com/11117.html

案例2:“{ }[ ]”
1、创建空栈;
2、对字符串进行遍历;
3、第一个元素是”{” 进栈;当前栈中元素有”{”;
4、第二个元素是”}”,栈非空,弹出栈顶元素;栈顶元素为”{”,与”}”可以匹配;
5、第三个元素是”[”,进栈;当前栈中元素有”[”;
6、第二个元素是”]”,栈非空,弹出栈顶元素;栈顶元素为”[”,与”]”可以匹配;
7、字符串遍历完毕,栈空,返回true文章源自随机的未知-https://sjdwz.com/11117.html

案例3:”( ) ) ]”
1、创建空栈;
2、对字符串进行遍历;
3、第一个元素是”(” 进栈;当前栈中元素有”(”;
4、第二个元素是”)”,栈非空,弹出栈顶元素;栈顶元素为”(”,与”)可以匹配;
5、第三个元素是”)”,栈空,返回false,匹配不成功,程序结束。文章源自随机的未知-https://sjdwz.com/11117.html

案例4: ”( ( ( { [ } ] ) )”
1、创建空栈;
2、对字符串进行遍历;
3、第一个元素是”(” 进栈;当前栈中元素有”(”;
4、第二个元素是”(” 进栈;当前栈中元素有”( (”;;
5、第三个元素是”(” 进栈;当前栈中元素有”( ( (”;
6、第四个元素是”{” 进栈;当前栈中元素有”( ( ( {”;
7、第五个元素是”[” 进栈;当前栈中元素有”( ( ( { [”;
8、第六个元素是”}”,栈非空,弹出栈顶元素;栈顶元素为”[”,与”}”不可以匹配,返回false,程序结束。文章源自随机的未知-https://sjdwz.com/11117.html

欢迎关注

扫下方二维码即可关注:
Leetcode 20题 有效的括号(Valid Parentheses) Java语言求解文章源自随机的未知-https://sjdwz.com/11117.html

文章源自随机的未知-https://sjdwz.com/11117.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年1月31日21:33:06
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11117.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定