LeetCode 題解

279. 完全平方數 （點擊查看題目）

題目描述

給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等於 n。你需要讓組成和的完全平方數的個數最少。

示例 1 ：

<code>輸入: n = 12
輸出: 3 
解釋: 12 = 4 + 4 + 4./<code>

示例 2 ：

<code>輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9./<code>

解決方案

方法一：暴力枚舉法 [超出時間限制]

這個問題要求我們找出由完全平方數組合成給定數字的最小個數。我們將問題重新表述成：

給定一個完全平方數列表和正整數 n，求出完全平方數組合成 n 的組合，要求組合中的解擁有完全平方數的最小個數。

注：可以重複使用列表中的完全平方數。

從上面對這個問題的敘述來看，它似乎是一個組合問題，對於這個問題，一個直觀的解決方案是使用暴力枚舉法，我們枚舉所有可能的組合，並找到完全平方數的個數最小的一個。

我們可以用下面的公式來表述這個問題：

從上面的公式中，我們可以將其轉換為遞歸解決方案。這裡有一個例子。

算法：

Python 實現

<code>class Solution(object):
    def numSquares(self, n):
        square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)]

        def minNumSquares(k):
            """ recursive solution """
            # bottom cases: find a square number
            if k in square_nums:
                return 1
            min_num = float('inf')

            # Find the minimal value among all possible solutions
            for square in square_nums:
                if k < square:
                    break
                new_num = minNumSquares(k-square) + 1
                min_num = min(min_num, new_num)
            return min_num

        return minNumSquares(n)/<code>

上面的解決方案可以適用於較小的正整數 n。然而，會發現對於中等大小的數字（例如 55），我們也會很快遇到超出時間限制的問題。

簡單的說，可能會由於過度遞歸，產生堆棧溢出。

方法二：動態規劃

使用暴力枚舉法會超出時間限制的原因很簡單，因為我們重複的計算了中間解。我們以前的公式仍然是有效的。我們只需要一個更好的方法實現這個公式。

你可能注意到從公式看來，這個問題和斐波那契數問題類似。和斐波那契數一樣，我們由幾種更有效的方法來計算解，而不是簡單的遞歸。

解決遞歸中堆棧溢出的問題的一個思路就是使用動態規劃（DP）技術，該技術建立在重用中間解的結果來計算終解的思想之上。

要計算

的值，首先要計算 n 之前的所有值，即

如果我們已經在某個地方保留了數字 n - k 的解，那麼就不需要使用遞歸計算。

算法：

基於上述所說，我麼可以在以下步驟實現 DP 解決方案。

• 幾乎所有的動態規劃解決方案，首先會創建一個一維或多維數組 DP 來保存中間子解的值，以及通常數組最後一個值代表最終解。注意，我們創建了一個虛構的元素 dp[0]=0 來簡化邏輯，這有助於在在餘數 (n-k）恰好是一個完全平方數的情況下。
• 我們還需要預計算小於給定數字 n 的完全平方數列表（即 square_nums）。
• 在主要步驟中，我們從數字 1 循環到 n，計算每個數字 i 的解（即 numSquares(i)）。每次迭代中，我們將 numSquares(i) 的結果保存在 dp[i] 中。
• 在循環結束時，我們返回數組中的最後一個元素作為解決方案的結果。
• 在下圖中，我們演示瞭如何計算與 dp[4] 和 dp[5] 相對應的 numSquares(4) 和 numSquares(5) 的結果。

下面是示例實現，其中 Python 解決方案花費了約 3500 ms，這比當時 50% 的提交要快。

注意：以下 Python 解決方案僅適用於 Python2。出於某種未知的原因，Python3 運行相同的代碼需要更長的時間。

Python 實現

<code>class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        dp = [float('inf')] * (n+1)
        # bottom case
        dp[0] = 0
        
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i-square] + 1)
        
        return dp[-1]/<code>

Java 實現

