【leetcode刷题】5.有效的括号——Java版

布满荆棘的人生 2021-09-09 02:10 321阅读 0赞

> 傻傻写了几百行代码，还不如一个好的思路。。。。。。
> 
> ——leetcode此题热评

## 前言 ##

> 这几天刷算法题一条发现一个事情
> 
> 以前总觉得我也不是专业搞算法的，算法可刷可不刷
> 
> 近几天联系下来发现，做算法真的对编码能力和思维方式有很大的提高
> 
> 所以最近会从`leetcode`100道热题里面按照`简单`——`中等`——`困难`的顺序刷下去
> 
> 跟着一条，每天进步亿点点！

## Question ##

难度：简单

> 给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。
> 
> 有效字符串需满足：
> 
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。
> 
> 示例 1：
> 
>     输入：s = "()"
>     输出：true
> 
> 示例 2：
> 
>     输入：s = "()[]{}"
>     输出：true
> 
> 示例 3：
> 
>     输入：s = "(]"
>     输出：false
> 
> 示例 4：
> 
>     输入：s = "([)]"
>     输出：false
> 
> 示例 5：
> 
>     输入：s = "{[]}"
>     输出：true
> 
> 提示：
> 
>     1 <= s.length <= 104
>     s 仅由括号 '()[]{}' 组成

## Solution ##

> 此题通用的解法都是`HashMap`加`栈`
> 
> 查找`ASCII`码字符对照表后可发现如下规律：
> 
> “\[”：91
> 
> “\]”：93
> 
> “(”：40
> 
> “)”：41
> 
> “\{”：123
> 
> “\}”：125
> 
> 能够互相匹配的一组括号相差1或者2

*  通过比较前后的`ASCII`值，将配对成功的剔除
 *  未配对的成功的放入新建的数组里
 *  最后判断数组的长度是否为`0`

## Code ##

> 所有`leetcode`代码已同步至[github][]
> 
> 欢迎`star`

class Solution { 
        public boolean isValid(String s) { 
            char[] charArray = s.toCharArray();
            char[] chars=new char[charArray.length];
            int count=0;
            for (int i = 0; i < charArray.length; i++) { 
                chars[count]=charArray[i];
                if (count!=0&&(chars[count]-chars[count-1]==1||chars[count]-chars[count-1]==2)){ 
                    count--;
                }else{ 
                    count++;
                }
            }
            return count==0;
        }
    }

## Result ##

> 复杂度分析
> 
>  *  时间复杂度：O(N) ,遍历一遍数组

![20210718094007390.png][]

--------------------

我是**一条**，一个在互联网摸爬滚打的程序员。

**道阻且长，行则将至**。大家的 **【点赞，收藏，关注】** 就是一条创作的最大动力，我们下期见！

[github]: https://github.com/lbsys/leetcode/tree/master/src/leetcode/editor/cn
[20210718094007390.png]: /images/20210901/39ad6bfe80774120adce60fd666e8a82.png