溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

LeetCode如何求n個骰子的點數(shù)

發(fā)布時間:2021-12-15 13:56:25 來源:億速云 閱讀:129 作者:小新 欄目:大數(shù)據(jù)

這篇文章主要介紹了LeetCode如何求n個骰子的點數(shù),具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。

題目描述

把 n 個骰子扔在地上,所有骰子朝上一面的點數(shù)之和為 s。輸入 n,打印出 s 的所有可能的值出現(xiàn)的概率。

你需要用一個浮點數(shù)數(shù)組返回答案,其中第 i 個元素代表這 n 個骰子所能擲出的點數(shù)集合中第 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]

                     

題目思考

  1. 可以根據(jù) n 個骰子的概率推導(dǎo)出 n+1 個骰子的概率嗎
                     

解決方案

                     
思路
  • 分析題目, 先從 1 個骰子的最簡單情況出發(fā), 顯然點數(shù)為 1~6 的概率都是 1/6
  • 那如果是 2 個骰子呢? 假設(shè)第一個骰子點數(shù)為 1, 第二個可以是 1~6, 兩者之和就是 2~7; 而如果第一個點數(shù)為 2, 那么兩者之和就是 3~8, 以此類推
  • 顯然 2 個骰子點數(shù)之和為 2 的概率是                         (1/6)*(1/6)=1/36, 只有 1+1 一種情況; 而點數(shù)之和為 3 的概率是                         1/36+1/36=1/18, 有 1+2 和 2+1 兩種情況, 以此類推
  • 所以如果我們使用一個字典來保存當(dāng)前骰子數(shù) n 的每個點數(shù)之和的概率, 即鍵值對是                         {點數(shù)和:概率}, 那么對于 n+1 而言, 我們只需要對每個點數(shù)之和加上 1~6 作為新的點數(shù)之和, 將原有概率乘以 1/6 累加到新的點數(shù)和對應(yīng)的概率上即可
  • 最后只需要根據(jù)有效點數(shù)之和從小到大, 將字典中的值依次存入最終結(jié)果中
  • 對于 n 個骰子而言, 其點數(shù)之和最小為 n (每個骰子點數(shù)都是 1), 最大為                         6*n (每個骰子點數(shù)都是 6)
  • 下面代碼對必要的步驟有詳細(xì)的解釋, 方便大家理解
                     
復(fù)雜度
  • 時間復(fù)雜度 O(N^2): 兩層循環(huán), 外層遍歷 N 個數(shù), 內(nèi)層遍歷                         5N*6 個數(shù)
  • 空間復(fù)雜度 O(N): 字典中需要存 5N 個鍵值對
                     
代碼
import collections


class Solution:
    def twoSum(self, n: int) -> List[float]:
        # DP, dp為當(dāng)前的點數(shù)和=>概率的字典, 初始化dp[0] = 1, 代表0個骰子時點數(shù)之和為0的概率為1
        # 增加一個骰子后, 我們只需要對原來字典的每個點數(shù)之和加上 1~6 作為新的點數(shù)之和, 并將原有概率乘以 1/6 累加到新的點數(shù)和對應(yīng)的概率上即可
        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):
                    # 增加一個骰子后, 累加其概率到新的點數(shù)和上
                    newdp[sm + v] += dp[sm] / 6
            dp = newdp
        res = []
        for sm in range(n, 6 * n + 1):
            # 將值依次存入結(jié)果中
            res.append(dp[sm])
        return res

感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“LeetCode如何求n個骰子的點數(shù)”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習(xí)!

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI