Power, Sqrt

MyPow(x, n)

思路

最简单的想法就是用一个for-loop，把x乘以n遍。

在主函数里面处理正负问题，在子函数里面处奇偶问题。

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0) {
            return 1 / helper(x, -n);
        } else {
            return helper(x, n);
        }
    }

    public double helper(double x, int n) {
        if(n == 0) {
            return 1.0;
        }
        if(n == 1) {
            return x;
        }

        double num = helper(x, n / 2);

        if(n % 2 == 0) {
            return num * num;
        } else {
            return num * num * x;
        }
    }
}

Iterative的做法

// problem : when n = min_value, will have problem.
public class Solution {
    public double myPow(double x, int n) {
        if(n < 0) {
            n = -n;
            x = 1 / x;
        } else if(n == 0) {
            return 1;
        } 

        double res = 1;
        while(n > 0) {
            // when n is odd
            if((n & 1) == 1) {
                res *= x;
            }

            x *= x;
            n >>= 1;
        }       
        return res;
    }
}

69. Sqrt(x)

题意：从小于x的数中找出两个数的积是 x。 left = 1, right = x / 2 + 1.

方法：二分查找法。通过定左右界的方法，每次砍掉不满足条件的一半，直到这两个界相遇。