剑指offer【30~39】
题目链接：
剑指offer 30-39
Python 实现：
30. 包含 min 函数的栈
除了存储数据的栈 stack，再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步，只不过其是一个递减栈。如 stack = [6,7,4,5,3,8]，则 minstack = [6,6,4,4,3,3]。这样，在 pop 的时候，同时 pop 两个栈，不会因为删除最小值而在 minstack 中找不到。
# -*- 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. 栈的压入、弹出序列
使用一个栈 stack 模拟压入操作；先遍历压入序列，将没有在弹出序列中遇到的数字存入 stack 中；然后再遍历弹出序列，判断是否和 stack 中序列相同。时间复杂度和空间复杂度均为 O(n)。
# -*- 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 True32.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:
addr = q.popleft()
ans.append(addr.val)
if addr.left:
q.append(addr.left)
if addr.right:
q.append(addr.right)
return ans32.2 把二叉树打印成多行
同 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],[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:
addr = q.popleft()
lens -= 1
ans[-1].append(addr.val)
if addr.left:
q.append(addr.left)
if addr.right:
q.append(addr.right)
return ans32.3 按之字形顺序打印二叉树
同 32.2，使用一个标记 flag，初始为 1，每过一层翻转 flag 的值。如果 flag = 0，说明某层要从右到左打印，则将该层的打印结果翻转存入结果中。
# -*- 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:
addr = q.popleft()
lens -= 1
ans[-1].append(addr.val)
if addr.left:
q.append(addr.left)
if addr.right:
q.append(addr.right)
if flag == 0: # flag = 0 时翻转该层
ans[-1].reverse()
flag = not flag
return ans33. 二叉搜索树的后序遍历序列
- 一个二叉搜索树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 right34.二叉树中和为某一值的路径
- 树的深搜，使用 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: # 找到一条路径
ans.add(tuple(path))
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. 复杂链表的复制
分三步： （1）遍历链表，复制 next 域； （2）遍历链表，复制 random 域（注意一个节点的 random 域可能为 None，因此在复制的过程中要判断是否为空）； （3）拆分两个链表（不能只拆分复制后的链表，会报错，两个都要拆出来）。
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
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
cur, pCloneHead = pHead, pHead.next # 3 拆分两链表
while cur.next:
nex_ = cur.next
cur.next = nex_.next
cur = nex_
return pCloneHead36. 二叉搜索树与双向链表
设置一个 pre 指向链表的前一个结点，初始值为 None。使用中序遍历，每次让当前结点左指针连接上一个结点 pre，pre 的右指针连接当前结点。具体做法：
（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) # 中序遍历：遍历左子树
if not self.head: # 链表头部
self.head = root
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)
return self.head37. 序列化二叉树
这里使用前序遍历对树序列化，然后对应的反序列化也要采取前序遍历才能恢复。在反序列化时，每次从列表中删除一个结点，遇到 "#" 要返回。之后按照前序遍历构造即可。
# -*- 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. 字符串的排列
回溯法，很坑，答案竟然要求返回的 list 的顺序要和参考答案的顺序一致，醉了...（本来一个 set 就搞定了，还需要增加点时间复杂度）
# -*- 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 ans39. 数组中出现次数超过一半的数字
这道题可以使用 LeetCode精讲：摩尔投票算法，使得时间复杂度为 O(n)，空间复杂度为 O(1)。
# -*- 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剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
文件存储
文件存储（Cloud File Storage，CFS）为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用，为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用，可实现对现有应用的无缝集成；按实际用量付费，为您节约成本，简化 IT 运维工作。
腾讯云开发者
