# 剑指offer【30~39】

#### Python 实现：

##### 30. 包含 min 函数的栈

``````# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.minstack = []

def push(self, node):
# write code here
self.stack.append(node)
if not self.minstack or node < self.minstack[-1]:
self.minstack.append(node)
else:
self.minstack.append(self.minstack[-1])

def pop(self):
# write code here
self.stack.pop()
self.minstack.pop()

def top(self):
# write code here
return self.stack[-1]

def min(self):
# write code here
return self.minstack[-1]``````
##### 31. 栈的压入、弹出序列

``````# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
stack = []
j = 0
for i in range(len(pushV)):
if pushV[i] != popV[j]:
stack.append(pushV[i])
else:
j += 1
while stack:
if stack[-1] != popV[j]:
return False
stack.pop()
j += 1
return True``````
##### 32.1 从上往下打印二叉树

``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root:
return []
q = collections.deque()
ans = []
q.append(root)
while q:
return ans``````
##### 32.2 把二叉树打印成多行

``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
ans = []
if not pRoot:
return []
q = collections.deque()
ans = []
q.append(pRoot)
while q:
lens = len(q)  # 每一层有 lens 个数
if lens > 0:   # 该层有数
ans.append([])
while lens > 0:
lens -= 1
return ans``````
##### 32.3 按之字形顺序打印二叉树

``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
def Print(self, pRoot):
# write code here
ans = []
if not pRoot:
return []
q = collections.deque()
ans = []
q.append(pRoot)
flag = 1
while q:
lens = len(q)  # 每一层有 lens 个数
if lens > 0:   # 该层有数
ans.append([])
while lens > 0:
lens -= 1
if flag == 0:  # flag = 0 时翻转该层
ans[-1].reverse()
flag = not flag
return ans``````
##### 33. 二叉搜索树的后序遍历序列
• 一个二叉搜索树BST满足： max(左子树) < 根节点 < min(右子树)；
• 对于空数组，应该返回 False。
• 题目给出的是一个后序遍历，那么序列的最后一个元素就应该是根节点；
• 从BST的定义出发，遍历整个序列，找到第一个大于根节点的元素k，k以前的元素属于左子树，从k开始到根节点之前的元素属于右子树；
• 判断右子树是否都比根节点要大，如果不是，直接返回 False。
• 如果遍历整个序列之后得到的左右子树都满足BST的定义，则递归判断左子树和右子树是否满足BST定义。
``````# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
lens = len(sequence)
# 空数组返回 False
if lens == 0:
return False
root = sequence[-1]
# 找到大于 root 的第一个元素
ind = 0
while ind < lens - 1:
if sequence[ind] > root:
break
ind += 1
# 先判断一下右子树是不是都比根大（左子树在上一个循环已经判断过了）
i = ind + 1
while i < lens - 1:
if sequence[i] < root:
return False
i += 1
# 递归判断左右子树是否都满足 BST
left = right = True  # 这里的初始值都要设置为 True，不然永远不可能为 True
if ind > 0:  # 防止为空数组
left = self.VerifySquenceOfBST(sequence[:ind])
if ind < lens - 1:  # 防止为空数组
right = self.VerifySquenceOfBST(sequence[ind:-1])
return left and right``````
##### 34.二叉树中和为某一值的路径
• 树的深搜，使用 dfs 回溯法，当到达根且目标值为 0 时找到一条路径。
• 在递归左右子树的过程中，如果发现提前到达根节点或者目标值为负，要进行剪枝。
``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
def dfs(root, expectNumber, path):
if not root and expectNumber == 0:  # 找到一条路径
return
if not root or expectNumber < 0:  # 减枝
return
dfs(root.left, expectNumber - root.val, path + [root.val])
dfs(root.right, expectNumber - root.val, path + [root.val])

ans = set()  # 使用 set 不是 list 防止同一路径输出两次
if not root:  # 防止 root 为空且 expectNumber 为 0 时输出 [[]] 而不是 []
return list(ans)
dfs(root, expectNumber, [])
return list(ans)``````
##### 35. 复杂链表的复制

``````# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
# 返回 RandomListNode
# write code here
return None
cur = pHead  # 1 复制 next
while cur:
co = RandomListNode(cur.label)
co.next = cur.next
cur.next = co
cur = cur.next.next
cur = pHead  # 2 复制 random
while cur:
if cur.random:  # 一个节点的 random 域可能为空
cur.next.random = cur.random.next
cur = cur.next.next
while cur.next:
nex_ = cur.next
cur.next = nex_.next
cur = nex_
##### 36. 二叉搜索树与双向链表

