資訊專欄INFORMATION COLUMN
摘要：題目要求判斷一個數(shù)字最少由幾個平方數(shù)的和構(gòu)成。思路一暴力遞歸要想知道什么樣的組合最好，暴力比較所有的結(jié)果就好啦。當(dāng)然，效率奇差。代碼如下思路三數(shù)學(xué)統(tǒng)治一切這里涉及了一個叫做四平方定理的內(nèi)容。有興趣的可以去了解一下這個定理。
題目要求
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
判斷一個數(shù)字最少由幾個平方數(shù)的和構(gòu)成。比如12=9+1+1+1=4+4+4，那么最少的數(shù)量為3。
思路一：暴力遞歸要想知道什么樣的組合最好，暴力比較所有的結(jié)果就好啦。當(dāng)然，效率奇差。
public int numSquares(int n) {
if(n==0) return 0;
if(n==1) return 1;
int sqrt = (int) Math.floor(Math.sqrt(n));
int count = Integer.MAX_VALUE;
while(sqrt>0){
int tmpCount = 0;
int copy = n;
do{
copy -= sqrt * sqrt;
tmpCount++;
}while(copy > sqrt * sqrt);
count = Math.min(count, tmpCount+numSquares(copy));
sqrt--;
}
return count;
}
思路二：動態(tài)規(guī)劃
我們可以用另一種思路來拆解n：
比如：
numSquares(1) = 1;
numSquares(2) = numSquares(1)+1
numSquares(3) = numSquares(3-1*1) + 1
numSquares(4) = 1
numSquares(5) = min(numSquares(5-1*1)+1, numSquares(5-2*2)+1)
numSquares(10) = min(numSquares(10-1*1)+1, numSquares(10-2*2)+1, numSquares(10-3*3)+1)
這樣我們就可以省去許多重復(fù)的計算。
代碼如下：
public int numSquares_dp(int n){
if(n<=1) return n;
int[] min = new int[n+1];
min[1] = 1;
for(int i = 2 ; i<=n ; i++){
int sqrt = (int)Math.floor(Math.sqrt(i));
int tempMin = Integer.MAX_VALUE;
while(sqrt-->0){
tempMin = Math.min(tempMin, min[n-sqrt*sqrt]);
sqrt--;
}
min[i] = tempMin;
}
return min[n];
}
思路三：數(shù)學(xué)統(tǒng)治一切
這里涉及了一個叫做四平方定理的內(nèi)容。有興趣的可以去了解一下這個定理?？傊褪墙o了一個一般規(guī)律，這里貼上代碼：
public int numSquares_math(int n){
if(isSquare(n)) return 1;
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}
// Check whether 2 is the result.
int sqrt_n = (int)(Math.sqrt(n));
for(int i = 1; i <= sqrt_n; i++)
{
if (isSquare(n - i*i))
{
return 2;
}
}
return 3;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68549.html
Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Exampl...
摘要：題目給一個正整數(shù)問他最少能被幾個完全平方數(shù)和表示。舉例，返回，返回解法我能看懂的就只有的方法，原理如下代碼 題目： 給一個正整數(shù)n,問他最少能被幾個完全平方數(shù)和表示。 舉例： 13=4+9， 返回2；12 = 4+4+4， 返回3； 解法： 我能看懂的就只有dynamic-programming的方法，原理如下： dp[0] = 0 dp[1] = dp[0]+1 = 1 dp[2...
摘要：動態(tài)規(guī)劃復(fù)雜度時間空間思路如果一個數(shù)可以表示為一個任意數(shù)加上一個平方數(shù)，也就是，那么能組成這個數(shù)最少的平方數(shù)個數(shù)，就是能組成最少的平方數(shù)個數(shù)加上因為已經(jīng)是平方數(shù)了。 Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4...
摘要：動態(tài)規(guī)劃法建立空數(shù)組從到每個數(shù)包含最少平方數(shù)情況，先所有值為將到范圍內(nèi)所有平方數(shù)的值賦兩次循環(huán)更新，當(dāng)它本身為平方數(shù)時，簡化動態(tài)規(guī)劃法四平方和定理法 Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) whi...
閱讀 1751·2023-04-25 23:43
閱讀 932·2021-11-24 09:39
閱讀 731·2021-11-22 15:25
閱讀 1729·2021-11-22 12:08
閱讀 1099·2021-11-18 10:07
閱讀 2083·2021-09-23 11:22
閱讀 3355·2021-09-22 15:23
閱讀 2513·2021-09-13 10:32
