二分查找：第一个错误版本
题目：
?
思路：划清左右边界，算出分界线， 在某条分界线上，如果这条分界线为true，则分界线左边都是true；那么把左边界设为中线部分，因为第一个错误的地方肯定在于中线的右侧，区间为[mid,right]。如果这条分界线为false，那么错误肯定位于左边，那么把right设置为mid，第一个错误的区间肯定位于[left,mid]。
这种方式不断地缩小查询的空间：
-
时间复杂度O(log n),n为给定长度/数量
-
空间复杂度O(1),只需要保持常数空间
代码：
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);这个函数返回的是 是否错误 true就是错了
int firstBadVersion(int n) {
int left=1,right=n;
//确保区间是在1~n
while(left<right)
{
//划分中线
int mid = left + (right - left)/2;
if(isBadVersion(mid))
{
//中线已经是false了，说明false的元素位于中线的左边
right = mid;
}
else
{
//那就是前面的版本都是对的，那就把区间化为[mid+1,right]
left = mid+1;
}
}
//此刻的left=right就是第一个错误的地方
return left;
}完全平方数：发现这是一个数学问题
从数学角度：
四平方定理：任何一个正整数都可以表示成不超过四个整数的平方之和。
那先从动态规划定理开始吧：
这个题目有两个条件是平方和又是最小数。其实翻译过来就是，完全平方数为物品（无限使用），凑个正整数n就是背包，那么要凑满这个背包最少需要多少个物品？
完完全全就是背包问题了，那么就是涉及动态规划了。
需要注意的是：
-
背包容量target和物品nums的类型可能是数，也可能是字符串。
-
target可能题目已经给出（如上题），也有可能是需要我们从题目的信息中挖掘出来。
-
背包问题的分类：
0/1背包问题：每个元素最多选取一次。
完全背包问题：每个元素都可以重复选择。
组合背包问题：背包中的物品要考虑顺序。
分组背包问题：不止一个背包，需要遍历每个背包。
-
背包问题的要求：
最值：要求最大值or最小值
存在问题：是否存在...满足...
组合问题：求所有满足...的排列组合
先从动态规划解决这个问题：
-
我们可以依据题目的要求写出状态表达式：f[i]，每个下标表示需要多少个数的平方可以表示这个整数i。
-
这些数肯定是落在[1,根号n]中，那么只需要每次遍历回去f[i-j*j]即可以实现找到这个数之前的平方数。状态方程如下：我的理解的+1是为了保证下一个数比上一个数多一个1 * 1，或是这个数可以自己开完全平方，加一补回去，因为f[0]=0。
?
?
-
f[0]=0，保证j=根号i。
代码：
int numSquares(int n){
//用于存储从0到这个数的所有数字的完全平方数
int f[n+1];
//用于实现数字本身就可以开根号用
f[0] = 0;
for(int i=1;i<=n;i++)
{
//定义为int类型的最大值的数字，方便比出最小值
int minn = INT_MAX;
//递归操作，算出是否存在f[i-j*j]，如果有那么值就为上一个f值再+1，如果算出来为f[0]，则说明他本身可以自行开根号
for(int j=1;j*j<=i;j++)
{
minn = fmin(minn,f[i-j*j]);
}
//本身自行可以开根号 or 补上1*1
f[i] = minn + 1;
}
//返回对应每个数字的完全平方数
return f[n];
}?
从数学角度解决这个问题:
四平方和定理：四平方和定理_百度百科
同时四平方和定里包含了一个更强的理论：
?那按照图中的思路我们可以写出：
//判断是否为1的情况，即完全平方数
bool isPerfectSquare(int x)
{
int y = sqrt(x);
return y*y == x;
}
//判断是否能表示为4^k*(8m+7)
bool checkAnswer4(int x)
{
//判断是不是4的几次方
while(x%4==0)
{
x/=4;
}
//判断是否存在有（8m+7）这个项，如果有则返回1
return x%8==7;
}
int numSquares(int n)
{
if(isPerfectSquare(n))
{
return 1;
}
if(checkAnswer4(n))
{
return 4;
}
for(int i=1;i*i<n;i++)
{
//除了1*1是否还存在别的数字可以直接开方
int j = n - i * i;
//如果没有 那就是存在3个了
if(isPerfectSquare(j))
{
return 2;
}
}
return 3;
}害，怪自己学艺不精了T T。