这一部分，我们开始介绍“栈、队列、优先队列”。栈和队列虽然是简单的数据结构，但是使用这些简单的数据结构所解决的算法问题不一定简单。在这一章里，我们将来探索，和栈与队列相关的算法问题。
栈和队列的使用，栈和队列是两种基础的数据结构。Stack 这个基础数据结构的特点是：后进先出，这一点是非常重要的。下面请看 LeetCode 第 20 题：
例题：LeetCode 第 20 题：有效的括号
传送门：英文网址：20. Valid Parentheses ，中文网址：20. 有效的括号 。
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true示例 2:
输入: "()[]{}" 输出: true示例 3:
输入: "(]" 输出: false示例 4:
输入: "([)]" 输出: false示例 5:
输入: "{[]}" 输出: true
分析：典型应用，检查括号匹配，是文本编辑器常见的功能。
注意空字符串可被认为是有效字符串。
思路：问题本身非常容易。判断字符串中的括号匹配是否合法。遍历一遍这个字符串，使用一个 Stack 作为辅助空间。
一旦遇到左方向的符号，就把这个符号推入栈。
一旦遇到右方向的符号，将栈的栈顶元素出栈，就须要判断是否对应匹配。
Stack 中只是存放左方向的符号：“{”、“[”、“(”，在整个方法返回之前，一定要判断一下 Stack 是否为空。因为 Stack 有可能出现全是左括号的情况。即：在栈中还有元素的情况下，待检测的字符串一定是不符合题意的。
我的解答（看起来有些繁琐）：
下面我按照老师的解法，写了一个不是优化了很多的解法：
Java 代码：
public class Solution {
public boolean isValid(String s) {
boolean isValid = false;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '{' || c == '(' || c == '[') {
stack.push(c);
}
if (c == '}' || c == ')' || c == ']') {
// 出栈之前，应该先检查一下栈中是否还有元素
if (stack.isEmpty()) {
return isValid;
}
Character popElement = stack.pop();
Character match = null;
if (c == '}') {
match = '{';
}
if (c == ']') {
match = '[';
}
if (c == ')') {
match = '(';
}
if (popElement != match) {
return isValid;
}
}
}
if (stack.isEmpty()) {
isValid = true;
}
return isValid;
}
public static void main(String[] args) {
Solution solution = new Solution();
boolean result = solution.isValid("8{90[s(d)f]44}33");
System.out.println(result);
}
}
说明：最后的这一步：
if (stack.isEmpty()) {
isValid = true;
}
很容易忽略，请留意。
学到栈的时候，也学习了一些经典的使用栈解决问题，我们要思考一下为什么使用栈？
使用栈的原因：在一个嵌套的关系中，通过栈顶元素来获得最近的那个我们须要处理的元素。
栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素。
Python 代码：
# 20. 有效的括号
# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
d = ["()", "[]", "{}"]
for i in range(0, len(s)):
stack.append(s[i])
if len(stack) >= 2 and stack[-2] + stack[-1] in d:
stack.pop()
stack.pop()
return len(stack) == 0
练习 1：LeetCode 第 150 题： 逆波兰表达式求值
传送门：150. 逆波兰表达式求值。
根据逆波兰表示法，求表达式的值。
有效的运算符包括
+,-,*,/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: ((2 + 1) * 3) = 9示例 2：
输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: (4 + (13 / 5)) = 6示例 3：
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 输出: 22 解释: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Java 代码：
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String token = tokens[i];
String pattern = "-?[0-9]+|[\\+\\-\\*/]";
if (!token.matches(pattern)) {
throw new RuntimeException("非法的表达式");
}
if (token.matches("-?[0-9]+")) {
int num = Integer.valueOf(token);
System.out.println(num);
stack.push(num);
}
if (token.matches("[\\+\\-\\*/]")) {
System.out.println("加减乘除" + token);
if (stack.size() >= 2) {
int num1 = stack.pop();
int num2 = stack.pop();
int result = 0;
switch (token){
case "+":
result = num2 +num1;
break;
case "-":
result = num2 -num1;
break;
case "*":
result = num2 *num1;
break;
case "/":
result = num2 /num1;
break;
}
stack.push(result);
}
}
}
return stack.pop();
}
public static void main(String[] args) {
String[] tokens = new String[]{"3", "-4", "+"};
Solution solution = new Solution();
int result = solution.evalRPN(tokens);
System.out.println(result);
}
}
是有问题的：Time Limit Exceeded 。然后我把上面的两个 System.out.println() 语句删除就 A 过了，好神奇，所以做题还是要规范啊。
练习2：LeetCode 第 71 题：简化路径
传送门：71. 简化路径。
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（
.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠
/开头，并且两个目录名之间必须只有一个斜杠/。最后一个目录名（如果存在）不能以/结尾。此外，规范路径必须是表示绝对路径的最短字符串。示例 1：
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。示例 2：
输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。示例 3：
输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。示例 4：
输入："/a/./b/../../c/" 输出："/c"示例 5：
输入："/a/../../b/../c//.//" 输出："/c"示例 6：
输入："/a//b////c/d//././/.." 输出："/a/b/c"
参考了如下的文章：http://blog.csdn.net/u012249528/article/details/46705867
Java 代码实现：
public class Solution {
public String simplifyPath(String path) {
String result = "";
String[] pathList = path.split("/");
if (pathList.length == 0) {
return "/";
}
Stack<String> stack = new Stack<>();
for (String p : pathList) {
if ("".equals(p) || ".".equals(p)) {
continue;
}
if ("..".equals(p)) {
if (!stack.isEmpty()) {
stack.pop();
}
} else { // 是正常的路径字符串的时候，入栈
stack.push(p);
}
}
// 现在考虑输出字符串
while (!stack.isEmpty()) {
result = "/" + stack.pop() + result;
}
if ("".equals(result)) {
result = "/";
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
String path1 = "/home/";
String result1 = solution.simplifyPath(path1);
System.out.println(result1);
String path2 = "/a/./b/../../c/";
String result2 = solution.simplifyPath(path2);
System.out.println(result2);
String path3 = "/..";
String result3 = solution.simplifyPath(path3);
System.out.println(result3);
String path4 = "/..";
String result4 = solution.simplifyPath(path4);
System.out.println(result4);
String path5 = "/abc/def/.";
String result5 = solution.simplifyPath(path5);
System.out.println(result5);
}
}
（本节完）
网友评论