LeetCode 279. Perfect Squares

Posted on | In |
Words count in article: 258 | Reading time ≈ 1

题目

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:

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

Example 2:

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

思路

Lagrange 四平方和定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。

因此此问题结果只有1,2,3,4这四种可能。

推论:

满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足 n=4^a (8b+7).

首先将n迅速缩小。然后再判断这个缩小后的数是否可以通过两个平方数的和或一个平方数组成，不能的话我们返回3，能的话我们返回平方数的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        while n%4 == 0:
            n /= 4
        if n%8 == 7:
            return 4
        a = 0
        while a*a <= n:
            b = int(math.sqrt(n - a*a))
            if a*a + b*b == n:
                return (not not a) + (not not b)  
            a = a + 1
        return 3