企业官网建设流程全解析

安国网站建设,视频网站的建设预算,本地专业app开发公司在哪里,WordPress阿里oss给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数#xff0c;其值等于另一个整数的平方#xff1b;换句话说#xff0c;其值等于一个整数自乘的积。例如#xff0c;1、4、9 和 16 都是完全平方数#xff0c;而 3 和 11 不是。 示…给你一个整数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) { /** * 这句比较难理解我们举个栗子假设n17 * 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 * resa*num的平方(a个)b能分成多少个 */ int a n /(num * num), b n % (num * num); res Math.min(res, a numSquares(b)); num ; } return res; } /** i1,result1 i2,result2 i3,result3 i4,result1 i5,result2 i6,result3 i7,result4 i8,result2 i9,result1 i10,result2 i11,result3 i12,result3 i13,result2 i14,result3 i15,result4 i16,result1 i17,result2 i18,result2 i19,result3 i20,result2 i21,result3 i22,result3 i23,result4 i24,result3 i25,result1 i26,result2 i27,result3 i28,result4 i29,result2 i30,result3 i31,result4 i32,result2 i33,result3 i34,result2 i35,result3 i36,result1 i37,result2 i38,result3 i39,result4 i40,result2 i41,result2 i42,result3 i43,result3 i44,result3 i45,result2 i46,result3 i47,result4 i48,result3 i49,result1 i50,result2 i51,result3 i52,result2 i53,result2 i54,result3 i55,result4 i56,result3 i57,result3 i58,result2 i59,result3 i60,result4 i61,result2 i62,result3 i63,result4 i64,result1 i65,result2 i66,result3 i67,result3 i68,result2 i69,result3 i70,result3 i71,result4 i72,result2 i73,result2 i74,result2 i75,result3 i76,result3 i77,result3 i78,result3 i79,result4 i80,result2 i81,result1 i82,result2 i83,result3 i84,result3 i85,result2 i86,result3 i87,result4 i88,result3 i89,result2 i90,result2 i91,result3 i92,result4 i93,result3 i94,result3 i95,result4 i96,result3 i97,result2 i98,result2 i99,result3 *总结一下规律 * (1) 不管对于什么数来说一共可以分解为4个以内 * (2) 出现一个的时候很容易求就是sqrt(n) * sqrt(n) n; * (3) n % 8 7的时候一定是4 * (4) 消去4的因子后%87一定是四个 */ /** * 根据暴力解找的规律 * param n * return */ public static int numSquares2(int n) { int rest n; /** * 消去4的因子 */ while(rest % 4 0) { rest rest / 4; } /** * 模87就是四个 */ 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则na*a b*b也就是答案为2 */ if(a * a b * b n) { return a 0 || b 0? 1 : 2; } } /** * 最多有1234四种可能性124都每返回那只能是3了 */ return 3; } }运行结果