三种 tac bsp div 返回 意思 这才 帮助 style
这星期听别人说在做LeetCode,让他分享一题来看看。试了感觉挺有意思,可以培养自己的思路,还能方便的查看优秀的解决方案。准备自己也开始。
解决方案通常有多种多样,我觉得把自己的解决思路记录下来,阶段性查看,一定能对自己有帮助。
这是我做的第一题,所以记录也从这题开始,之后尽力以简短的说明,描述出思路,方便以后能回顾到简介明了的记录。
20. Valid Parentheses
Given a string containing just the characters
,
- ‘(‘
,
- ‘)‘
,
- ‘{‘
,
- ‘}‘
and
- ‘[‘
, determine if the input string is valid.
- ‘]‘
The brackets must close in the correct order,
and
- "()"
are all valid but
- "()[]{}"
and
- "(]"
are not.
- "([)]"
给定一个字符串,只包含三种括号字符,需要确认是否有效
- //一开始审题不仔细,没有注意到只有括号字符,所以按有其他字符思考了
- //思路:假如输入的字符有效(即所有括号都被正确闭合),那在嵌套的最里层,一定存在至少一对括号,里面没有其他任何括号字符。
- //那只要找到它,把它和其中的内容一起从字符串中删除。剩下的字符串,要么没有任何一个括号字符,要么仍然至少存在一对括号里面没有其他括号字符。
- //循环,剔除所有正常使用的成对的括号,剩下的字符串中,如果还有括号字符则输入值无效,反之有效
- //文字描述可能不够清晰,上代码
- /**
- * @param {string} s
- * @return {boolean}
- */
- var isValid = function(s) {
- var str = s;
- var reg1 = new RegExp(/\([^\[\]\{\}\(\)]*\)/); //匹配()中无其他括号字符的字符串
- var reg2 = new RegExp(/\[[^\[\]\{\}\(\)]*\]/);
- var reg3 = new RegExp(/\{[^\[\]\{\}\(\)]*\}/);
- var reg4 = new RegExp(/[\[\]\{\}\(\)]/);
- while (reg1.test(str) || reg2.test(str) || reg3.test(str)) { //如果还有任意一种正确的成对括号,则继续循环
- str = str.replace(reg1, ‘‘); //如匹配到正确的成对括号字符串,用空字符串替换,从而删除
- str = str.replace(reg2, ‘‘);
- str = str.replace(reg3, ‘‘);
- }
- return ! reg4.test(str); //检测最后剩下的字符串,如有任意括号字符,则输入无效,返回false
- };
以上是第一次做LeetCode,提交以后把我给惭愧的,做的慢都不说,运行效率惨不忍睹。马上意识到觉得自己一定是用了不太好的方法,决定去借鉴别人的思路
- public boolean isValid(String s) {
- Stack<Character> stack = new Stack<Character>();
- for (char c : s.toCharArray()) {
- if (c == ‘(‘)
- stack.push(‘)‘);
- else if (c == ‘{‘)
- stack.push(‘}‘);
- else if (c == ‘[‘)
- stack.push(‘]‘);
- else if (stack.isEmpty() || stack.pop() != c)
- return false;
- }
- return stack.isEmpty();
- }
讨论中最热的一个是java写的,最然不会java,但还好这题写的简单,不会java也不妨碍理解其思路
一开始被第三个else if整蒙了,怎么都想不通为什么堆里最后的元素不等于循环的字符,就是无效输入,有其他非括号字符怎么办。
回去看题,这才发现自己审题不仔细,没看到只有括号字符...
我对热门解法思路的理解:假如输入有效,则从左往右第一个右括号前面一个字符必须为其对应的左括号,否则无效。如对应则此对括号匹配,继续向右的第一个右括号,和其前面第一个非已匹配 的左括号必须对应,否则无效。。。到最后如有效则恰好所有括号字符两俩匹配
利用这一特点。把输入字符分割成数组,遍历,匹配到左括号,则使用栈记录其对应的右括号(用于与匹配的括号对比)。如遇到右括号,但栈空,则说明出现单独的右括号,输入无效返回false;栈不空,则把最后添加的元素拿出来和遍历到的右括号对比,如一样,则说明和其前面最近的一个左括号成对,是正确使用,反之输入无效,返回false;
循环完,如栈空,则字符都两两匹配,无单独左括号,输入有效返回true,反正返回false。
对其解法,我觉得有两点让我很有启发,
1.巧妙利用无其他字符,想到括号对应规则,让函数只需要遍历一遍输入的字符串转成的数组,效率相当高
2.用栈来存储左括号对应的右括号,利用栈后进先出的特点,让右括号可以和其前面最近的左括号尝试匹配。pop删除并返回,不匹配直接终止程序,返回false,当然不用管栈,匹配到则正好删除匹配好了的括号,让下一个右括号能匹配最近的、未匹配的左括号
其构想让我觉得很有意思,禁不住想自己写一遍
- /**
- * @param {string} s
- * @return {boolean}
- */
- var isValid = function(s) {
- var stack = [];//他使用栈,主要就是利用其后入先出,这样的话js用数组也能实现同样的功能
- var strArr = s.split(‘‘);
- for(var i in strArr){
- if(strArr[i] == ‘(‘) stack.push(‘)‘);
- else if(strArr[i] == ‘{‘) stack.push(‘}‘);
- else if(strArr[i] == ‘[‘) stack.push(‘]‘);
- else if(stack.length == 0||stack.pop() != strArr[i]) return false;
- }
- return stack.length == 0;
- };
- //解法一模一样,只是把换成了js实现
换成这种解法,运行效率果然大幅度提升。一想到其他题也能领略到其他优秀思路,不经有些激动。
不过由于自己水平还不够,做题效率不高,而且还需要学习其他知识,所以不准备短时间多做。一周7题,争取能长时间保持,相信哪怕一天只一题,积累下来,也能提高自己。
LeetCode解题笔记 - 20. Valid Parentheses
三种 tac bsp div 返回 意思 这才 帮助 style
原文:http://www.cnblogs.com/liyan-web/p/7816774.html
来源: http://www.bubuko.com/infodetail-2390016.html