LeetCode如何求n个骰子的点数
发表于:2024-12-13 作者:千家信息网编辑
千家信息网最后更新 2024年12月13日,这篇文章主要介绍了LeetCode如何求n个骰子的点数,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。题目描述把 n 个骰子扔在地上,所
千家信息网最后更新 2024年12月13日LeetCode如何求n个骰子的点数
这篇文章主要介绍了LeetCode如何求n个骰子的点数,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
题目描述
把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
1 <= n <= 11
题目样例
示例
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
题目思考
可以根据 n 个骰子的概率推导出 n+1 个骰子的概率吗
解决方案
思路
分析题目, 先从 1 个骰子的最简单情况出发, 显然点数为 1~6 的概率都是 1/6 那如果是 2 个骰子呢? 假设第一个骰子点数为 1, 第二个可以是 1~6, 两者之和就是 2~7; 而如果第一个点数为 2, 那么两者之和就是 3~8, 以此类推 显然 2 个骰子点数之和为 2 的概率是 (1/6)*(1/6)=1/36
, 只有 1+1 一种情况; 而点数之和为 3 的概率是1/36+1/36=1/18
, 有 1+2 和 2+1 两种情况, 以此类推所以如果我们使用一个字典来保存当前骰子数 n 的每个点数之和的概率, 即键值对是 {点数和:概率}
, 那么对于 n+1 而言, 我们只需要对每个点数之和加上 1~6 作为新的点数之和, 将原有概率乘以 1/6 累加到新的点数和对应的概率上即可最后只需要根据有效点数之和从小到大, 将字典中的值依次存入最终结果中 对于 n 个骰子而言, 其点数之和最小为 n (每个骰子点数都是 1), 最大为 6*n
(每个骰子点数都是 6)下面代码对必要的步骤有详细的解释, 方便大家理解
复杂度
时间复杂度 O(N^2): 两层循环, 外层遍历 N 个数, 内层遍历 5N*6
个数空间复杂度 O(N): 字典中需要存 5N 个键值对
代码
import collections
class Solution:
def twoSum(self, n: int) -> List[float]:
# DP, dp为当前的点数和=>概率的字典, 初始化dp[0] = 1, 代表0个骰子时点数之和为0的概率为1
# 增加一个骰子后, 我们只需要对原来字典的每个点数之和加上 1~6 作为新的点数之和, 并将原有概率乘以 1/6 累加到新的点数和对应的概率上即可
dp = {}
dp[0] = 1
for i in range(1, n + 1):
newdp = collections.defaultdict(int)
for sm in dp:
for v in range(1, 7):
# 增加一个骰子后, 累加其概率到新的点数和上
newdp[sm + v] += dp[sm] / 6
dp = newdp
res = []
for sm in range(n, 6 * n + 1):
# 将值依次存入结果中
res.append(dp[sm])
return res
感谢你能够认真阅读完这篇文章,希望小编分享的"LeetCode如何求n个骰子的点数"这篇文章对大家有帮助,同时也希望大家多多支持,关注行业资讯频道,更多相关知识等着你来学习!
点数
骰子
概率
之和
字典
篇文章
题目
复杂
复杂度
情况
输入
以此类推
个数
代码
代表
就是
结果
类推
输出
最小
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
我的世界服务器简介修改颜色
北京盛世泰伯网络技术有
主流软件开发过程有哪些
功能安全设备 数据库
数据库2021会议时间线
浙教版网络技术应用课时
大一数据库的应用论文
财务软件能装到云数据库吗
网络安全单项选择考试题
全国期刊联合目录数据库
软件开发转行转什么比较好
广东应用软件开发常见问题
浪潮服务器生产地
不死鸟互联网科技公司
阿拉德之怒官方平台服务器升级
be的服务器
数据库主键设置为自动增长
架设流媒体服务器软件
阿里云数据库如何使用
男生学软件开发
朝阳区管理软件开发口碑推荐
内蒙古电子软件开发计划
银川学习网络安全
软件开发未签保密协议书
台湾odm服务器厂商
数据库linux优化
阿里云 上传数据库文件
武器移动通信网络技术的优点
网络技术监管手段
大学城网络安全工程师