长沙网站开发方案,途牛网站建设策划书,金网科技有限公司,wordpress域名指向二级目录一、题目 二、解题思路
1、我的思路
我看到题目之后#xff0c;想着这可能是力扣里唯一一道我能秒杀的题目了
于是一波操作猛如虎写出了如下代码
public boolean isValid(String s) {char[] c s.toCharArray();for(int i0;ic.length;i){switch (c[i]){case (:if(c[i]…一、题目 二、解题思路
1、我的思路
我看到题目之后想着这可能是力扣里唯一一道我能秒杀的题目了
于是一波操作猛如虎写出了如下代码
public boolean isValid(String s) {char[] c s.toCharArray();for(int i0;ic.length;i){switch (c[i]){case (:if(c[i]!))return false;break;case [:if(c[i]!])return false;break;case {:if(c[i]!})return false;break;}}return true;}
运行的时候三个测试用例都通过了我心想这把稳了。信心满满地点击提交……
什么解答错误 嗷那没事了原来左括号后不一定跟的是右括号……这就回去重写
再仔细一思考猛然回想起当时学数据结构的时候遇到过的括号匹配问题。这可能要用到栈遇到左括号就让这个左括号进栈遇到右括号就出栈一个括号如果这两个括号能匹配就继续执行反之则直接返回false
于是有了如下的代码而且这段代码的运行效率竟然击败了98%的用户
char[] sc s.toCharArray();StackCharacter stack new Stack();for(int i0;isc.length;i){switch (sc[i]){case (:case {:case [:stack.push(sc[i]);break;default:if(stack.size()0){return false;}switch(stack.pop()){case (:if(sc[i]!))return false;break;case {:if(sc[i]!})return false;break;case [:if(sc[i]!])return false;break;}}}if(stack.size()!0){return false;}return true; 只不过我一开始没有考虑到循环中的
if(stack.size()0){return false;
}
和循环结束的
if(stack.size()!0){return false;
}
导致代码在测试 [ 和 ] 两个测试用例的时候都返回了错误的结果还好力扣上可以看到出错的执行用例所以我才能很快地找到问题
但是有很多算法竞赛是看不到执行出错的测试用例的所以在打算法竞赛时如果我们提交的代码出现了问题不妨自己输入一些数据进行测试而且要输入比较特殊的例子如 [ 和 ] 这样的极端例子
2、官方题解
class Solution {public boolean isValid(String s) {int n s.length();if (n % 2 1) {return false;}MapCharacter, Character pairs new HashMapCharacter, Character() {{put(), ();put(], [);put(}, {);}};DequeCharacter stack new LinkedListCharacter();for (int i 0; i n; i) {char ch s.charAt(i);if (pairs.containsKey(ch)) {if (stack.isEmpty() || stack.peek() ! pairs.get(ch)) {return false;}stack.pop();} else {stack.push(ch);}}return stack.isEmpty();}
}作者力扣官方题解
链接https://leetcode.cn/problems/valid-parentheses/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 三、栈
考虑到可能也有一些小伙伴不会用栈在这里给大家科普一下图片来源于《labuladong的算法笔记》
