网站建设合同的注意事项,阿里云的网站空间,山东网站建设哪里好,建设网站的行业现状题目链接
完全平方数
题目描述 注意点
返回 和为 n 的完全平方数的最少数量
解答思路
初始想到使用动态规划#xff0c;后续数字的完全平方数可以由前面数字的完全平方数求得#xff0c;对于任意数字#xff0c;可以计算其减去从1…i之间#xff08;保证做减操作后的值…题目链接
完全平方数
题目描述 注意点
返回 和为 n 的完全平方数的最少数量
解答思路
初始想到使用动态规划后续数字的完全平方数可以由前面数字的完全平方数求得对于任意数字可以计算其减去从1…i之间保证做减操作后的值大于等于0的一个平方数得到其前面数字的完全平方数再加1个1…i之间的平方数就可求得该数字的完全平方数公式如下 f(n) f(n - i²) 1还有一种数学方法可以以更快计算出结果一个数学定理可以帮助解决本题「四平方和定理」四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界最终结果只有4种也就是1、2、3、4当此时n可以直接表示为某个数i的平方此时答案为1当此时n减去某个数i的平方后的数字k可以直接表示为另一个数j的平方公式为f(n) f(n - i²) 1其中f(n - i²) j²此时答案为2答案为3时毕竟难以判断可以通过排除另外三种情况得到答案3四平方和定理包含了一个更强的结论当且仅当n Math.pow(4, k) * (8m 7)时n 只能被表示为四个正整数的平方和。此时答案为 4
代码
方法一
// 动态规划
class Solution {public int numSquares(int n) {int[] dp new int[n 1];for (int i 1; i n; i) {int minNum Integer.MAX_VALUE;int sqNum 1;while (sqNum * sqNum i) {minNum Math.min(minNum, dp[i - sqNum * sqNum] 1);sqNum;}dp[i] minNum;}return dp[n];}
}方法二
// 数学方法
class Solution {public int numSquares(int n) {if (isPerfectSquare(n)) {return 1;}if (checkAnswer4(n)) {return 4;}for (int i 1; i * i n; i) {int j n - i * i;if (isPerfectSquare(j)) {return 2;}}return 3;}// 判断是否为完全平方数public boolean isPerfectSquare(int x) {int y (int) Math.sqrt(x);return y * y x;}// 判断是否能表示为 4^k*(8m7)public boolean checkAnswer4(int x) {while (x % 4 0) {x / 4;}return x % 8 7;}
}关键点
动态规划的思想了解四平方和定理学习数学方法了解哪些情况对应四种答案
