Fork me on GitHub

LeetCode 栈类算法精析

前言

栈虽然是简单的数据结构,但是使用栈的数据结构所解决的算法问题不一定简单,今天主要介绍 LeetCode 中与栈的数据结构有关的算法问题。栈与递归的关系密切,我还会使用栈模拟递归解决一些算法的问题。

栈的基本应用

20. 有效的括号(前往该题

题目描述
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解题思路

我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回 False,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回 False 。栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素。

代码实现

1
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
30
31
32
33
34
35
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
n = len(s)
if n == 0:
return True
stack = []
for item in s:
if item in {'(', '{', '['}:
stack.append(item)
else:
if len(stack) == 0:
return False
lstr = stack.pop()
match = ''
if lstr == '(':
match = ')'
elif lstr == '{':
match = '}'
elif lstr == '[':
match = ']'
if match != item:
return False
if len(stack):
return False
return True

150. 逆波兰表达式求值(前往该题

题目描述

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
    示例 1:
    1
    2
    3
    输入: ["2", "1", "+", "3", "*"]
    输出: 9
    解释: ((2 + 1) * 3) = 9

示例 2:

1
2
3
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3:

1
2
3
4
5
6
7
8
9
10
输入: ["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

解题思路

用栈来实现,遍历当前字符串,如果当前字符串可以转换为数组类型,则当前元素转换为数值,将其入栈,如果是运算符,则取出栈中两个元素(如果此时栈中小于两个元素直接直接返回False)。并计算当前两个元素的值。然后结果再次入栈。

代码实现

1
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
30
31
32
33
34
35
36
37
38
class Solution:
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = list()
for item in tokens:
if self.isInt(item):
stack.append(item)
elif item in {'+', '-', '*', '/'}:
if len(stack) < 2:
return False
item2 = stack.pop()
item1 = stack.pop()
ret = self.calculate(int(item1), int(item2), item)
stack.append(ret)
return int(stack.pop())
def isInt(self, num):
try:
num = int(str(num))
return isinstance(num, int)
except:
return False
def calculate(self, num1, num2, operator):
if (operator == '+'):
return num1 + num2
elif operator == '-':
return num1 - num2
elif operator == '/':
return num1 / num2
elif operator == '*':
return num1 * num2

71. 简化路径(前往该题

题目描述

给定一个文档 (Unix-style) 的完全路径,请进行路径简化。

例如,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”

边界情况:

  • 你是否考虑了 路径 = “/../“ 的情况?
    在这种情况下,你需返回 “/“ 。
  • 此外,路径中也可能包含多个斜杠 ‘/‘ ,如 “/home//foo/“ 。
    在这种情况下,你可忽略多余的斜杠,返回 “/home/foo” 。

解题思路

思路很简单,我们首先使用 path.split(‘/‘) 将字符串切开,然后判断 path.split(‘/‘) 中每个元素。如果等于 ‘.’,我们继续判断下一个,如果等于’..’,弹出一个元素(此时需要栈不为空),否则我们将这个元素添加到 stack 中。最后将栈 stack 中的元素用 ‘/‘ 连接即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
if len(path) == 0:
return path
stack = list()
path = [p for p in path.split('/') if p]
for f in path:
if f == '.':
continue
elif f== '..':
if stack:
stack.pop()
else:
stack.append(f)
return '/' + '/'.join(stack)

栈和递归的紧密关系

利用栈这种数据机构我们可以将递归算法转化为非递归算法。

144. 二叉树的前序遍历(前往该题

题目描述

给定一个二叉树,返回它的 前序 遍历。

示例:

1
2
3
4
5
6
7
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

递归解题思路

首先访问,根节点,然后递归的遍历左子树和右子树,采用递归的代码很简洁。

递归代码代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = list()
if root:
ret.append(root.val)
ret1 = self.preorderTraversal(root.left)
ret2 = self.preorderTraversal(root.right)
ret += ret1 + ret2
return ret

非递归解题思路

可以使用栈模拟系统栈,我们先推入右孩子,在再推入左孩子,最后推入要打印的节点,由于栈的后进先出就完成了先序遍历。需要一个类型来表示此时应该是直接打印还是继续存入,所以我们新建了一个结构体(一个类)来表示存入的节点应该打印( print )还是继续往下走 ( go )

非递归代码实现

1
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
30
31
32
33
34
35
36
37
38
39
40
41
42
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Command:
def __init__(self, s, node):
self.s = s
self.node = node
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = list()
if root == None:
return res
stack = list()
stack.append(Command("go", root))
while stack:
command = stack.pop()
if command.s == "print":
res.append(command.node.val)
else:
# stack.push(Command("print", command.node));后序遍历
if command.node and command.node.right:
stack.append(Command("go", command.node.right))
# stack.append(Command("print", command.node)); 中序遍历
if command.node and command.node.left:
stack.append(Command("go", command.node.left)) # 先序遍历
stack.append(Command("print", command.node))
return res

相似问题

对于二叉树的中序遍历和后序遍历,只需要改变打印值的位置,相应的非递归算法在上面注释的代码中给出了(值需要改变stack.append(Command(“print”, command.node)) 这行代码的位置即可),递归代码和非递归代码都可以直接在 LeetCode 中直接 AC, 我们直接给出代码。

94. 二叉树的中序遍历(前往该题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = list()
if root:
ret1 = self.inorderTraversal(root.left)
ret += ret1
ret.append(root.val)
ret2 = self.inorderTraversal(root.right)
ret += ret2
return ret

145. 二叉树的后序遍历(前往该题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = list()
if root:
ret1 = self.postorderTraversal(root.left)
ret += ret1
ret2 = self.postorderTraversal(root.right)
ret += ret2
ret.append(root.val)
return ret

总结

我们知道在准备面试的时候,刷算法题是一种捷径,特别是刷 LeetCode,但是不能一味的刷题,我们需要总结和思考,对于一些相似的题目我们应该多想想他们的思想,其实很多题的解题思路都是相近的。

-------------本文结束 感谢您的阅读-------------
  • 本文标题: LeetCode 栈类算法精析
  • 本文作者: 吴军旗
  • 本文链接: http://fanqieto.top/2018/09/04/LeetCode-栈类算法精析/
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请保留原文链接及作者!
    • 欢迎搜索及关注:番茄技术小栈,所有文章都将同步在公众号上!
坚持原创技术分享,您的支持将鼓励我继续创作!