leetcode279. 完全平方数

题目：

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
翻译：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

image.png

题解：

image.png

分析：
解题思路
解释一下 四平方定理
四平方和定理：任何正整数都可以用最多4个数的平方表示
最多确定了，那就确定1，2，3
第一，判断n是否完全平方数：int(n0.5)2==n True
第二，判断n-i*i是否完全平方数
第三，剩下的就是3了

代码如下：
class Solution:
def numSquares(self, n: int) -> int:

    while n % 4 ==0:
        n //=4
    if n % 8 == 7:
        return 4
    for i in range(n+1):
        tmp = i*i
        if tmp <= n:
            if int((n-tmp)**0.5)**2 +tmp == n:
                return 1 + (0 if tmp == 0 else 1)
        else:
            break
    return 3

作者：vigilant-7amportprg
链接：https://leetcode-cn.com/problems/perfect-squares/solution/si-ping-fang-ding-li-jie-ti-by-vigilant-flvyf/