<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0877. 石子游戲 ## 題目地址(877. 石子游戲) <https://leetcode-cn.com/problems/stone-game/> ## 題目描述 ``` <pre class="calibre18">``` 亞歷克斯和李用幾堆石子在做游戲。偶數堆石子排成一行,每堆都有正整數顆石子 piles[i] 。 游戲以誰手中的石子最多來決出勝負。石子的總數是奇數,所以沒有平局。 亞歷克斯和李輪流進行,亞歷克斯先開始。 每回合,玩家從行的開始或結束處取走整堆石頭。 這種情況一直持續到沒有更多的石子堆為止,此時手中石子最多的玩家獲勝。 假設亞歷克斯和李都發揮出最佳水平,當亞歷克斯贏得比賽時返回 true ,當李贏得比賽時返回 false 。 示例: 輸入:[5,3,4,5] 輸出:true 解釋: 亞歷克斯先開始,只能拿前 5 顆或后 5 顆石子 。 假設他取了前 5 顆,這一行就變成了 [3,4,5] 。 如果李拿走前 3 顆,那么剩下的是 [4,5],亞歷克斯拿走后 5 顆贏得 10 分。 如果李拿走后 5 顆,那么剩下的是 [3,4],亞歷克斯拿走后 4 顆贏得 9 分。 這表明,取前 5 顆石子對亞歷克斯來說是一個勝利的舉動,所以我們返回 true 。 提示: 2 <= piles.length <= 500 piles.length 是偶數。 1 <= piles[i] <= 500 sum(piles) 是奇數。 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 字節 ## 思路 由于 piles 是偶數的,并且 piles 的總和是奇數的。 因此 Alex`可以做到`要不拿的全部是奇數,要么全部是偶數。 舉個例子: 比如 Alex 第一次先拿第一個 這里有兩種情況: 1. Lee 如果拿了第二塊(偶數),那么 Alex 繼續拿第三塊,以此類推。。。 2. Lee 如果拿了最后一塊(偶數),那么 Alex 繼續拿倒數第二塊,以此類推。。。 因此 Alex`可以`做到只拿奇數或者偶數,只是他可以控制的,因此他要做的就是數一下,奇數加起來多還是偶數加起來多就好了。 奇數多就全部選奇數,偶數就全部選偶數。 Lee 是沒有這種自由權的。 ## 關鍵點解析 - 可以用 DP(動態規劃) - 可以從數學的角度去分析 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} piles * @return {boolean} */</span> <span class="hljs-keyword">var</span> stoneGame = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">piles</span>) </span>{ <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; }; ``` ``` ## 擴展 騰訊面試題:一共 100 只弓箭 你和你的對手共用。你們每次只能射出一支箭或者兩支箭,射擊交替進行,設計一個算法,保證自己獲勝。 答案: 先手,剩下的是 3 的倍數就行(100-1=99),然后按照 3 的倍數射箭必贏。 比如你先拿了 1,剩下 99 個。 對手拿了 1,你就拿 2。這樣持續 33 次就贏了。如果對手拿了 2 個,你就拿 1 個,這樣持續 33 次你也是贏的。 > 這是一種典型的博弈問題, 你和對手交替進行,對手的行動影響你接下來的策略。 這算是一種最簡單的博弈問題了
                  <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>

                              哎呀哎呀视频在线观看