1. 首页
  2. IT资讯

279.完全平方数

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

示例 1:

输入: n = 12 输出: 3  解释: 12 = 4 + 4 + 4. 

示例 2:

输入: n = 13 输出: 2 解释: 13 = 4 + 9. 

【中等】
【分析】BFS,利用自带你seen来记录当前应该被分解的数字,记录当前数字之前已经被分解的次数,当该数字被访问过时,不加入队列。

class Solution:     def numSquares(self, n: int) -> int:         queue=[n] # 记录当前应该被分解的数字以及在此之前已经被分解的次数         seen={n:0}         while queue:             num=queue.pop(0)                           i=1             while i<=num and num-i**2>=0:                 nums=num-i**2   #将num分解到nums                 if nums==0:                     return seen[num]+1                 if nums not in seen:                     queue.append(nums)                     seen[nums]=seen[num]+1                     i+=1 

279.完全平方数
【分析2】动态规划
定义状态和状态转移方程

class Solution:     def numSquares(self, n: int) -> int:         dp=[float("inf") for _ in range(n+1)]         dp[0]=0         for i in range(1,n+1):             j=1             while j<=i and i-j*j>=0:                 dp[i]=min(dp[i],dp[i-j*j]+1)                 j+=1         return dp[-1] 

上面的代码时间超出限制,。
改进,将上面while换成了直接在

ijj&gt;=01&lt;=j&lt;=ii-j*j&gt;=0即1&lt;=j&lt;=sqrt i

范围内直接求所有

dp[ijj]dp[i-j*j]

们的最小值:

class Solution:     dp_=[0]     def numSquares(self, n: int) -> int:         dp=self.dp_         for num in range(1,n+1):             dp+=[min(dp[num-i*i]+1 for i in range(1,int(num**0.5+1)))]         return dp[-1] 

【分析3】四平方和定理

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

if and only if n is not of the form

n=4a(8b+7)n=4^a(8b+7)

for integers a and b.

原文始发于:279.完全平方数

主题测试文章,只做测试使用。发布者:sys234,转转请注明出处:http://www.cxybcw.com/92963.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code