<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之旅 廣告
                # 0935. 騎士撥號器 ## 題目地址 (935. 騎士撥號器) <https://leetcode-cn.com/problems/knight-dialer/> ## 題目描述 ``` <pre class="calibre18">``` 國際象棋中的騎士可以按下圖所示進行移動: ``` ``` ![](https://img.kancloud.cn/62/3b/623ba1013108392121e3de8c9bbb9bcb_183x205.jpg) ``` <pre class="calibre18">``` 這一次,我們將 “騎士” 放在電話撥號盤的任意數字鍵(如上圖所示)上,接下來,騎士將會跳 N-1 步。每一步必須是從一個數字鍵跳到另一個數字鍵。 每當它落在一個鍵上(包括騎士的初始位置),都會撥出鍵所對應的數字,總共按下 N 位數字。 你能用這種方式撥出多少個不同的號碼? 因為答案可能很大,所以輸出答案模 10^9 + 7。 示例 1: 輸入:1 輸出:10 示例 2: 輸入:2 輸出:20 示例 3: 輸入:3 輸出:46 提示: 1 <= N <= 5000 ``` ``` ## 前置知識 - DFS - 記憶化搜索 ## 深度優先遍歷(DFS) ## 公司 - 暫無 ### 思路 這道題要求解一個數字。并且每一個格子能夠跳的狀態是確定的。 因此我們的思路就是“狀態機”(動態規劃),暴力遍歷(BFS or DFS),這里我們使用 DFS。(注意這幾種思路并無本質不同) 對于每一個號碼鍵盤,我們可以轉移的狀態是確定的,我們做一個”預處理“,將這些狀態轉移記錄到一個數組 jump,其中 jump\[i\] 表示 i 位置可以跳的點(用一個數組來表示)。問題轉化為: - 從 0 開始所有的路徑 - 從 1 開始所有的路徑 - 從 2 開始所有的路徑 - ... - 從 9 開始所有的路徑 不管從幾開始思路都是一樣的。 我們使用一個函數 f(i, n) 表示`騎士在 i 的位置,還剩下 N 步可以走`的時候可以撥出的總的號碼數。那么問題就是求解 `f(0, N) + f(1, N) + f(2, N) + ... + f(9, N)`。對于 f(i, n),我們初始化 cnt 為 0,由于 i 能跳的格子是 jump\[i\],我們將其 `cnt += f(j, n - 1)`,其中 j 屬于 jump\[i\],最終返回 cnt 即可。 不難看出,這種算法有大量重復計算,我們使用記憶化遞歸形式來減少重復計算。 這種算法勉強通過。 ### 代碼 ``` <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">knightDialer</span><span class="hljs-params">(self, N: int)</span> -> int:</span> cnt = <span class="hljs-params">0</span> jump = [[<span class="hljs-params">4</span>, <span class="hljs-params">6</span>], [<span class="hljs-params">6</span>, <span class="hljs-params">8</span>], [<span class="hljs-params">7</span>, <span class="hljs-params">9</span>], [<span class="hljs-params">4</span>, <span class="hljs-params">8</span>], [ <span class="hljs-params">0</span>, <span class="hljs-params">3</span>, <span class="hljs-params">9</span>], [], [<span class="hljs-params">0</span>, <span class="hljs-params">1</span>, <span class="hljs-params">7</span>], [<span class="hljs-params">2</span>, <span class="hljs-params">6</span>], [<span class="hljs-params">1</span>, <span class="hljs-params">3</span>], [<span class="hljs-params">2</span>, <span class="hljs-params">4</span>]] visited = dict() <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(i, n)</span>:</span> <span class="hljs-keyword">if</span> (i, n) <span class="hljs-keyword">in</span> visited: <span class="hljs-keyword">return</span> visited[(i, n)] <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> cnt = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> jump[i]: cnt += helper(j, n - <span class="hljs-params">1</span>) visited[(i, n)] = cnt <span class="hljs-keyword">return</span> cnt <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">10</span>): cnt += helper(i, N) <span class="hljs-keyword">return</span> cnt % (<span class="hljs-params">10</span>**<span class="hljs-params">9</span> + <span class="hljs-params">7</span>) ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 樸素遍歷 ### 思路 我們使用迭代的形式來優化上述過程。我們初始化十個變量分別表示鍵盤不同位置能夠撥出的號碼數,并且初始化為 1。接下來我們只要循環 N - 1 次,不斷更新狀態即可。不過這種算法和上述算法并無本質不同。 ### 代碼 ``` <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">knightDialer</span><span class="hljs-params">(self, N: int)</span> -> int:</span> a0 = a1 = a2 = a3 = a4 = a5 = a6 = a7 = a8 = a9 = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(N - <span class="hljs-params">1</span>): a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = a4 + a6, a6 + a8, a7 + \ a9, a4 + a8, a0 + a3 + a9, <span class="hljs-params">0</span>, a0 + a1 + a7, a2 + a6, a1 + a3, a2 + a4 <span class="hljs-keyword">return</span> (a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9) % (<span class="hljs-params">10</span>**<span class="hljs-params">9</span> + <span class="hljs-params">7</span>) ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的 LeetCode 題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.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>

                              哎呀哎呀视频在线观看