Description
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.
Solutions
题意很简明,找到加和为 n 的最小个数的完全平方数,如 1,4,6,16 等。
1. DP
面试中遇到过的题目,当场只给出了思路,还不对,要继续加油啊!查看了下前辈的思路,用动规来做,我们定义 dp[i] 为整数 i 最少能分解成多少个正整数的平方和:
dp[i + j * j] = min(dp[i + j * j], dp[i] + 1)
参考下得到这样的结果,也是对照之后才写出来的,还得注意:
# Time: O(n^2)
# Space: O(n)
class Solution:
def numSquares(self, n: int) -> int:
if n <= 0 :
return 0
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n+1):
j = 1
while j * j <= n:
dp[i] = min(dp[i], dp[i - j * j] + 1)
j += 1
return dp[n]
之前 DP 这种解法还行,现在可能改了测试样例,会超时。要先计算得到所有的平方数:
class Solution:
def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(0, int(n ** 0.5)+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]
# 588/588 cases passed (4584 ms)
# Your runtime beats 36.9 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)
2. 四平方定理
参考 submit 的结果看到原来有四平方定理:
class Solution:
def numSquares(self, n: int) -> int:
'''
思路:四平方定理(任何一个整数都可以表示成四个数的平方和)
1.由于一个数如果含有因子4,那么我们可以把4都去掉,并不影响结果
2.等于4的情况:如果一个数除以8余7的话,那么肯定是由4个完全平方数组成
3.等于2或者1的情况:如果一个数由2个平方数组成,如果其中一个平方数是0,那么就是1,如果不是0,那就是2。
4.等于3的情况:其他
'''
if n <= 0:
return 1
while n % 4 == 0:
n = n / 4
# 等于4的情况
if n % 8 == 7:
return 4
i = 0
while i * i <= n:
j = int((n - i * i) ** 0.5)
if i * i + j * j == n:
if i == 0 or j == 0:
return 1
else:
return 2
i = i + 1
return 3
# 588/588 cases passed (28 ms)
# Your runtime beats 99.54 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)