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

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/524cf64f28b5复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 快速拿下面试算法

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

    公众号guangcity
  • 剑指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编程语言解答此题。

    Amusi
  • 剑指Offer-1

    晚上没宵夜
  • 剑指Offer-2

    晚上没宵夜
  • 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

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

    杨鹏伟
  • 写给Java程序员看的算法学习指南!

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

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

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

    Michael阿明
  • 剑指Offer全解

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

    racaljk
  • 剑指offer【03~09】

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

    echobingo
  • 剑指offer【10~19】

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

    echobingo

扫码关注云+社区

领取腾讯云代金券