3.LeetCode刷题-完全平方数
本帖最后由 语欣老爹 于 2022-2-6 10:24 编辑采用每日一练的方式学习思考解题思路，探寻优化方法。
完全平方数
完全平方数有这样的特性：如果一个正整数a是某一个整数b的平方，那么这个正整数a叫做完全平方数，零也可称为完全平方数。那么： 给定正整数n，找到若干个完全平方数使得它们的和等于n。你需要确定组成和的完全平方数的最少的个数。例如：对于正整数13，其可以拆解为13 = 4 + 9，则最少个数为2。对于正整数12，其可以拆解为 12 = 4 + 4 + 4，则最少个数为3。
四平方数和定理
四平方数和定理又称拉格朗日四平方数和定理，由拉格朗日最终解决，四平方数和定理可以证明：任何正整数均可表示为四个整数的平方和(其中允许有整数为0)。
如果一个数n只能使用4个非零的完全平方数的和表示，则这个数n一定满足4a(8b+7)
解题算法
1、先假设组成这个数n的完全平方数的个数最少为4，则数n必定满足n = 4a(8b+7)，首先对这个等式进行检查，如果检查通过，则最终答案为4。否则继续算法。
2、假设假设组成这个数n的完全平方数的个数最少为1，则数n可以表示为某个正整数的平方，遍历查找。如果找不到则继续算法。
3、假设假设组成这个数n的完全平方数的个数最少为2，使用循环嵌套嵌套进行遍历查找，找不到则继续算法。
4、算法执行到此，则最终答案为3。
方案一、
def yyds(n):
num=n
while num % 4 ==0:
num = num / 4
if num % 8 ==7:
return 4
for i in range(1,n+1):
if i*i ==n:
return 1
for i in range(1,n+1):
for j in range(1,n+1):
if i * i+j*j==n:
return 2
return 3
print(yyds(12))
优化方案二、
import math
def yyds(n):
num=n
while num % 4 ==0:
num = num / 4
if num % 8 ==7:
return 4
if math.pow(int(math.sqrt(n)),2)==n:
return 1
max = int(math.sqrt(n))+1
for i in range(1,max):
tmp=n-i*i
if math.pow(int(math.sqrt(tmp)),2)==tmp:
return 2
return 3
print(yyds(13))
还有更简洁的代码吗？请贴出来
当我乐呵呵的DP过了以后，大家开始秀上了数学。。
这DP多简单啊。
第二个方案更简洁些 算法刷的头秃 谢谢，有用 有个疑问，满足 n = 4a(8b+7) 时，答案一定是 4 吗？
4*6*(8*1+7) = 324+36，我不确定是否理解对了:lol cloud2010 发表于 2022-11-16 08:31
有个疑问，满足 n = 4a(8b+7) 时，答案一定是 4 吗？
4*6*(8*1+7) = 324+36，我不确定是否理解对了
其实是4的a次方，不是4 * a。 zzzzxcv 发表于 2022-11-17 23:58
其实是4的a次方，不是4 * a。
谢谢指点:lol
页:
[1]