【每日算法Day 46】栈和队列1
昨晚的笔试题中就遇到了一道使用栈来解决的问题，今天来回顾一些使用栈来单纯地处理字符串或是数据的题目。
# LeetCode 155. 最小栈 (opens new window)
# 题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
pop、top 和 getMin 操作总是在 非空栈 上调用。
# 示例
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 解题思路
在使用一个通常的栈结构的同时，利用一个辅助栈，其栈顶存储当前栈的最小元素。
class MinStack {
Deque<Integer> mainStack;
Deque<Integer> helperStack;
public MinStack() {
mainStack = new ArrayDeque<>();
helperStack = new ArrayDeque<>();
}
public void push(int x) {
mainStack.push(x);
if (helperStack.size()==0||x<=helperStack.peek())
helperStack.push(x);
}
public void pop() {
int x= mainStack.pop();
if (helperStack.size()!=0&&x==helperStack.peek())
helperStack.pop();
}
public int top() {
return mainStack.peek();
}
public int getMin() {
return helperStack.peek();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# LeetCode 150. 逆波兰表达式求值 (opens new window)
# 题目描述
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
# 示例
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
2
3
# 解题思路
后缀表达式适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中，一个完整的后缀表达式运算完之后栈顶元素就是最终的解。
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {
stack.push(Integer.parseInt(token));
} else {
int operator2 = stack.pop(), operator1 = stack.pop();
int ans=0;
switch (token) {
case "+":
ans = operator1 + operator2;
break;
case "-":
ans = operator1 - operator2;
break;
case "*":
ans = operator1 * operator2;
break;
case "/":
ans = operator1 / operator2;
break;
}
stack.push(ans);
}
}
return stack.peek();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
如果不使用JCF而是直接使用纯数组来模拟栈会更快一些：
class Solution {
public static int evalRPN(String[] tokens) {
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
switch (s) {
case "+":
numStack[index - 2] += numStack[--index];
break;
case "-":
numStack[index - 2] -= numStack[--index];
break;
case "*":
numStack[index - 2] *= numStack[--index];
break;
case "/":
numStack[index - 2] /= numStack[--index];
break;
default:
numStack[index++] = Integer.parseInt(s);
break;
}
}
return numStack[0];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# LeetCode 71. 简化路径 (opens new window)
# 题目描述
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
# 示例
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
2
3
4
5
6
7
# 解题思路
首先根据/分割字符串，得到文件夹或者.和..，由于连续的斜线的存在还可能出现空串。对于空串和.处理时直接跳过就可以了，对于一般代表文件夹的字符串我们将其入栈，对于..我们将栈顶的文件夹出栈。最后将栈中的内容按照从栈底到栈顶的顺序（在Deque表示的栈中，栈顶为first，栈底为last）连同/拼接到StringBuilder中即可。
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
String[] dirs=path.split("/");
for (String dir : dirs) {
if (dir.length() != 0&&!dir.equals(".")) {
if (dir.equals("..")) {
stack.poll();
} else {
stack.push(dir);
}
}
}
StringBuilder sb=new StringBuilder("/");
if (!stack.isEmpty()) {
while (stack.size()>1) {
sb.append(stack.pollLast()).append("/");
}
sb.append(stack.pollLast());
}
return sb.toString();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21