367. 有效的完全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
思路1：
牛顿迭代法：
最快的是用一个公式：1+3+5+7+ … + (2n-1) = n^2
等差数列求和公式可得：
class Solution {
public:
bool isPerfectSquare(int num) {
int n=1;
while(num>0)
{
num-=n;
n+=2;
}
return num==0;
}
};
思路2：
二分查找的思路
class Solution {
public:
bool isPerfectSquare(int num) {
long long left = 0,right = num;
while(left<=right){
long long mid = left+(right-left)/2;
long long t=mid*mid;
if(t==num){
return true;
}else if(t<num){
left = mid+1;
}else{
right = mid-1;
}
}
return false;
}
};
279. 完全平方数
题目描述：
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
思路1：
动态规划思路：
时间复杂度O(nlogn)，空间复杂度O(n)。
dp(n)表示凑成n的完全平方数的个数，类似于背包问题，去掉一个完全平方数后的最小完全平方数的个数 再 加上1，就是整体最小完全平方数的个数；
思路清楚了，其实代码很好写，注意不要产生越界就好了；
状态方程：
dp(n) = 1 + min{
dp(n-1^2), dp(n-2^2), dp(n-3^2), dp(n-4^2), ... , dp(n-k^2) //(k为满足k^2<=n的最大的k)
}
class Solution {
public:
int numSquares(int n) {
// 初始化为大一点的数，不影响后序计算
vector<int> dp(n+1,n);
dp[0]=0;
dp[1]=1;
for(int i=2;i<n+1;i++){
int temp = n;
for(int j=1;j*j<=i;j++){
temp = min(dp[i-j*j],temp);
}
dp[i]=temp+1;
}
return dp[n];
}
};
思路2:最短路径法
这道题看起来有点像贪心算法，但是如果运用贪心算法的话 12 = 3*3 + 1*1 + 1*1，那么返回结果是4，但是实际上的返回结果是3。
转换思路，时间上这道题相当于一个图，共计有n+1个顶点，分别是从0到n这n个整数，其中两个顶点满足差值绝对值为平方数才可以连接，
最终求得的结果实际上就是n到0的最短路径。
广度优先遍历，谁先找到为tmp值为0的点，谁先返回step;
class Solution {
public:
int numSquares(int n) {
queue< pair<int,int>> q; //剩余数，步数
q.push( make_pair(n,0) );
vector<bool> visited (n ,false); //[0..n-1]是否被访问过得标志位
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
int i = 1;
//存储各种可能的节点，step数值都是统一的
while(num - i * i >= 0){
int tmp = num - i * i;
if(tmp == 0)
return step + 1;
if(tmp > 0){
// 判断是否被访问过，已经被加入过路径过
if(visited[tmp] == false){
q.push(make_pair(tmp,step + 1));
visited[tmp] = true;
}
}
i++;
}
}
return 0;
}
};
原文：https://www.cnblogs.com/Allen-rg/p/13927290.html