- 剑指 Offer 59 - I. 滑动窗口的最大值
- 剑指 Offer 61. 扑克牌中的顺子
- 剑指 Offer 62. 圆圈中最后剩下的数字
- 剑指 Offer 63. 股票的最大利润
- 剑指 Offer 68 - 二叉树的最近公共祖先
- 剑指 Offer 04. 二维数组中的查找
- 剑指 Offer 07. 重建二叉树
- 剑指 Offer 12. 矩阵中的路径
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
注意不用切片和max——每次取max无法降低重复操作
用一个队列维护最大值的index 最大长度为3，单调递减，队首为当前窗口的最大值
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
nums = [1, 3, -1, 6, -3, 3, 1, 2, 5, 3, 6, 7]
k = 3
queue, res = [], []
for i in range(len(nums)):
while queue and (nums[i] > nums[queue[-1]]):
queue.pop() # 如果nums[i]比之前的大，就把队列里小的pop掉
queue.append(i) # 加入queue
if i - queue[0] >= k: # 如果最大值不在窗口内了，则pop掉
queue.pop(0)
if i >= k-1:
res.append(nums[queue[0]]) # 队首是当前窗口的最大值
print(res)
[3, 6, 6, 6, 3, 3, 5, 5, 6, 7]
剑指 Offer 61. 扑克牌中的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王(0)可以看成任意数字。
技巧点：没有重复 & 最大值-最小值 <= 4，就是顺子
[2,0,0,0,0]
[0,0,0,0,0]
[1,2,5,0,0]
[1,2,2,3,0] 有重复
[2,3,4,0,7] 极值>4
所以首先进行一步检查重复，如果出现非0的重复直接 return False，然后再检查极差
def isStraight(nums):
d = dict()
for num in nums:
if num in d.keys() and num!=0:
return False
elif num!=0:
d[num] = 1
newnums = list(d.keys())
if len(newnums) > 1 and (max(newnums)-min(newnums) > 4):
return False
else:
return True
isStraight([10,4,5,0,0])
False
剑指 Offer 62. 圆圈中最后剩下的数字
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
- 基础版的可以理解为一个队列问题，每次把队首的移到队尾，如果移动了m次，pop就不再添加到队尾了
- 复杂情况下这样就超时了，结合数学知识理解:
- 每次pop掉的索引是(i + m - 1) % len(a)
- 递推公式 f(N,M)=(f(N−1,M)+M)%N
# 简单版——一个队列问题——超时
def lastRemaining(n, m):
queue = list(range(n))
while len(queue) > 1:
for j in range(m):
cur = queue.pop(0)
if j < m-1:
queue.append(cur)
print(queue)
return queue[0]
print(lastRemaining(5, 3))
# 结合数学逻辑，每次pop掉的索引是(i + m - 1) % len(a)——可以理解
def lastRemaining(n, m):
queue = list(range(n))
i = 0
while len(queue) > 1:
i = ( i + m - 1 ) % len(queue)
queue.pop(i)
return queue[0]
print(lastRemaining(5, 3))
print(lastRemaining(500, 300))
# 最佳解答——递推公式——其实使用了数学逻辑
def lastRemaining(n, m):
# 递推公式 f(N,M)=(f(N−1,M)+M)%N
# // f(n,m) = (f(n-1,m)+m) % n
# // 我们把数字看做人，报到 m 的人，直接干掉
# // n 代表的是当前人数，m 代表的是报数
# // 假设一共有 11 人,最后那个胜利的人下标是 6
# // 在下一轮 10 人的时候，胜利者的编号往前移动三格(假设m=3)
# // 那假设我们有 10 人，胜利者下标为3，到 11 人的时候胜利者下标是 6
# // 所以公式为 fn = (fn-1 + m) % n
# // 如果只有一个人，那么下标为0
last = 0
# 往回推 推出最出最开始人数是n的时候last的index
for i in range(2, n+1):
last = (last+m)%i
return last
print(lastRemaining(500, 300))
[3, 4, 0, 1]
[1, 3, 4]
[1, 3]
[3]
3
3
335
335
剑指 Offer 63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
def maxprofit(prices):
profit = 0
minprice = prices[0]
if len(prices)<2:
return profit
for i in range(1, len(prices)):
if prices[i] < minprice:
minprice = prices[i]
elif prices[i] > minprice + profit:
profit = prices[i] - minprice
return profit
maxprofit([7,1,5,3,6,4]),maxprofit([7,6,4,3,1])
(5, 0)
剑指 Offer 68 - 二叉树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 定义测试用例
t1 = TreeNode(5)
t2 = TreeNode(3)
t3 = TreeNode(9)
t1.left = t2; t1.right = t3
t4 = TreeNode(1)
t5 = TreeNode(4)
t6 = TreeNode(12)
t7 = TreeNode(18)
t2.left = t4; t2.right = t5; t3.right = t6;t6.right = t7
class Solution:
# 1.如果是二叉搜索树，非常直接，题目给出pq一定有公共祖先
def lowestCommonAncestor(self, root, p, q):
if root.val > max(p.val, q.val):
return self.lowestCommonAncestor(root.left, p, q)
if root.val < min(p.val, q.val):
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
def lowestCommonAncestor(root, p, q):
# 2.不是二叉搜索树，递归的时候有技巧
if not root:
return None
if root == p or root == q:
return root
else:
l1 = lowestCommonAncestor(root.left, p, q)
l2 = lowestCommonAncestor(root.right, p, q)
if l1 and l2:
return root
elif l1 or l2:
return l1 or l2
else:
return None
print(lowestCommonAncestor(t1,t4,t7).val)
5
剑指 Offer 04. 二维数组中的查找
每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30],
[25, 28, 31, 33, 40]
]
逐行二分法，其实效率也还不错
注意点：
- 如果行长度小于列长度——转置，保证遍历行min(m,n)次，每行二分查找时间复杂度为o(log(max(m,n)))，总复杂度O(min(m,n)*log(max(m,n)))
class Solution:
def findNumberIn2DArray(self, matrix, target):
# 定义二分查找
def binarySearch1(alist,item):
if not alist:
return False
left, right = 0, len(alist) - 1
while left <= right:
if item > alist[right] or item < alist[left]:
return False
mid = (right + left)//2
if alist[mid] == item:
return True
if alist[mid] < item:
left = mid+1
if alist[mid] > item:
right = mid - 1
return False
# 如果是空，直接F
if not len(matrix) or not len(matrix[0]):
return False
# 如果行长<列长——转置，从而实现只遍历min(m,n)次
if len(matrix[0]) < len(matrix):
matrix = zip(*matrix)
# 开始逐行二分:
for row_list in matrix:
if binarySearch1(row_list, target): # 找到了
return True
return False
s7 = Solution()
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30],[2,28,31,33,40]]
s7.findNumberIn2DArray(matrix, 17)
True
转化为图问题
时间复杂度 O(M+N)
这里的旋转之后用二叉搜索树，从左上角或者右下角开始搜索的想法，直呼好家伙！！！神仙思路
def findTarget(matrix, target):
# 从左下角开始
i, j = len(matrix)-1, 0
while i >=0 and j < len(matrix[0]):
cur = matrix[i][j]
if cur < target:
j += 1
if cur > target:
i -= 1
if cur == target:
return True
return False # 包括没找到、空值、等等各种情形
findTarget(matrix, 16)
True
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,4,1,6,20,15,8,11,7]
中序遍历 inorder = [1,4,9,6,3,8,15,11,20,7]
自己的逻辑可以看出，这是一个递归问题
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def rebuild(preorder, inorder):
n = len(preorder)
if not n:
return None
root = TreeNode(preorder[0])
i = inorder.index(preorder[0])
root.left = rebuild(preorder[1:i+1], inorder[:i])
root.right = rebuild( preorder[i+1:], inorder[i+1:])
return root
preorder = [3,9,4,1,6,20,15,8,11,7]
inorder = [1,4,9,6,3,8,15,11,20,7]
t1 = rebuild(preorder, inorder)
t1.val
3
# 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
def print_row(root):
row_list = [root]
res = []
while row_list:
row_res = []
for i in range(len(row_list)):
cur = row_list.pop(0)
row_res.append(cur.val)
if cur.left:
row_list.append(cur.left)
if cur.right:
row_list.append(cur.right)
res.append(row_res)
return res
print_row(t1)
[[3], [9, 20], [4, 6, 15, 7], [1, 8, 11]]
剑指 Offer 12. 矩阵中的路径
- 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
- 输出：true
[["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
感觉是一个图的问题——DFS问题，类似骑士周游
- 我的想法写的太复杂啦：
# 我的解答
def findPath(board, word):
words = list(word)
def dfs(location, k):
if k >= len(words) or not board[location[0]][location[1]] or words[k] != board[location[0]][location[1]]:
return False
if k == len(words) - 1:
print(location)
return True
print(location)
board[location[0]][location[1]] = None
nexts = next_step(board, location)
if not nexts:
return False
for _ in nexts:
if dfs(_, k+1):
return True
board[location[0]][location[1]] = words[k]
return False
def next_step(matrix, location):
res = []
if not len(matrix) or not len(matrix[0]):
return res
m = len(matrix) - 1
n = len(matrix[0]) - 1
cur_x, cur_y = location[0], location[1]
if cur_x >= 1:
res.append([cur_x - 1, cur_y])
if cur_y >= 1:
res.append([cur_x, cur_y - 1])
if cur_x <= m - 1:
res.append([cur_x +1, cur_y])
if cur_y <= n - 1:
res.append([cur_x, cur_y + 1])
return res
def getlocation(matrix, word):
res = []
if not len(matrix) or not len(matrix[0]):
return res
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == word:
res.append([i, j])
return res
start = getlocation(board, words[0])
for s in start:
if dfs(s, 0):
return True
return False
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
findPath(board, 'ABCCEDFSA')
[0, 0]
[0, 1]
[0, 2]
[1, 2]
[2, 2]
[2, 1]
[1, 1]
[1, 0]
[2, 0]
True
标准答案真的清晰简单，好好学好好看：
- 递归的时候一定想清楚函数（）里面是什么更加简洁清晰，多想想在下手敲
- 可以合并的内容尽量合并起来不要再写上面这样又臭又长的code啦
def exist(board, word):
def dfs(i, j, k):
# 结束条件
if not 0<=i<len(board) or not 0<=j<len(board[0]) or board[i][j]!=word[k]:
return False
if k==len(word)-1:
return True
board[i][j] = None
# 递归
return dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or dfs(i, j+1, k+1) or dfs(i, j-1, k+1)
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0):
return True
return False
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
exist(board, 'ABCCEDFSA')
True