<code>class Solution {

  public int numSquares(int n) {
    int dp[] = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    // bottom case
    dp[0] = 0;

    // pre-calculate the square numbers. 

    int max_square_index = (int) Math.sqrt(n) + 1;
    int square_nums[] = new int[max_square_index];
    for (int i = 1; i < max_square_index; ++i) {
      square_nums[i] = i * i;
    }

    for (int i = 1; i <= n; ++i) {
      for (int s = 1; s < max_square_index; ++s) {
        if (i < square_nums[s])
          break;
        dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
      }
    }
    return dp[n];
  }
}/<code>

複雜度分析

• 時間複雜度：

在主步驟中，我們有一個嵌套循環，其中外部循環是 n 次迭代，而內部循環最多需要

迭代。

• 空間複雜度：O(n)，使用了一個一維數組 dp。

方法三：貪心枚舉

遞歸解決方法為我們理解問題提供了簡潔直觀的方法。我們仍然可以用遞歸解決這個問題。為了改進上述暴力枚舉解決方案，我們可以在遞歸中加入貪心。我們可以將枚舉重新格式化如下：

從一個數字到多個數字的組合開始，一旦我們找到一個可以組合成給定數字 n 的組合。

那麼我們可以說我們找到了最小的組合，因為我們貪心的從小到大的枚舉組合。

為了更好的解釋，我們首先定義一個名為 is_divided_by(n, count) 的函數，該函數返回一個布爾值，表示數字 n是否可以被一個數字 count 組合，而不是像前面函數 numSquares(n) 返回組合的確切大小。

與遞歸函數 numSquare(n) 不同，is_divided_by(n, count) 的遞歸過程可以歸結為底部情況（即 count==1）更快。

下面是一個關於函數 is_divided_by(n, count) 的例子，它對 輸入 n=5 和 count=2 進行了分解。

通過這種重新構造的技巧，我們可以顯著降低堆棧溢出的風險。

算法：

• 首先，我們準備一個小於給定數字 n 的完全平方數列表（稱為 square_nums）。
• 在主循環中，將組合的大小（稱為 count）從 1 迭代到 n，我們檢查數字 n 是否可以除以組合的和，即 is_divided_by(n, count)。
• 函數 is_divided_by(n, count) 可以用遞歸的形式實現，汝上面所說。
• 在最下面的例子中，我們有 count==1，我們只需檢查數字 n 是否本身是一個完全平方數。可以在 square_nums 中檢查，即

如果 square_nums 使用的是集合數據結構，我們可以獲得比 n == int(sqrt(n)) ^ 2 更快的運行時間。

關於算法的正確性，通常情況下，我們可以用反證法來證明貪心算法。這也不例外。假設我們發現 count=m 可以除以 n，並且假設在以後的迭代中存在另一個 count=p 也可以除以 n，並且這個數的組合小於找到的數，即 p

下面是一些示例實現。Python 解決方案需要大約 70ms，這比當時大約 90% 的提交要快。

Python 實現

<code>class Solution:
    def numSquares(self, n):
        
        def is_divided_by(n, count):
            """
                return: true if "n" can be decomposed into "count" number of perfect square numbers.
                e.g. n=12, count=3:  true.
                     n=12, count=2:  false
            """
            if count == 1:
                return n in square_nums
            
            for k in square_nums:
                if is_divided_by(n - k, count - 1):
                    return True
            return False

        square_nums = set([i * i for i in range(1, int(n**0.5)+1)])
    
        for count in range(1, n+1):
            if is_divided_by(n, count):
                return count/<code>

Java 實現

<code>class Solution {
  Set<integer> square_nums = new HashSet<integer>(); 


  protected boolean is_divided_by(int n, int count) {
    if (count == 1) {
      return square_nums.contains(n);
    }

    for (Integer square : square_nums) {
      if (is_divided_by(n - square, count - 1)) {
        return true;
      }
    }
    return false;
  }

  public int numSquares(int n) {
    this.square_nums.clear();

    for (int i = 1; i * i <= n; ++i) {
      this.square_nums.add(i * i);
    }

    int count = 1;
    for (; count <= n; ++count) {
      if (is_divided_by(n, count))
        return count;
    }
    return count;
  }
}/<integer>/<integer>/<code>

複雜度分析

• 時間複雜度：

