LeetCode(279)Perfect Squares
2024-09-04 06:51:05
题目
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
分析
完美平方数,给定任意数n,它可表示为多个平方数(如1,4,9,16…)的和,求出表示出任意数n所需的平方数的最少个数。
考察动态规划,
如果一个数x可以表示为一个任意数a加上一个平方数b∗b,也就是x=a+b∗b,那么能组成这个数x最少的平方数个数,就是能组成a最少的平方数个数加上1(因为b∗b已经是平方数了)。
AC代码
class Solution {
public:
/* 如果一个数x可以表示为一个任意数a加上一个平方数bxb,也就是x = a + bxb,
* 那么能组成这个数x最少的平方数个数,就是能组成a最少的平方数个数加上1(因为b*b已经是平方数了)。
*/
int numSquares(int n) {
// 将所有非平方数的结果置最大,保证之后比较的时候不被选中
vector<int> nums(n + 1, INT_MAX);
// 将所有整平方数的结果置1
for (int i = 0; i*i <= n; ++i)
{
nums[i*i] = 1;
}//for
// 从小到大找任意数a
for (int a = 0; a <= n; ++a)
{
// 从小到大找平方数b*b
for (int b = 0; a + b*b <= n; ++b)
{
// 因为a+b*b可能本身就是平方数,所以我们要取两个中较小的
nums[a + b*b] = min(nums[a] + 1, nums[a + b*b]);
}//for
}//for
return nums[n];
}
};
最新文章
- SQL 数据库性能问题排查
- Inside Flask - flask.__init__.py 和核心组件
- winform 开发之Control.InvokeRequired
- 1038: [ZJOI2008]瞭望塔 - BZOJ
- Anti-pattern(反面模式)
- Eclipse Code Template 设置自动加注释(转)
- [HDU 1317]XYZZY[SPFA变形][最长路]
- ORACLE/MYSQL/DB2等不同数据库取前几条记录
- vb.NET基础总结
- arduino循迹小车
- intellij IDEA配置Tomcat
- property相关补充
- 逆天的 GRUB
- python 的基础 学习 第四天 基础数据类型
- Web服务器之Nginx详解(操作部分)
- vim之quickfix
- Android开发问题积累 <;加载在线Gif>;<;WebView无法加载网页图片>;
- php单例模式 (转
- 数据库SQLITE3初识
- NetCore 下集成SignalR并进行分组处理