剑指offer【60~68】

echobingo

发布于 2019-12-20 11:59:41

3640

发布于 2019-12-20 11:59:41

题目链接：

Python 实现：

动态规划。令 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 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

python

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

python

编程算法

登录后参与评论

0 条评论

热度