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

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0279. 完全平方數 ## 題目地址(279. 完全平方數) <https://leetcode-cn.com/problems/perfect-squares/> ## 題目描述 ``` <pre class="calibre18">``` 給定正整數 n,找到若干個完全平方數(比如 1, 4, 9, 16, ...)使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。 示例 1: 輸入: n = 12 輸出: 3 解釋: 12 = 4 + 4 + 4. 示例 2: 輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9. ``` ``` ## 前置知識 - 遞歸 - 動態規劃 ## 公司 - 阿里 - 百度 - 字節 ## 思路 直接遞歸處理即可,但是這種暴力的解法很容易超時。如果你把遞歸的過程化成一棵樹的話(其實就是遞歸樹), 可以看出中間有很多重復的計算。 如果能將重復的計算緩存下來,說不定能夠解決時間復雜度太高的問題。 > 遞歸對內存的要求也很高, 如果數字非常大,也會面臨爆棧的風險,將遞歸轉化為循環可以解決。 遞歸 + 緩存的方式代碼如下: ``` <pre class="calibre18">``` <span class="hljs-keyword">const</span> mapper = {}; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">d</span>(<span class="hljs-params">n, level</span>) </span>{ <span class="hljs-keyword">if</span> (n === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> level; <span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> arr = []; <span class="hljs-keyword">while</span> (n - i * i >= <span class="hljs-params">0</span>) { <span class="hljs-keyword">const</span> hit = mapper[n - i * i]; <span class="hljs-keyword">if</span> (hit) { arr.push(hit + level); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">const</span> depth = d(n - i * i, level + <span class="hljs-params">1</span>) - level; mapper[n - i * i] = depth; arr.push(depth + level); } i++; } <span class="hljs-keyword">return</span> <span class="hljs-params">Math</span>.min(...arr); } <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> numSquares = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">return</span> d(n, <span class="hljs-params">0</span>); }; ``` ``` 如果使用 DP,其實本質上和遞歸 + 緩存 差不多。 DP 的代碼見代碼區。 ## 關鍵點解析 - 如果用遞歸 + 緩存, 緩存的設計很重要 我的做法是 key 就是 n,value 是以 n 為起點,到達底端的深度。 下次取出緩存的時候用當前的 level + 存的深度 就是我們想要的 level. - 使用動態規劃的核心點還是選和不選的問題 ``` <pre class="calibre18">``` <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i <= n; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j * j <= i; j++) { <span class="hljs-title">// 不選(dp[i]) 還是 選(dp[i - j * j])</span> dp[i] = <span class="hljs-params">Math</span>.min(dp[i], dp[i - j * j] + <span class="hljs-params">1</span>); } } ``` ``` ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> numSquares = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">if</span> (n <= <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; } <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(n + <span class="hljs-params">1</span>).fill(<span class="hljs-params">Number</span>.MAX_VALUE); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i <= n; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j * j <= i; j++) { <span class="hljs-title">// 不選(dp[i]) 還是 選(dp[i - j * j])</span> dp[i] = <span class="hljs-params">Math</span>.min(dp[i], dp[i - j * j] + <span class="hljs-params">1</span>); } } <span class="hljs-keyword">return</span> dp[n]; }; ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(N)O(N)O(N) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看