其他

50. Pow(x, n)

就是一个递归，顺便复习下指数运算

var myPow = function(x, n) {
    if (n === 0) {
        return 1;
    }
    if (n < 0) {
        return 1 / myPow(x, -n);
    }
    if (n % 2 === 0) {
        return myPow(x * x, n / 2);
    } else {
        return x * myPow(x, n - 1);
    }
};

69. x 的平方根

var mySqrt = function(x) {
    if (x <= 1) {
        return Math.min(x);
    }
    let result = 0;
    for (let i = 1; i * i <= x; i++) {
        if (i * i <= x) {
            result = i;
        }
    }
    return result;
};

二分法：

var mySqrt = function(x) {
    if (x <= 1) {
        return Math.min(x);
    }
    let left = 0;
    let right = Math.floor(x / 2);
    let ans;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (mid * mid <= x) {
            ans = mid;
            left = mid + 1; // 让指针真的动起来
        } else {
            right = mid - 1;
        }
    }
    return ans;
};