# 剑指offer【60~68】

#### Python 实现：

##### 60. n 个骰子的点数

``````class Solution:
# @param {int} n an integer
# @return {tuple[]} a list of tuple(sum, probability)
def dicesSum(self, n):
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``````

##### 61. 扑克牌顺子

``````# -*- 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. 圆圈中最后剩下的数

``````# -*- 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. 股票的最大利润

``````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

``````# -*- 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. 不用加减乘除做加法

``````class Solution {
public:
{
if(num2 == 0)
return num1;
return Add(num1 ^ num2, (num1 & num2) << 1);
}
};``````
``````class Solution:
# 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  # 越界``````
##### 二叉查找树

``````# 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)``````
##### 普通二叉树

``````# 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  # 根节点就是祖先``````

0 条评论

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

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

• ### 剑指offer（51-60）题解

显然我们可以想到通过遍历的方式，但是一旦出现环，那么我们是遍历不完的，所以我们必须添加截止条件，每次我们遍历一个元素时就将他的值存入list之中，这样我们就...

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

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

• ### 【剑指Offer】60. n个骰子的点数

使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

• ### 一个正经的前端学习 开源 仓库（阶段二十五）

一个 ☝️ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。（非常口语化的，手写总结）

• ### 一个正经的前端学习 开源 仓库（阶段二十六）

一个 ☝️ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。（非常口语化的，手写总结）

• ### 一个正经的前端学习 开源 仓库（每日更新）-572道知识点

一个 ☝️ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。（非常口语化的，手写总结）

• ### 一个正经的前端学习 开源 仓库（每日更新）-598道知识点

一个 ☝ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。一个人可以走的更快，但一群人才能走的更远。（非常口语化的，...

• ### emmo!!!

一个 ☝ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。一个人可以走的更快，但一群人才能走的更远。（非常口语化的，...

• ### 【每日更新 Suggest 】leetcode解题

一个 ☝️ 正经的前端学习 开源 仓库，启发来自 淘宝大佬 @冴羽 ，初心做一个真正能帮助到大家的仓库。（非常口语化的，手写总结）

• ### 刷题笔记 | 剑指Offer 03 二维数组中的查找

本文主要讲解《剑指Offer》中第03题"二维数组中的查找"，介绍题目、解决思路、解题步骤，并分别以C++和Python编程语言解答此题。

• ### 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

思路：由二叉搜索树的性质我们很容易得到从根结点到p和q的路径，那么p和q的最近公共祖先就是从根结点到他们路径上的最后一个相同的结点。

• ### 写给Java程序员看的算法学习指南！

大家好，我是 Guide 哥！这篇文章我会推荐一些关于算法学习的书籍以及资源。希望对大家学习算法有帮助！

• ### LeetCode 236. 二叉树的最近公共祖先

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节...

• ### 剑指Offer全解

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个...

• ### 剑指offer【03~09】

注意：这道题如果数据范围变为 [1, n]，那么可以将其转化为使用快慢指针判断有环问题，和 Leetcode 【Two Pointers】287. Find t...

• ### 剑指offer【10~19】

f(n) = f(n-1) + f(n-2) + ... + f(0)，其中 f(i) 表示从第 i 层跳到第 n 层的跳法。化简的 f(n) = 2 * f(...