278. First Bad Version
二分查找的思路
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while(left <= right){
int mid = (right - left) / 2 + left;
if(isBadVersion(mid)==true)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
}
279. Perfect Squares
使用動(dòng)態(tài)規(guī)劃的方法泪幌，注意 dp[0] = 0這一步分蓖。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i=0;i<=n;i++){
for(int j=1;i + j * j <= n;j++){
dp[i+j*j] = Math.min(dp[i] + 1,dp[i+j*j]);
}
}
return dp[n];
}
}
