刷穿剑指offer-Day17-栈I 栈的使用与基础题型
栈的介绍
栈(stack) 本身是一种简单、常用的数据结构，它常常用来和队列进行比较。
- 队列： 先入先出
- 栈： 后入先出
栈的所有操作都发生在栈顶，其实就三个操作，入栈(压栈)、出栈(弹栈)、获取栈顶元素。
Python & Java 中的栈
Java中存在Stack的数据结构，但Python是没有栈的，它们的实现与操作方式如下：
| 操作 | Python | Java | 说明 |
|---|---|---|---|
| 初始化 | Stack<Integer> stack = new Stack<>(); | stack = [] | |
| 入栈 | stack.push(1); | stack.append(1) | |
| 出栈 | stack.pop(); | stack.pop() | 为空时报错 |
| 获取栈顶元素 | stack.peek(); | stack[-1] | 为空时报错 |
栈的操作就是这几个，是不是很简单，要不直接下一章？too young，too simple！
栈的操作是简单的，但是栈在算法中的应用确实变化多端....有些题目打眼一看就是栈操作，比如 括号匹配。但更多的题目并不是能直接看出来通过栈去解决的。比如单调栈等类型的题目，真的是新手劝退神器....
但饭要一口一口吃，让我们先来看一道简单的括号匹配问题，熟悉下栈的操作吧。
1021.删除最外层的括号
难度：简单
题目
有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
提示：
- 1 <= s.length <= 10 ^ 5
- s[i] 为 '(' 或 ')'
- s 是一个有效括号字符串
示例
示例 1：
输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：
输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
输入：s = "()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
分析
这道题本身并不麻烦，主要是理解这句原语的含义：
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语
其实就是每获取一组左右括号相等的搭配后，将左右括号各删除一个，并保存即可。
由于这道题目提供的用例都是满足括号匹配关系的内容，使得这道题的难度就更低了。
- 我们创建一个字符串用于接收每次获取的原语进行拼接
- 然后创建一个栈，开始循环s，进行栈的入栈操作，每次入栈的是s的下标
- 左括号直接入栈，右括号时弹出栈顶，并判断栈是否为空，为空则代表找到一对匹配内容
- 此时获取栈顶index以及当前循环的下标i，ret += s[left+1:i]（删除最外层的左右括号）即可。
解题
Python:
class Solution:
def removeOuterParentheses(self, s):
ret = ""
stack = []
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
left = stack.pop()
if not stack:
ret += s[left + 1:i]
return ret
Java:
class Solution {
public String removeOuterParentheses(String s) {
Stack<Integer> stack = new Stack<>();
StringBuilder ret = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') stack.push(i);
else {
int index = stack.pop();
if (stack.empty()) {
ret.append(s.substring(index + 1, i));
}
}
}
return ret.toString();
}
}
看过了上面这道简单的栈题目，下来就该完成书中相关的题目了。
剑指OfferII036.后缀表达式
https://leetcode-cn.com/problems/8Zf90G/solution/shua-chuan-jian-zhi-offer-day10-zi-fu-ch-c9f1/
难度：中等
题目
根据 逆波兰表示法，求表达式的值。
有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
提示：
- 1 <= tokens.length <= 10 ^ 4
- tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
示例
示例1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例3：
输入：tokens = ["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
分析
- 根据题目所知，输入的逆波兰表达式都是有效的，所以无需考虑特殊的场景。
- 既然是一道栈的题目，肯定要先创建一个stack，然后依次将元素入栈，但什么时候出栈呢？
- 后缀表达式是指算符写在后面，即当我们遇到操作符时，需要将操作符紧邻的前两项拿出来进行计算
- 在第3步计算完成后，还需要将结果重新加入栈中
- 最终将计算结果返回即可
解题
Python:
class Solution:
def evalRPN(self, tokens):
stack = []
calc = {'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: int(x / y), }
for i in tokens:
if i in calc:
num2, num1 = stack.pop(), stack.pop()
stack.append(calc[i](num1, num2))
else:
stack.append(int(i))
return stack[0]
Java:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String c : tokens) {
switch (c) {
case "+":
case "-":
case "*":
case "/":
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(calc(num1, num2, c));
break;
default:
stack.push(Integer.parseInt(c));
}
}
return stack.pop();
}
private int calc(int a, int b, String op) {
switch (op) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
default:
return a / b;
}
}
}
虽说是一道中等题目，但仅仅是多了几种判断而已，主要能第一时间想到栈的套路，那离AC也就不差多少了....
下面再来一道同等难度的题目，考验下大家在场景分析中对栈的理解！
剑指OfferII037.小行星碰撞
https://leetcode-cn.com/problems/XagZNi/solution/shua-chuan-jian-zhi-offer-day17-zhan-i-0-5yho/
难度：中等
题目
给定一个整数数组 asteroids，表示在同一行的小行星。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
提示：
- 2 <= asteroids.length <= 10 ^ 4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
示例
示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
示例 4：
输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
分析
这道栈的题目难点应该主要是在分析场景上了。 我们需要明确什么时候无脑入栈，什么时候需要判断，理解这两点就可以轻松解题了。 首先，循环每一个元素时，在什么情况下无脑入栈呢？
- 栈为空
- 栈顶元素为负数(下一个为负数则一起向左，下一个为正数则分向两边)
- 当前元素为正数（栈顶为正一起向左，栈顶为负分向两边）
下来，我们需要看碰撞的场景又细分为什么情况：
- 栈顶元素大于abs(当前元素)，当前元素被撞毁
- 栈顶元素等于abs(当前元素)，栈顶弹出和当前元素抵消
- 栈顶元素小于abs(当前元素)，栈顶弹出，并与新栈顶完成上述判断
最终返回栈即可。
解题
Python:
class Solution:
def asteroidCollision(self, asteroids):
s, p = [], 0
while p < len(asteroids):
if not s or s[-1] < 0 or asteroids[p] > 0:
s.append(asteroids[p])
elif s[-1] <= -asteroids[p]:
if s.pop() < -asteroids[p]:
continue
p += 1
return s
Java:
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> s = new Stack<>();
int p = 0;
while (p < asteroids.length) {
if (s.empty() || s.peek() < 0 || asteroids[p] > 0) {
s.push(asteroids[p]);
} else if (s.peek() <= -asteroids[p]) {
if (s.pop() < -asteroids[p]) {
continue;
}
}
p++;
}
int[] ret = new int[s.size()];
for (int i = ret.length - 1; i >= 0; i--) {
ret[i] = s.pop();
}
return ret;
}
}
那么，今天关于栈的基础操作就先学习到这里，关于栈的特殊场景单调栈，将在明天开始学习。
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论