其中 h 是可能發生的最大遞歸次數。你可能會注意到，上面的公式實際上類似於計算完整 N 元數種結點數的公式。事實上，算法種的遞歸調用軌跡形成一個 N 元樹，其中 N 是 square_nums種的完全平方數個數。即，在最壞的情況下，我們可能要遍歷整棵樹才能找到最終解。

• 空間複雜度：

我們存儲了一個列表 square_nums，我們還需要額外的空間用於遞歸調用堆棧。但正如我們所瞭解的那樣，調用軌跡的大小不會超過 4。

方法四：貪心 + BFS（廣度優先搜索）

正如上述貪心算法的複雜性分析種提到的，調用堆棧的軌跡形成一顆 N 元樹，其中每個結點代表 is_divided_by(n, count) 函數的調用。基於上述想法，我們可以把原來的問題重新表述如下：

給定一個 N 元樹，其中每個節點表示數字 n 的餘數減去一個完全平方數的組合，我們的任務是在樹中找到一個節點，該節點滿足兩個條件：

(1) 節點的值（即餘數）也是一個完全平方數。

(2) 在滿足條件（1）的所有節點中，節點和根之間的距離應該最小。

下面是這棵樹的樣子。

在前面的方法 3 中，由於我們執行調用的貪心策略，我們實際上是從上到下逐層構造 N 元樹。我們以 BFS（廣度優先搜索）的方式遍歷它。在 N 元樹的每一級，我們都在枚舉相同大小的組合。

遍歷的順序是 BFS，而不是 DFS（深度優先搜索），這是因為在用盡固定數量的完全平方數分解數字 n 的所有可能性之前，我們不會探索任何需要更多元素的潛在組合。

算法：

注意：在典型的 BFS 算法中，queue 變量通常是數組或列表類型。但是，這裡我們使用 set 類型，以消除同一級別中的剩餘項的冗餘。事實證明，這個小技巧甚至可以增加 5 倍的運行加速。

在下圖中，我們以 numSquares(7) 為例說明隊列的佈局。

Python 實現

<code>class Solution:
    def numSquares(self, n):

        # list of square numbers that are less than `n`
        square_nums = [i * i for i in range(1, int(n**0.5)+1)]
    
        level = 0
        queue = {n}
        while queue:
            level += 1
            #! Important: use set() instead of list() to eliminate the redundancy,
            # which would even provide a 5-times speedup, 200ms vs. 1000ms. 

            next_queue = set()
            # construct the queue for the next level
            for remainder in queue:
                for square_num in square_nums:    
                    if remainder == square_num:
                        return level  # find the node!
                    elif remainder < square_num:
                        break
                    else:
                        next_queue.add(remainder - square_num)
            queue = next_queue
        return level/<code>

Java 實現

<code>class Solution {
  public int numSquares(int n) {

    ArrayList<integer> square_nums = new ArrayList<integer>();
    for (int i = 1; i * i <= n; ++i) {
      square_nums.add(i * i);
    }

    Set<integer> queue = new HashSet<integer>();
    queue.add(n);

    int level = 0;
    while (queue.size() > 0) {
      level += 1;
      Set<integer> next_queue = new HashSet<integer>();

      for (Integer remainder : queue) {
        for (Integer square : square_nums) {
          if (remainder.equals(square)) {
            return level;
          } else if (remainder < square) {
            break;
          } else {
            next_queue.add(remainder - square);
          }
        }
      }
      queue = next_queue;
    }
    return level;
  }
}/<integer>/<integer>/<integer>/<integer>/<integer>/<integer>/<code>

複雜度分析

時間複雜度：

其中 h 是 N 元樹的高度。在前面的方法三我們可以看到詳細解釋。

空間複雜度：

這也是在 h 級可以出現的最大節點數。可以看到，雖然我們保留了一個完全平方數列表，但是空間的主要消耗是隊列變量，它跟蹤給定 N 元樹級別上要訪問的剩餘節點。

方法五：數學運算

隨著時間的推移，已經提出並證明的數學定理可以解決這個問題。在這一節中，我們將把這個問題分成幾個例子。

