题目链接：
剑指offer 60-68
目录：
60. n 个骰子的点数
61. 扑克牌顺子
62. 圆圈中最后剩下的数
63. 股票的最大利润
64. 求 1+2+3+...+n
65. 不用加减乘除做加法
66. 构建乘积数组
67. 把字符串转换成整数
68. 树中两个节点的最低公共祖先
Python 实现：
60. n 个骰子的点数
动态规划。令 dp[n][6*n]，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。则 dp[-1][1...6*n] 就是每一种点数的次数。点数的总次数为 6^n，然后再求概率即可。状态转移方程很好找：dp[i][j] += dp[i-1][j-k]，其中 k 为点数 1~6。时间复杂度为 O(n*(6*n)*6)，空间复杂度为 O(n*(6*n))。
class Solution:
# @param {int} n an integer
# @return {tuple[]} a list of tuple(sum, probability)
def dicesSum(self, n):
# Write your code here
dp = [[0] * (6 * n + 1) for _ in range(n + 1)]
ans = []
for i in range(1, 7): # 初始化
dp[1][i] = 1
for i in range(2, n + 1): # 掷 n 枚骰子
for j in range(i, 6 * i + 1): # n 枚骰子之和
for k in range(1, 7):
if j > k:
dp[i][j] += dp[i-1][j-k] # dp[i][j] 却决于 dp[i-1][j-k]
total = 6 ** n # 点数的总次数
for j in range(n, 6 * n + 1): # 求每个点数出现的概率
ans.append([j, dp[-1][j] / total])
return ans
因为 dp[i][...] 只依赖于 dp[i-1][...]，实际上空间还可以继续优化到 O(n)，即使用旋转数组 dp[flag][...] 和 dp[1-flag][...] 交替存储。代码略。
61. 扑克牌顺子
排序，然后用癞子（0）补全中间有差值的地方。
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if len(numbers) != 5:
return False
numbers.sort() # 排序
zeros = 0
for i in range(len(numbers) - 1):
if numbers[i] == 0:
zeros += 1
elif numbers[i+1] - numbers[i] == 0: # 连续两个数相同
return False
elif numbers[i+1] - numbers[i] <= 1 + zeros: # 癞子数量足够
zeros -= (numbers[i+1] - numbers[i] - 1)
else:
return False
return True
62. 圆圈中最后剩下的数
经典的约瑟夫环问题，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。可以得到递推公式，f(n) = (f(n-1) +m) % n。时间复杂度为 O(n)，空间复杂度为 O(1)（因为 f(n) 只依赖于 f(n-1)）。
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
ans = -1
for i in range(1, n + 1):
ans = (ans + m) % i # f(n) = (f(n-1) + m) % n
return ans if n != 0 else -1 # 没有小朋友返回 -1
63. 股票的最大利润
股票单买单卖问题，详情请见我的博客：Leetcode 股票合集 【121、122、714、309】
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_, min_ = 0, float("inf")
for i in range(len(prices)):
min_ = min(min_, prices[i])
max_ = max(max_, prices[i]-min_)
return max_
64. 求 1+2+3+...+n
由题目限制只能使用递归求解前 n 个数的和，但是递归出口有 if，怎么解决？使用“与”（and）操作进行短路处理即可。
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
ans = n
# 使用 and 的短路处理作为递归出口
tmp = (n > 0) and self.Sum_Solution(n - 1)
ans += tmp
return ans
65. 不用加减乘除做加法
位操作。a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。
递归终止的条件是进位 (a & b) << 1 最终会变为 0。
注意：这道题如果使用 Python 实现，会有问题，因为 Python 在进行负数的按位加法时，int 类型无限大，程序会无限进行下去导致超时，因此还要进行截断处理。
这里放上 C++ 的代码（递归实现）和 Python 代码（迭代实现）：
class Solution {
public:
int Add(int num1, int num2)
{
if(num2 == 0)
return num1;
return Add(num1 ^ num2, (num1 & num2) << 1);
}
};
class Solution:
def Add(self, num1, num2):
# write code here
while num2 != 0:
tmp = num1 ^ num2
num2 = (num1 & num2) << 1
num1 = tmp & 0xFFFFFFFF # Python 把数限制在 32 位内
# 最高位为符号位，为 0 则说明正数，返回 num1，否则为 1，说明负数，取其补码
return num1 if num1 >> 31 == 0 else ~ (num1 ^ 0xFFFFFFFF)
66. 构建乘积数组
- 对原数组，分别从左到右和从右到左进行累乘，得到 left 和 right 数组。对于 A[i]，将 left[i-1] 与 right[i] 相乘就可以得到 B[i]。
- left 可以在从左到右遍历的过程中使用一个变量保存。时间复杂度和空间复杂度均为 O(n)。
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
if not A:
return []
lens = len(A)
right = [1] * lens # 从右到左累乘
for i in range(lens - 1, 0, -1):
right[i-1] = right[i] * A[i]
B = [0] * lens
left = 1 # 从左到右累乘
for i in range(lens):
B[i] = left * right[i]
left *= A[i]
return B
67. 把字符串转换成整数
字符串操作，注意数字的 +- 号和整数构造的方法即可。
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
if s == "":
return 0
i, num, sign = 0, 0, 1 # sign 为符号
flag = True # 标记数字之后不能出现 +- 这种符号
for i in range(len(s)):
if (not '0' <= s[i] <= '9') and (s[i] not in "+-"): # 非法字符
return 0
if flag == False and (s[i] in "+-"): # 数字后面出现字符+-
return 0
if s[i] in '-': # 可能出现 ---2 / +-3 这种
sign *= -1
if '0' <= s[i] <= '9':
flag = False
num = num * 10 + ord(s[i]) - ord('0') # 构造数字
return sign * num if -2 ** 31 <= sign * num <= 2 ** 31 - 1 else 0 # 越界
68. 树中两个节点的最低公共祖先
二叉查找树
由于二叉查找树（BST）的性质，可以从根节点出发，如果根节点比两个节点都大，则遍历左子树；根节点比两个节点都小，则遍历右子树；直到两个节点比根节点一大一小，则该根节点就是最低公共祖先；
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or p.val <= root.val <= q.val or q.val <= root.val <= p.val:
return root
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, q, p)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, q, p)
普通二叉树
在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最近公共祖先。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q: # p 和 q 中有一个和根节点相同
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left == None: # 在右子树中找到的祖先
return right
if right == None: # 在左子树中找到的祖先
return left
return root # 根节点就是祖先
剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。这里做一个总结：
剑指offer【03~09】
剑指offer【10~19】
剑指offer【20~29】
剑指offer【30~39】
剑指offer【40~49】
剑指offer【50~59】
剑指offer【60~68】
网友评论