算法练习——有效的括号

2021年1月16日LeetCode每日一题803. 打砖块,连续这么多天并查集的题目,还是没办法想到并查集,决定在这个寒假恶补数据结构和算法知识。今日一题就完成20. 有效的括号,这道题挺简单的,使用一个栈就能搞定,只要是左括号,就入栈,遇到右括号就弹出栈顶的元素进行比较是否为对应的左括号,如果不是,就为非有效的括号。基本上整体逻辑就搞定了,剩下的就是结果和特殊情况,如果第一个就是右括号,那么肯定无法匹配,因此直接返回false,只有当栈中的所有元素都弹出了才算全部匹配成功。因此代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public boolean isValid(String s) {
int length = s.length();
if (length < 2 || length % 2 != 0) return false;
char[] chars = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < length; i++) {
char c = chars[i];
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()
|| (c == ')' && stack.pop() != '(')
|| (c == ']' && stack.pop() != '[')
|| (c == '}' && stack.pop() != '{')
) {
return false;
}
}
}
return stack.isEmpty();
}
}

这道题对于熟悉栈的人来说是非常容易完成的,栈结构还有一道比较有趣的题目叫做后缀表达式。数据结构是支撑算法的基础,决定后天就开始攻克树结构和图结构,争取过年之前将这些结构和基本算法思想搞定。