<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 1227. 飛機座位分配概率 ## 題目地址(1227. 飛機座位分配概率) <https://leetcode-cn.com/problems/airplane-seat-assignment-probability/> ## 題目描述 ``` <pre class="calibre18">``` 有 n 位乘客即將登機,飛機正好有 n 個座位。第一位乘客的票丟了,他隨便選了一個座位坐下。 剩下的乘客將會: 如果他們自己的座位還空著,就坐到自己的座位上, 當他們自己的座位被占用時,隨機選擇其他座位 第 n 位乘客坐在自己的座位上的概率是多少? 示例 1: 輸入:n = 1 輸出:1.00000 解釋:第一個人只會坐在自己的位置上。 示例 2: 輸入: n = 2 輸出: 0.50000 解釋:在第一個人選好座位坐下后,第二個人坐在自己的座位上的概率是 0.5。 提示: 1 <= n <= 10^5 ``` ``` ## 前置知識 - 記憶化搜索 - 動態規劃 ## 暴力遞歸 這是一道 LeetCode 為數不多的概率題,我們來看下。 ## 公司 - 字節 ### 思路 我們定義原問題為 f(n)。對于第一個人來說,他有 n 中選擇,就是分別選擇 n 個座位中的一個。由于選擇每個位置的概率是相同的,那么選擇每個位置的概率應該都是 1 / n。 我們分三種情況來討論: - 如果第一個人選擇了第一個人的位置(也就是選擇了自己的位置),那么剩下的人按照票上的座位做就好了,這種情況第 n 個人一定能做到自己的位置 - 如果第一個人選擇了第 n 個人的位置,那么第 n 個人肯定坐不到自己的位置。 - 如果第一個人選擇了第 i (1 < i < n)個人的位置,那么第 i 個人就相當于變成了“票丟的人”,此時問題轉化為 f(n - i + 1)。 此時的問題轉化關系如圖: ![](https://img.kancloud.cn/8e/2e/8e2eb2ac16efc01131baad9a0f7c4670_1586x664.jpg)(紅色表示票丟的人) 整個過程分析: ![](https://img.kancloud.cn/ad/8c/ad8c321a36a5538a1034b976d0cc7fbe_1586x404.jpg) ### 代碼 代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nthPersonGetsNthSeat</span><span class="hljs-params">(self, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0.5</span> res = <span class="hljs-params">1</span> / n <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, n): res += self.nthPersonGetsNthSeat(n - i + <span class="hljs-params">1</span>) * <span class="hljs-params">1</span> / n <span class="hljs-keyword">return</span> res ``` ``` 上述代碼會棧溢出。 ## 暴力遞歸 + hashtable ### 思路 我們考慮使用記憶化遞歸來減少重復計算,雖然這種做法可以減少運行時間,但是對減少遞歸深度沒有幫助。還是會棧溢出。 ### 代碼 代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> seen = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nthPersonGetsNthSeat</span><span class="hljs-params">(self, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0.5</span> <span class="hljs-keyword">if</span> n <span class="hljs-keyword">in</span> self.seen: <span class="hljs-keyword">return</span> self.seen[n] res = <span class="hljs-params">1</span> / n <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, n): res += self.nthPersonGetsNthSeat(n - i + <span class="hljs-params">1</span>) * <span class="hljs-params">1</span> / n self.seen[n] = res <span class="hljs-keyword">return</span> res ``` ``` ## 動態規劃 ### 思路 上面做法會棧溢出。其實我們根本不需要運行就應該能判斷出棧溢出,題目已經給了數據規模是 1 <= n <= 10 \*\* 5。 這個量級不管什么語言,除非使用尾遞歸,不然一般都會棧溢出,具體棧深度大家可以查閱相關資料。 既然是棧溢出,那么我們考慮使用迭代來完成。 很容易想到使用動態規劃來完成。其實遞歸都寫出來,寫一個樸素版的動態規劃也難不到哪去,畢竟動態規劃就是記錄子問題,并建立子問題之間映射而已,這和遞歸并無本質區別。 ### 代碼 代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nthPersonGetsNthSeat</span><span class="hljs-params">(self, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0.5</span> dp = [<span class="hljs-params">1</span>, <span class="hljs-params">.5</span>] * n <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, n): dp[i] = <span class="hljs-params">1</span> / n <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, i): dp[i] += dp[i - j + <span class="hljs-params">1</span>] * <span class="hljs-params">1</span> / n <span class="hljs-keyword">return</span> dp[<span class="hljs-params">-1</span>] ``` ``` 這種思路的代碼超時了,并且僅僅執行了 35/100 testcase 就超時了。 ## 數學分析 ### 思路 我們還需要進一步優化時間復雜度,我們需要思考是否可以在線形的時間內完成。 我們繼續前面的思路進行分析, 不難得出,我們不妨稱其為等式 1: ``` <pre class="calibre18">``` f(n) = 1/n + 0 + 1/n * (f(n-1) + f(n-2) + ... + f(2)) = 1/n * (f(n-1) + f(n-2) + ... + f(2) + 1) = 1/n * (f(n-1) + f(n-2) + ... + f(2) + f(1)) ``` ``` 似乎更復雜了?沒關系,我們繼續往下看,我們看下 f(n - 1),我們不妨稱其為等式 2。 ``` <pre class="calibre18">``` f(n-1) = 1/(n-1) * (f(n-2) + f(n-3) + ... + f(1)) ``` ``` 我們將等式 1 和等式 2 兩邊分別同時乘以 n 和 n - 1 ``` <pre class="calibre18">``` n * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) (n-1) * f(n-1) = f(n-2) + f(n-3) + ... + f(1) ``` ``` 我們將兩者相減: ``` <pre class="calibre18">``` n * f(n) - (n-1)*f(n-1) = f(n-1) ``` ``` 我們繼續將 (n-1)\*f(n-1) 移到等式右邊,得到: ``` <pre class="calibre18">``` n * f(n) = n * f(n-1) ``` ``` 也就是說: ``` <pre class="calibre18">``` f(n) = f(n - 1) ``` ``` 當然前提是 n 大于 2。 既然如此,我們就可以減少一層循環, 我們用這個思路來優化一下上面的 dp 解法。這種解法終于可以 AC 了。 ### 代碼 代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nthPersonGetsNthSeat</span><span class="hljs-params">(self, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0.5</span> dp = [<span class="hljs-params">1</span>, <span class="hljs-params">.5</span>] * n <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">2</span>, n): dp[i] = <span class="hljs-params">1</span>/n+(n<span class="hljs-params">-2</span>)/n * dp[n<span class="hljs-params">-1</span>] <span class="hljs-keyword">return</span> dp[<span class="hljs-params">-1</span>] ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 優化數學分析 ### 思路 上面我們通過數學分析,得出了當 n 大于 2 時: ``` <pre class="calibre18">``` f(n) = f(n - 1) ``` ``` 那么是不是意味著我們隨便求出一個 n 就好了? 比如我們求出 n = 2 的時候的值,是不是就知道 n 為任意數的值了。 我們不難想出 n = 2 時候,概率是 0.5,因此只要 n 大于 1 就是 0.5 概率,否則就是 1 概率。 ### 代碼 代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">nthPersonGetsNthSeat</span><span class="hljs-params">(self, n: int)</span> -> float:</span> <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span> <span class="hljs-keyword">else</span> <span class="hljs-params">.5</span> ``` ``` **復雜度分析** - 時間復雜度:O(1)O(1)O(1) - 空間復雜度:O(1)O(1)O(1) ## 關鍵點 - 概率分析 - 數學推導 - 動態規劃 - 遞歸 + mapper - 棧限制大小 - 尾遞歸 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看