【力扣279. 完全平方数】完全背包+数学法-四平方和定理+BFS(python3)
2021/6/28 20:25:32
本文主要是介绍【力扣279. 完全平方数】完全背包+数学法-四平方和定理+BFS(python3),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
https://leetcode-cn.com/problems/perfect-squares/
思路题解
完全背包
一开始的思路:n=6665的时候,时间超限
class Solution: def numSquares(self, n: int) -> int: if n<4:return n dp=[10001]*(n+1) dp[1],dp[2],dp[3],dp[4]=1,2,3,1 for i in range(5,n+1): if math.sqrt(i)%1!=0: for j in range(1,i//2+1): dp[i]=min(dp[i-j]+dp[i-(i-j)],dp[i]) else:dp[i]=1 return dp[n]
看了下答案, 进行了改进
class Solution: def numSquares(self, n: int) -> int: if n<4:return n dp=[i for i in range(n+1)] for i in range(2,n+1): j=1 while j*j<=i: dp[i]=min(dp[i-j*j],dp[i]) j+=1 dp[i]+=1 return dp[n]
数学法-四平方和定理
https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
BFS:层序遍历树
https://leetcode-cn.com/problems/perfect-squares/solution/shu-ju-jie-gou-he-suan-fa-bfsdong-tai-gu-jl6u/
这篇关于【力扣279. 完全平方数】完全背包+数学法-四平方和定理+BFS(python3)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python