Math例题分析

-- Pow(x, n) 
    >> 题目：实现x的n次方
    >> 解题思路：n个x相乘，如果是n个相乘那么复杂度为O（N），如果n比较大，可以两两相乘，分治。时间复杂度logn
        ++ 功能：n为正数 0 负数
        ++ 边界：
        ++ 负面：n为负数，x为0

    public double pow(double x, int n) {
        if (x == 0.0) return x; // 底为0的特殊处理
        int newN = n > 0 ? n : (-1 * n); // 负数处理
        double result = 1.0;
        if (newN > 0) {
            // 分治
            if ((newN & 0x1) == 1) {//位运算代替取余操作
                result = pow(x, (newN - 1) / 2);
                result *= result;
                result *= x;
            } else {
                result = pow(x, newN / 2);
                result *= result;
            }
        }
        if (n < 0) {
            result = 1.0 / result;
        }
        return result;
    }

-- 打印1到最大的n位数
    >> 题目：如题
    >> 解题思路：n位数，n的范围未知，也就说可能很大，所以最简单的使用数组模拟数。进行递归或者循环。


-- Reverse Integer 
    >> 题目：Reverse Integer ， 123 -> 321   -123 -> -321
    >> 解题思路：关注溢出问题，尾部的长尾0问题，但是通过扩大范围可以解决

    public int reverse(long x) {
        long newX = x > 0 ? x : (-1 * x);
        long result = 0, temp = newX;
        while (temp != 0) {
            result = result * 10 + temp % 10;
            temp = temp / 10;
        }
        if (result > Integer.MAX_VALUE) {
            result = 0;
        }
        if (x < 0) {
            result = -1 * result;
        }

        return (int)result;
    }

-- Sqrt(x) 

    >> 题目：Sqrt(x) ，对于不能整出的需要去掉小数，最后的end刚好是这个数

    >> 解题思路：较简单的就是二分查找。

    public int sqrt(int x) {
        if (x == 1 || x == 0) return x;
        int start = 0, end = x / 2 + 1, mid = 0;
        for ( ; start <= end; ) {
            mid = start + (end - start) / 2; // 防止溢出
            if (mid < x / mid) { // 防止溢出
                start = mid + 1;
            } else if (mid > x / mid){
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return end;
    }