LeetCode 0279. Perfect Squares完全平方數(shù)【Medium】【Python】【BFS】

Problem

LeetCode

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

問題

力扣

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

示例 1:

輸入: n = 12
輸出: 3 
解釋: 12 = 4 + 4 + 4.

示例 2:

輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.

思路

解法一

BFS

把每個整數(shù)都看成圖中的節(jié)點(diǎn)，如果兩個整數(shù)之差為一個平方數(shù)，表示兩點(diǎn)之間存在一條邊連通。
求最小平方數(shù)，就是求 n 到 0 的最短路徑，于是就可以用 BFS。

時間復(fù)雜度: O(n^2)
空間復(fù)雜度: O(n^2)

Python3代碼

class Solution:
    def numSquares(self, n: int) -> int:
        # solution one: BFS
        q = [(n, 0)]
        visited = [False for i in range(n + 1)]  # initialize all False
        visited[n] = True

        while any(q):  # any: if all elements are False, return False, or return True
            num, step = q.pop(0)

            i = 1
            Num = num - i ** 2
            while Num >= 0:
                if Num == 0:
                    return step + 1
                if not visited[Num]:  # not visited
                    q.append((Num, step + 1))
                    visited[Num] = True
                
                i += 1
                Num = num - i ** 2

解法二

四平方和定理

Lagrange 四平方定理：任何一個正整數(shù)都可以表示成不超過四個整數(shù)的平方之和。
于是答案只可能是：1，2，3，4。
還有一個定理：滿足四數(shù)平方和定理的數(shù) n（這里要滿足由四個數(shù)構(gòu)成，小于四個不行），必定滿足 n=(8b+7)*4^a。
于是先縮小 n。
再判斷，這個縮小后的數(shù)是否可以通過兩個平方數(shù)的和或一個平方數(shù)組成，不能的話我們返回3，能的話我們返回平方數(shù)的個數(shù)。

Python3代碼

class Solution:
    def numSquares(self, n: int) -> int:
        # solution two: Lagrange's Four-square Theorem
        while n % 4 == 0:  # reduce n
            n /= 4

        if n % 8 == 7:
            return 4

        a = 0
        while a ** 2 <= n:
            b = int((n - a ** 2) ** 0.5)
            if a ** 2 + b ** 2 == n:
                return (not not a) + (not not b)  # whether a and b are positive integers
            a += 1

        return 3

代碼地址

GitHub鏈接