中等难度也太难了，做吐了，每一道题的心路历程:
- （开始前）这是中等难度，估计很难
- （看完题目）似乎还行啊？我可以
- （试错）我真的可以吗？有点麻烦了
- （再坚持一会）烦躁！怎么还不对劲
- （看完题解）好家伙🐂原来要这样想可以这么简单
剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
class MaxQueue:
def __init__(self):
self.queue = []
self.stack = [] #用一个单调栈来保存最大值
def max_value(self) -> int:
if not self.stack:
return -1
return self.stack[0]
def push_back(self, value: int) -> None:
self.queue.append(value)
while self.stack and value > self.stack[-1]:
self.stack.pop() # 把stack里所有小于当前值的都pop掉
self.stack.append(value)
def pop_front(self) -> int:
if not self.queue:
return -1
if self.queue[0] == self.stack[0]:
self.stack.pop(0)
return self.queue.pop(0)
# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
剑指 Offer 33. 二叉搜索树的后序遍历序列
后续遍历的理解关键点（for me）：先找到左下角的节点，然后按照左——右——根节点的顺序来，总之注意，当前节点append进去之后，先看看他的父节点的右子节点有没有遍历完，没有的话先去遍历这个右子节点/右子树，遍历完之后在去父节点的位置。
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
——递归思路：
给出遍历序列 [1, 4, 3, 17, 12, 9, 5]，
-
最后一个数字是跟节点
-
第一个比节点大的数index，0,index为左子数，index,len-1为右子树，
-
递归看是否满足规则
在判断每次的左子树个数加上右子树的个数是否为树的长度
class Solution:
def verifyPostorder(self, postorder):
while len(postorder) > 2:
node = postorder.pop()
length = 0
for i in range(len(postorder)):
if postorder[i] < node:
length += 1
else: break
for j in range(i, len(postorder)):
if postorder[j] > node:
length += 1
else: break
print(length, postorder)
if length != len(postorder):
return False
return True
# 测试
s2 = Solution()
arr = [1,4,3,7,10,13,12,19,18,15,9]
print(s2.verifyPostorder(postorder = arr))
arr = [1, 6, 16, 13, 15, 19, 11, 10]
print(s2.verifyPostorder(postorder = arr))
10 [1, 4, 3, 7, 10, 13, 12, 19, 18, 15]
9 [1, 4, 3, 7, 10, 13, 12, 19, 18]
8 [1, 4, 3, 7, 10, 13, 12, 19]
7 [1, 4, 3, 7, 10, 13, 12]
6 [1, 4, 3, 7, 10, 13]
5 [1, 4, 3, 7, 10]
4 [1, 4, 3, 7]
3 [1, 4, 3]
2 [1, 4]
True
7 [1, 6, 16, 13, 15, 19, 11]
6 [1, 6, 16, 13, 15, 19]
5 [1, 6, 16, 13, 15]
3 [1, 6, 16, 13]
False
剑指 Offer 14. 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
e.g.
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
输出所有的可能
用字典记录算出过的值，加速，避免重复计算
d = dict()
d[2] = 1
def cuttingRope(n):
res = []
if n in d.keys():
return d[n]
for i in range(1, n//2 + 1):
tmpi = max(i * cuttingRope(n-i), i * (n-i))
res.append(tmpi)
d[n] = max(res)
return d[n]
print(cuttingRope(36))
print(d)
531441
{2: 1, 3: 2, 4: 4, 5: 6, 6: 9, 7: 12, 8: 18, 9: 27, 10: 36, 11: 54, 12: 81, 13: 108, 14: 162, 15: 243, 16: 324, 17: 486, 18: 729, 19: 972, 20: 1458, 21: 2187, 22: 2916, 23: 4374, 24: 6561, 25: 8748, 26: 13122, 27: 19683, 28: 26244, 29: 39366, 30: 59049, 31: 78732, 32: 118098, 33: 177147, 34: 236196, 35: 354294, 36: 531441}
剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
- 不断入栈，1 2 3 4，此时栈顶=popped[0]，pop()
- 辅助栈剩下1 2 3 5 栈顶=popped[1] pop
- 1 2 3 3 = popped[2] pop
- 最后popped遍历完，辅助栈为空-》return T
'''
stack = []
j = 0
for num in pushed:
stack.append(num)
while stack and stack[-1]==popped[0]:
stack.pop()
popped.pop(0)
print(not stack)
'''
def validateStackSequences(pushed, popped):
stack, i = [], 0
for num in pushed:
stack.append(num) # 入栈
while stack and stack[-1] == popped[i]: # 判断出栈
stack.pop()
i += 1
return not stack
# 测试
validateStackSequences(pushed = [1,2,3,4,5], popped = [4,3,5,1,2]),validateStackSequences(pushed = [1,0], popped = [1,0])
(False, True)
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
好家伙递归套递归，思路太清晰了🐂
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 定义测试用例1
t1 = TreeNode(5)
t2 = TreeNode(4)
t3 = TreeNode(8)
t4 = TreeNode(11)
t5 = TreeNode(13)
t6 = TreeNode(4)
t7 = TreeNode(7)
t8 = TreeNode(2)
t9 = TreeNode(5)
t10 = TreeNode(1)
t1.left = t2; t1.right = t3
t2.left = t4; t3.left = t5; t3.right = t6;
t4.left = t7; t4.right = t8; t6.left = t9; t6.right = t10
# 定义测试用例2
z1 = TreeNode(-2)
z2 = TreeNode(-3)
z1.right = z2
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A, B):
# 补充定义函数
def recur(A,B): # 递归判断是否是子结构：
# 结束条件——匹配完了/发现不一致的
if not B:
return True
if not A or (A.val != B.val):
return False
# 递归
return recur(A.left, B.left) and recur(A.right, B.right)
# 结束条件1：空树
if (not A) or (not B): # 约定空树不是任意一个树的子结构
return False
# 结束条件2：找到了子结构
if recur(A, B):
return True
# 否则递归
return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
s5 = Solution()
s5.isSubStructure(t1, t3), s5.isSubStructure(z1, z2),s5.isSubStructure(t2, t6)
(True, True, False)
剑指 Offer 34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
def pathSum(root, target):
res, path = [], []
def recur(root, target):
if not root: return
path.append(root.val)
print(path, target, res)
if root.val == target: # 找到这样的路径就append进去
res.append(list(path))
'''
if (not root.right) and (not root.left): # 如果题目要求必须从根节点-叶节点的路径，加入这一个判断
res.append(list(path))
'''
recur(root.left, target - root.val)
recur(root.right, target - root.val)
path.pop() # 这里是关键点
return
recur(root, target)
return res
pathSum(t1, 22)
print("\n")
pathSum(z1, -5)
[5] 22 []
[5, 4] 17 []
[5, 4, 11] 13 []
[5, 4, 11, 7] 2 []
[5, 4, 11, 2] 2 []
[5, 8] 17 [[5, 4, 11, 2]]
[5, 8, 13] 9 [[5, 4, 11, 2]]
[5, 8, 4] 9 [[5, 4, 11, 2]]
[5, 8, 4, 5] 5 [[5, 4, 11, 2]]
[5, 8, 4, 1] 5 [[5, 4, 11, 2], [5, 8, 4, 5]]
[-2] -5 []
[-2, -3] -3 []
[[-2, -3]]
剑指 Offer 47. 礼物的最大价值
在一个 mXn 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
基础版本
def maxValue(grid):
if (not len(grid)) or (grid and not len(grid[0])):
return False
m = len(grid)
n = len(grid[0])
def gifts(i, j):
# print(i,j)
if i >= m or j>=n :
return 0
if i == m-1 and j == n-1:
return grid[i][j]
else:
return grid[i][j] + max(gifts(i, j+1), gifts(i+1, j))
return gifts(0,0)
grid = [
[1,3,1],
[1,5,1],
[4,2,1]
]
maxValue(grid)
12
对于复杂的情况，上面的版本就超时了，如何解决？
改进版本
考虑用字典改进为记忆递归（套路方法嘿嘿），确实加速了，但是无论时间/空间复杂度表现都不太行
grid = [[7,1,3,5,8,9,9,2,1,9,0,8,3,1],[9,5,9,4,0,4,8,8,9,5,7,3,6,6],[8,2,9,1,3,1,9,7,2,5,3,1,2,4],[6,7,9,8,4,8,3,0,4,0,9,6,6,0],[7,1,3,1,8,8,3,1,2,1,5,0,2,1],[9,5,4,3,5,6,1,3,6,4,9,7,0,8],[1,4,2,5,8,7,7,0,0,7,1,2,1,2],[3,9,7,9,5,8,9,5,6,9,8,8,0,1],[1,5,2,2,2,5,6,3,9,3,1,7,9,6]]
m = len(grid)
n = len(grid[0])
d = dict()
def gifts2(i, j):
if i >= m or j>=n :
return 0
if i == m-1 and j == n-1:
d[(i, j)] = grid[i][j]
return d[(i, j)]
else:
t1 = d[i, j+1] if (i, j+1) in d else gifts2(i, j+1)
t2 = d[i+1, j] if (i+1, j) in d else gifts2(i+1, j)
d[(i, j)] = grid[i][j] + max(t1, t2)
return d[(i, j)]
print(gifts2(0, 0))
print(d)
164
{(8, 13): 6, (7, 13): 7, (6, 13): 9, (5, 13): 17, (4, 13): 18, (3, 13): 18, (2, 13): 22, (1, 13): 28, (0, 13): 29, (8, 12): 15, (7, 12): 15, (6, 12): 16, (5, 12): 17, (4, 12): 20, (3, 12): 26, (2, 12): 28, (1, 12): 34, (0, 12): 37, (8, 11): 22, (7, 11): 30, (6, 11): 32, (5, 11): 39, (4, 11): 39, (3, 11): 45, (2, 11): 46, (1, 11): 49, (0, 11): 57, (8, 10): 23, (7, 10): 38, (6, 10): 39, (5, 10): 48, (4, 10): 53, (3, 10): 62, (2, 10): 65, (1, 10): 72, (0, 10): 72, (8, 9): 26, (7, 9): 47, (6, 9): 54, (5, 9): 58, (4, 9): 59, (3, 9): 62, (2, 9): 70, (1, 9): 77, (0, 9): 86, (8, 8): 35, (7, 8): 53, (6, 8): 54, (5, 8): 64, (4, 8): 66, (3, 8): 70, (2, 8): 72, (1, 8): 86, (0, 8): 87, (8, 7): 38, (7, 7): 58, (6, 7): 58, (5, 7): 67, (4, 7): 68, (3, 7): 70, (2, 7): 79, (1, 7): 94, (0, 7): 96, (8, 6): 44, (7, 6): 67, (6, 6): 74, (5, 6): 75, (4, 6): 78, (3, 6): 81, (2, 6): 90, (1, 6): 102, (0, 6): 111, (8, 5): 49, (7, 5): 75, (6, 5): 82, (5, 5): 88, (4, 5): 96, (3, 5): 104, (2, 5): 105, (1, 5): 109, (0, 5): 120, (8, 4): 51, (7, 4): 80, (6, 4): 90, (5, 4): 95, (4, 4): 104, (3, 4): 108, (2, 4): 111, (1, 4): 111, (0, 4): 128, (8, 3): 53, (7, 3): 89, (6, 3): 95, (5, 3): 98, (4, 3): 105, (3, 3): 116, (2, 3): 117, (1, 3): 121, (0, 3): 133, (8, 2): 55, (7, 2): 96, (6, 2): 98, (5, 2): 102, (4, 2): 108, (3, 2): 125, (2, 2): 134, (1, 2): 143, (0, 2): 146, (8, 1): 60, (7, 1): 105, (6, 1): 109, (5, 1): 114, (4, 1): 115, (3, 1): 132, (2, 1): 136, (1, 1): 148, (0, 1): 149, (8, 0): 61, (7, 0): 108, (6, 0): 110, (5, 0): 123, (4, 0): 130, (3, 0): 138, (2, 0): 146, (1, 0): 157, (0, 0): 164}
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
- 用一个优先队列来维护，用双指针表示
- 每次在队列内循环——如果存在和当前相同的，就把左指针变为重复的下一位，保证队列内unique
- 保留最大长度的队列
strings = list("daddvdffd") # 最长的是vdf——3
i = 0
curmax = 0
for j in range(len(strings)):
for idx in range(i, j):
if strings[idx] == strings[j]:
i = idx + 1
break
print(strings[i:(j+1)]) # 保留的队列
curmax = j - i +1 if ( j-i +1 > curmax) else curmax
curmax
['d']
['d', 'a']
['a', 'd']
['d']
['d', 'v']
['v', 'd']
['v', 'd', 'f']
['f']
['f', 'd']
3
剑指 Offer 49. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数
动态规划
dp[i]=min(dp[a]∗2,dp[b]∗3,dp[c]∗5)
n = 10
dp = [None] * n
dp[0] = 1
a,b,c = 0, 0, 0
for i in range(1, n):
tmp = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)
dp[i] = tmp
if tmp == dp[a] * 2:
a += 1
if tmp == dp[b] * 3:
b += 1
if tmp == dp[c] * 5:
c +=1
print(tmp, dp)
print(dp)
2 [1, 2, None, None, None, None, None, None, None, None]
3 [1, 2, 3, None, None, None, None, None, None, None]
4 [1, 2, 3, 4, None, None, None, None, None, None]
5 [1, 2, 3, 4, 5, None, None, None, None, None]
6 [1, 2, 3, 4, 5, 6, None, None, None, None]
8 [1, 2, 3, 4, 5, 6, 8, None, None, None]
9 [1, 2, 3, 4, 5, 6, 8, 9, None, None]
10 [1, 2, 3, 4, 5, 6, 8, 9, 10, None]
12 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
剑指 Offer 60. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
# 单个
probs = ([1/6]*6)
# 两个骰子
d = dict()
for i in range(6):
for j in range(6):
if i+j+2 in d:
d[i+j+2] = d[i+j+2] + probs[i]*probs[j]
else:
d[i+j+2] = probs[i]*probs[j]
print(d)
# 如果是多个怎么办——换一种思路——递归
{2: 0.027777777777777776, 3: 0.05555555555555555, 4: 0.08333333333333333, 5: 0.1111111111111111, 6: 0.1388888888888889, 7: 0.16666666666666669, 8: 0.1388888888888889, 9: 0.1111111111111111, 10: 0.08333333333333333, 11: 0.05555555555555555, 12: 0.027777777777777776}
1.暴力解答
时间复杂度：O(6^n)
def dicesProbability(n):
def count(n, s):
if s < n or s > 6 * n:
return 0
if n == 1:
return 1
return sum([count(n - 1, s - i) for i in range(1, 7)])
res = []
for s in range(n, 6 * n +1 ):
res.append(count(n,s))
return [x/sum(res) for x in res]
# 测试
dicesProbability(3)
[0.004629629629629629,
0.013888888888888888,
0.027777777777777776,
0.046296296296296294,
0.06944444444444445,
0.09722222222222222,
0.11574074074074074,
0.125,
0.125,
0.11574074074074074,
0.09722222222222222,
0.06944444444444445,
0.046296296296296294,
0.027777777777777776,
0.013888888888888888,
0.004629629629629629]
动态规划方法
递推公式：probs(n,s) = sigma i从1到6求和{1/6 * probs(n-1, n-i)}
用一个二维数组去记录
n = 3
dp = [[0 for _ in range((6*n)+1)] for _ in range(n+1)]
for i in range(1,7):
dp[1][i] = 1.0/6
for i in range(2, n+1): # i表示从掷出1个筛子的情况，递推到掷出n个
for j in range(i, (6 * i) + 1):
for k in range(1, 7):
if j >= k+1:
dp[i][j] += (1/6) * dp[i-1][j-k]
dp[n][n:]
[0.004629629629629629,
0.013888888888888888,
0.027777777777777776,
0.046296296296296294,
0.06944444444444445,
0.09722222222222224,
0.11574074074074074,
0.125,
0.125,
0.11574074074074073,
0.09722222222222222,
0.06944444444444445,
0.046296296296296294,
0.027777777777777776,
0.013888888888888888,
0.004629629629629629]