1770 年，Joseph Louis Lagrange證明了一個定理，稱為四平方和定理，也稱為 Bachet 猜想，它指出每個自然數都可以表示為四個整數平方和：

其中 a0,a1,a2,a3 表示整數。

例如，3，31 可以被表示為四平方和如下：

情況 1：拉格朗日四平方定理設置了問題結果的上界，即如果數 n 不能分解為較少的完全平方數，則至少可以分解為 4 個完全平方數之和，即

正如我們在上面的例子中可能注意到的，數字 0 也被認為是一個完全平方數，因此我們可以認為數字 3 可以分解為 3 個或 4 個完全平方數。

然而，拉格朗日四平方定理並沒有直接告訴我們用最小平方數來分解自然數。

後來，在 1797 年，Adrien Marie Legendre用他的三平方定理完成了四平方定理，證明了正整數可以表示為三個平方和的一個特殊條件：

其中 k 和 m 是整數。

情況 2：與四平方定理不同，Adrien-Marie-Legendre 的三平方定理給了我們一個充分必要的條件來檢驗這個數是否只能分解成 4 個平方。

從三平方定理看我們在第 2 種情況下得出的結論可能很難。讓我們詳細說明一下推論過程。

首先，三平方定理告訴我們，如果 n 的形式是

那麼 n 不能分解為 3 個平方的和。此外，我們還可以斷言 n 不能分解為兩個平方和，數本身也不是完全平方數。因為假設數 n 可以分解為

然後通過在表達式中添加平方數 0，即

我們得到了數 n 可以分解為 3 個平方的結論，這與三平方定理相矛盾。因此，結合四平方定理，我們可以斷言，如果這個數不滿足三平方定理的條件，它只能分解成四個平方和。

如果這個數滿足三平方定理的條件，則可以分解成三個完全平方數。但我們不知道的是，如果這個數可以分解成更少的完全平方數，即一個或兩個完全平方數。

所以在我們把這個數視為底部情況（三平方定理）之前，還有兩種情況需要檢查，即：

情況 3.1：如果數字本身是一個完全平方數，這很容易檢查，例如 n == int(sqrt(n)) ^ 2。

情況 3.2：如果這個數可以分解成兩個完全平方數和。不幸的是，沒有任何數學定理可以幫助我們檢查這個情況。我們需要使用枚舉方法。

算法：

可以按照上面的例子來實現解決方案。

• 首先，我們檢查數字 n 的形式是否為

如果是，則直接返回 4。

<code>class Solution:
    def isSquare(self, n: int) -> bool:
        sq = int(math.sqrt(n))
        return sq*sq == n

    def numSquares(self, n: int) -> int:
        # four-square and three-square theorems
        while (n & 3) == 0:
            n >>= 2      # reducing the 4^k factor from number
        if (n & 7) == 7: # mod 8
            return 4

        if self.isSquare(n):
            return 1
        # check if the number can be decomposed into sum of two squares
        for i in range(1, int(n**(0.5)) + 1):
            if self.isSquare(n - i*i):
                return 2
        # bottom case from the three-square theorem
        return 3/<code>

Java 實現

<code>class Solution {

  protected boolean isSquare(int n) {
    int sq = (int) Math.sqrt(n);
    return n == sq * sq;
  }

  public int numSquares(int n) {
    // four-square and three-square theorems.
    while (n % 4 == 0)
      n /= 4;
    if (n % 8 == 7)
      return 4;

    if (this.isSquare(n))
      return 1;
    // enumeration to check if the number can be decomposed into sum of two squares.
    for (int i = 1; i * i <= n; ++i) {
      if (this.isSquare(n - i * i))
        return 2;
    } 

    // bottom case of three-square theorem.
    return 3;
  }
}/<code>

複雜度分析

時間複雜度：

在主循環中，我們檢查數字是否可以分解為兩個平方和，這需要

個迭代。在其他情況下，我們會在常數時間內進行檢查。

空間複雜度：O(1)，該算法消耗一個常量空間。

閱讀更多 力扣LeetCode 的文章

關鍵字: 算法 Python 題解