（1）遍历左子树，找到第一个结点，并设置为链表头部； （2）当前结点的左指针连接上一个结点，pre 的右指针连接当前结点，并修改 pre 指向当前结点； （3）遍历右子树。

``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
def inorder(root):
if not root:
return
inorder(root.left) # 中序遍历：遍历左子树
root.left = self.pre  # 连接左指针
if self.pre:  # 连接右指针
self.pre.right = root
self.pre = root  # 修改上一个指针
inorder(root.right)  # 中序遍历：遍历右子树

self.pre = self.head = None  # 变量要加 self，如果是 list 则可以不用
inorder(pRootOfTree)
##### 37. 序列化二叉树

``````# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def Serialize(self, root):
# write code here
if not root:
return "#"
return str(root.val) + "!" + self.Serialize(root.left) + "!" + self.Serialize(root.right)

def Deserialize(self, s):
# write code here
def preorder():
if not li:
return None
val = li.pop(0)  # 每次都从 list 中删除一个结点
if val == "#":
return None
root = ListNode(int(val))
root.left = preorder()
root.right = preorder()
return root

li = s.split("!")
return preorder()``````
##### 38. 字符串的排列

``````# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
def dfs(k, path):
if k == lens and path not in ans:
ans.append(path)
return
for i in range(lens):
if flag[i] == 0:
flag[i] = 1
dfs(k + 1, path + ss[i])
flag[i] = 0

lens = len(ss)
if lens == 0:
return []
flag = [0] * lens
ans = []
dfs(0, "")
return ans``````
##### 39. 数组中出现次数超过一半的数字

``````# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers:
return 0
pre, cnt = numbers[0], 1   # pre 记录出现次数多的那个数字
for i in range(1, len(numbers)):
if cnt == 0:
pre = numbers[i]
cnt += 1
elif pre == numbers[i]:
cnt += 1
elif pre != numbers[i]:
cnt -= 1
# pre 是否超过了一半
return pre if numbers.count(pre) > len(numbers) // 2 else 0``````

0 条评论

• ### 剑指offer | 面试题51：不用加减乘除做加法

参考链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof...

• ### 剑指offer | 面试题31：数组中出现次数超过一半的数字

推论一： 若记众数的票数为+1，非众数的票数为-1,则一定有所有数字的票数和> 0。推论二： 若数组的前a个数字的票数和=0，则数组剩余(n-a)个数字的票数和...

• ### 剑指offer | 面试题50：求1+2+…+n

思考： 除了 if和 switch 等判断语句外，本题需要实现 “当 n = 1 时终止递归” 的需求，可通过短路效应实现。

• ### 剑指offer | 面试题49：圆圈中最后剩下的数字

参考文章：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-z...

• ### 剑指offer | 面试题44：和为s的连续整数序列

设连续正整数序列的左边界 ii 和右边界 jj ，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内

• ### 剑指offer | 面试题48：扑克牌中的顺子

参考链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/m...

• ### 剑指offer | 面试题46：左旋转字符串

获取字符串 s[ n : ] 切片和 s[ : n ]切片，使用 "+" 运算符拼接并返回即可。

• ### 剑指offer | 面试题43：和为s的两个数字

参考链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/m...

• ### 快速拿下面试算法

在面试前一周，我刷了很多道算法，分类刷，有些是做过的，因为我是面试C++相关岗位，除了leetcode与剑指offer相关的算法，还需要手撕一些智能指针呀，单例...

• ### 剑指offer | 面试题45：翻转单词顺序

参考链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mia...

• ### 剑指offer | 面试题42：平衡二叉树

思路：平衡二叉树的条件：左子树是平衡二叉树，右子树是平衡二叉树，左右子树高度不超过 1。

• ### 剑指offer | 面试题40：数组中数字出现的次数

异或运算有个重要的性质，两个相同数字异或为 0。因此，若将 nums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 x ，即：

• ### 剑指offer(16-30题) 精解

比如两个链表你可以用一个list1作为主链表返回。返回另一个list2进行遍历比较插入到主链表适当位置中。有兴趣可以试一试。 当然你还可以直接建立一个新链表头节...

• ### LeetCode 开卷考试，不开心么

马上快 3 月份，不知道小伙伴们有没有做好跳槽的打算，而不管想不想跳槽，很多时候都会有猎头来联系，有些猎头甚至会透露一些岗位的面试内容。

• ### 剑指offer | 面试题35：把数组排成最小的数

思路：此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y,则规 定排序判断规则为:

• ### 剑指offer 30:包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。