剑指offer【60~68】

题目链接:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • 剑指offer【03~09】

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

    echobingo
  • 剑指offer【20~29】

    方法1:使用正则表达式,格式为 import re,re.match(r"^...$", s) ,其中 ^ 表示匹配 s 的开始,$ 表示匹配 s 的结尾,.....

    echobingo
  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • C++版 - Leetcode 8: String to Integer (myAtoi,C库函数atoi模拟) (剑指offer 面试题49) 解题报告

    提交网址: https://leetcode.com/problems/string-to-integer-atoi/

    Enjoy233
  • python操作MongoDB

    爱撒谎的男孩
  • Android仿京东、天猫商品详情页

    前言 前面在介绍控件TabLayout控件和CoordinatorLayout使用的时候说了下实现京东、天猫详情页面的效果,今天要说的是优化版,是我们线上实现的...

    xiangzhihong
  • Android仿京东、天猫商品详情页

    前言 前面在介绍控件TabLayout控件和CoordinatorLayout使用的时候说了下实现京东、天猫详情页面的效果,今天要说的是优化版,是我们线上实现的...

    xiangzhihong
  • Android Architecture Component之Lifecycle解析HeaderLifecyclePart 1Part 2Part 3Footer

    终于到了最后的关头,Android Architecture Component 系列的最后一节内容。今天给大家带来的就是 Lifecycle 的解析。

    俞其荣
  • 一文看尽15种语义分割损失函数(含代码解析)

    https://github.com/shruti-jadon/Semantic-Segmentation-Loss-Functions

    Amusi

扫码关注云+社区

领取腾讯云代金券