Leetcode279:完全平方数
给你一个整数n，返回和为n的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。
示例 1：
输入：n =12输出：3解释：12 = 4 + 4 + 4
示例 2：
输入：n =13输出：2解释：13 = 4 + 9
提示：
1 <= n <= 10^4
直接上代码，实在看不懂就学会纯暴力解就行了，面试没问题的：
class Solution { /** * 纯暴力解 * @param n * @return */ public static int numSquares1(int n) { /** * 最差的情况n = 1 * 1+ 1*1 ....一共n个1*1 * 我们从2开始试，看看能不能让结果变的更小 */ int res = n, num = 2; while(num * num <= n) { /** * 这句比较难理解，我们举个栗子，假设n=17 * a = 17 / (2 * 2) = 4 b = 17 % (2 * 2) = 1 * 是不是太简单了，我们举个复杂点的例子 * 假设n = 99 * a = 99/(2*2)=24 b = 99 % (2*2)= 3 * 这里我们是想要这样一个一个结果 * n = a * (num * num) + b * res=a*num的平方(a个)+b能分成多少个 */ int a = n /(num * num), b = n % (num * num); res = Math.min(res, a + numSquares(b)); num ++; } return res; } /** i=1,result=1 i=2,result=2 i=3,result=3 i=4,result=1 i=5,result=2 i=6,result=3 i=7,result=4 i=8,result=2 i=9,result=1 i=10,result=2 i=11,result=3 i=12,result=3 i=13,result=2 i=14,result=3 i=15,result=4 i=16,result=1 i=17,result=2 i=18,result=2 i=19,result=3 i=20,result=2 i=21,result=3 i=22,result=3 i=23,result=4 i=24,result=3 i=25,result=1 i=26,result=2 i=27,result=3 i=28,result=4 i=29,result=2 i=30,result=3 i=31,result=4 i=32,result=2 i=33,result=3 i=34,result=2 i=35,result=3 i=36,result=1 i=37,result=2 i=38,result=3 i=39,result=4 i=40,result=2 i=41,result=2 i=42,result=3 i=43,result=3 i=44,result=3 i=45,result=2 i=46,result=3 i=47,result=4 i=48,result=3 i=49,result=1 i=50,result=2 i=51,result=3 i=52,result=2 i=53,result=2 i=54,result=3 i=55,result=4 i=56,result=3 i=57,result=3 i=58,result=2 i=59,result=3 i=60,result=4 i=61,result=2 i=62,result=3 i=63,result=4 i=64,result=1 i=65,result=2 i=66,result=3 i=67,result=3 i=68,result=2 i=69,result=3 i=70,result=3 i=71,result=4 i=72,result=2 i=73,result=2 i=74,result=2 i=75,result=3 i=76,result=3 i=77,result=3 i=78,result=3 i=79,result=4 i=80,result=2 i=81,result=1 i=82,result=2 i=83,result=3 i=84,result=3 i=85,result=2 i=86,result=3 i=87,result=4 i=88,result=3 i=89,result=2 i=90,result=2 i=91,result=3 i=92,result=4 i=93,result=3 i=94,result=3 i=95,result=4 i=96,result=3 i=97,result=2 i=98,result=2 i=99,result=3 *总结一下规律， * (1) 不管对于什么数来说，一共可以分解为4个以内 * (2) 出现一个的时候很容易求，就是sqrt(n) * sqrt(n) = n; * (3) n % 8 == 7的时候一定是4 * (4) 消去4的因子后%8==7一定是四个 */ /** * 根据暴力解找的规律 * @param n * @return */ public static int numSquares2(int n) { int rest = n; /** * 消去4的因子 */ while(rest % 4 == 0) { rest = rest / 4; } /** * 模8==7就是四个 */ if(rest % 8 == 7) { return 4; } /** * 如果刚好是某个数的平方，是1个 */ int f = (int)Math.sqrt(n); if(f * f == n) { return 1; } /** * 如果上面两种都不是，就肯定是2或者3，尝试一下 * 先设置为最大3 */ int res = 3; for(int first = 1; first * first <= n; first ++) { int left = n - first * first; int sqrtLeft = (int)Math.sqrt(left); if(sqrtLeft * sqrtLeft == left) { res = 2; break; } } return res; } /** * 数学解：四平方和定理 * @param n * @return */ public static int numSquares(int n) { /** * 规律4，消除4的因子 */ while (n % 4 == 0) { n = n / 4; } if(n % 8 == 7) { return 4; } for(int a = 0; a * a <= n; a++) { /** * b是剩余部分的平方根 */ int b = (int)Math.sqrt(n - a * a); /** * 如果两个数的平方和等于n，分为两种情况 * 1.如果a和b某一个为0，则另外一个数的平方等于n，这种的答案是1 * 2.如果a和b都不为0，则n=a*a + b*b也就是答案为2 */ if(a * a + b * b == n) { return a == 0 || b == 0? 1 : 2; } } /** * 最多有1，2，3，4四种可能性，1，2，4都每返回，那只能是3了 */ return 3; } }运行结果：