69. Sqrt(x)

Implementint sqrt(int x).

Compute and return the square root of x.

解题方法

一次次折半去判斷

**乘積須小心溢位

    public int mySqrt(int x){
        //corner case
        if(x == 0){ return 0;}

        int start = 1;
        int end = x;
        while(start + 1 < end){
            double mid = start + (end - start) / 2;
            if(mid * mid == x && (mid + 1)*(mid + 1) > x){
                return (int)mid;
            }else if(mid * mid < x){
                start = (int)mid;
            }else{
                end = (int)mid;
            }
        }
        if(start * start <= x){
            return start;
        }
        return end;
    }

50. Pow(x, n)

Implement pow( x, n)

解题方法

一次次折半去判斷

**考慮負數 / 奇偶問題

//**********若n = -2147483648, 則反號一調換，會錯值, 需改為long

public double myPow(double x, int n) {         //**********若n = -2147483648, 則反號一調換，會錯值,  需改為long
        /*这一题主要是递归类似二分法，每次递归求n/2的结果，再乘以自己，如果是奇数再乘以一个x 注意点
        n 是负数的情况
        n 是奇数的情况*/
        if(x == 0){ return 0;}
        if(n == 0){ return 1;}

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