当前位置 博文首页 > WLSK801的博客：[leetCode刷题笔记]2017.03.30
50. Pow(x, n)
这道题要用递归，但是递归不能用一个个减，因为这样要是碰到很大的n的情况会有stack overflow error。所以要利用平方，一次变成n / 2。
public class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
double powV = myPow(x, n / 2);
if (n % 2 != 0) {
if (n > 0) {
return x * powV * powV;
}
else {
return powV * powV / x;
}
}
else {
return powV * powV;
}
}
}这道题也是用二分法。注意边界条件，还有要防止输入一个很大的数，所以要用long形式。
public class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
return (int)find(x, 0, x);
}
private long find(long x, long lo ,long hi) {
if (lo == hi) {
return hi - 1;
}
long mid = lo + (hi - lo) / 2;
if (mid * mid > x) {
return find(x, lo, mid);
}
else if (mid * mid < x){
return find(x, mid + 1, hi);
}
else {
return mid;
}
}
}275. H-Index II
二分法轻松·搞定
public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int lo = 0;
int hi = len - 1;
while (lo <= hi) {
int mid = (hi + lo) / 2;
if (citations[mid] == len - mid) {
return len - mid;
}
else if (citations[mid] < len - mid) {
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return len - lo;
}
}