图解LeetCode——剑指 Offer 60. n个骰子的点数

简介: 图解LeetCode算法

一、题目

n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

二、示例

2.1> 示例 1:

输入】 1

输出】 [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

2.2> 示例 2:

输入】 2

输出】 [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制:

  • 1 <= n <= 11

三、解题思路

根据题目要求,我们需要获得N个骰子总和点数的概率集合,那么我们就从最简单的1个骰子来看,那么针对一个骰子来说,一共会有从1~6的六个点,并且每个点被投掷出来的概率都是一样的,即:1/6的概率(0.16667);

那么两个骰子呢?其投掷的总和的值就在从2~12的这11个点(因为一个骰子的点数是从1~6)。那么如何计算其概率呢?我们可以拿两个骰子A和B为例。以骰子A作为基准骰子,以骰子B作为附加值骰子,那么就有如下图规则:

当投出附加骰子为1点时

基准骰子1点的总和为2;

基准骰子2点的总和为3;

基准骰子3点的总和为4;

基准骰子4点的总和为5;

基准骰子5点的总和为6;

基准骰子6点的总和为7;

当投出附加骰子为2点时

基准骰子1点的总和为3;

基准骰子2点的总和为4;

基准骰子3点的总和为5;

基准骰子4点的总和为6;

基准骰子5点的总和为7;

基准骰子6点的总和为8;

关于投出附加骰子的其他数值,依次类推即可,我就不一一列出来了……

那么如果投掷的骰子是3个呢?即:增加一个骰子C;那么我们也可以将其作为“两个骰子”来计算,即:(骰子A骰子B的概率)和 骰子C的概率(1/6)。所以,无论是求多少个骰子的总和值概率,我们都可以一步步的将其归化为两个骰子的概率计算方式。下图是两个骰子和三个骰子的概率计算过程:

那么上面介绍完解题思想了之后,我们还是通过示例来加深对这道题的理解。下面我们以两个骰子为例,计算其投掷值总和的概率。具体操作,请见下图所示:

四、代码实现

class Solution {
    public double[] dicesProbability(int n) {
        double[] result = new double[6];
        Arrays.fill(result, 1/6d);
        double[] temp;
        for (int m = 2; m <= n; m++) {
            temp = new double[5 * m + 1];
            for (int i = 0; i < result.length; i++) 
                for (int j = 0; j < 6; j++) 
                    temp[i+j] += result[i] / 6;
            result = temp;
        }
        return result;
    }
}

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
52 4
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 49. 丑数
解决剑指 Offer 49题"丑数"的Python实现,通过动态规划的方法计算出第n个丑数。
46 2
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 04. 二维数组中的查找
剑指Offer题目 "二维数组中的查找" 的Python解决方案,包括非递归迭代、递归以及使用内置函数的二分查找方法,以判断一个有序的二维数组中是否含有给定整数。
38 1
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
39 1
|
4月前
|
iOS开发 MacOS
【Mac系统】解决Vscode中LeetCode插件不能刷剑指offer题库
文章讨论了解决Mac系统中Vscode里LeetCode插件无法刷剑指Offer题库的问题,并提供了一些相关的使用技巧和资源链接。
253 1
|
1月前
|
存储
leetcode 740 删除并获得点数
【11月更文挑战第2天】给定一个整数数组 `nums`,每次可以选择删除一个元素并获得该元素的点数,同时该元素的左右相邻元素会变成相邻元素。目标是返回你能获得的最大点数。通过动态规划解决,统计每个数字的出现次数,设 `dp[i]` 表示以数字 `i` 结尾时能获得的最大点数。最终结果为 `dp` 数组中的最大值。时间复杂度为 O(n + m),空间复杂度为 O(m)。
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
29 4
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
Leetcode题目"剑指 Offer 21. 调整数组顺序使奇数位于偶数前面"的两种Python解决方案,一种是使用双端队列调整数组顺序,另一种是使用双指针法将奇数移到数组前半部分,偶数移到后半部分。
29 4