每天一道高頻題:pow(x,n)

說明：-100.0<x<100.0，n是32位有符號整數，其數值範圍是[-2^31,2^31-1]最簡單的做法：將n個x進行相乘，時間複雜度：O(n)，空間複雜度：O(1)

1public class Pow {
2    public double myPow(double x, int n) {
3        double res = 1;
4        while (n > 0) {
5            res *= x;
6            n--;
7        }
8        return res;
9    }
10}

快速冪（分治）：時間複雜度：O(logn)，非遞歸空間複雜度：O(1)，遞歸空間複雜度：O(logn)

1public class Pow {
2    public double myPow(double x, int n) {
3        if (n == 0) return 1;
4        if (n == -1) return 1 / x;
5        double half = myPow(x, n >> 1);
6        half *= half;
7        // 是否為奇數
8        return ((n & 1) == 1) ? (half * x) : half;
9    }
10}

1public class Pow {
2    public static double myPow(double x, int n) {
3        long y = (n < 0) ? -((long) n) : n;
4        double res = 1.0;
5        while (y > 0) {
6            if ((y & 1) == 1) {
7                // 如果最後一個二進位位是1，就累乘上x
8                res *= x;
9            }
10            x *= x;
11            // 捨棄掉最後一個二進位位
12            y >>= 1;
13        }
14        return (n < 0) ? (1 / res) : res;
15    }
16}

請設計一個算法求x的y次冪模z的結果：x^y%z，假設x，y都可能是很大的整數，x>=0,y>=0,z!=0公式：(a*b)%p=((a%p)*(b%p))%p2^100 % 6 = (2^50 * 2^50) % 6 = ((2^50 % 6) * (2^50 % 6)) % 62^101 % 6 = (2^50 * 2^50 * 2) % 6 = ((2^50 % 6) * (2^50 % 6) * (2 % 6)) % 6

1public class Pow {
2    public static int powMod(int x, int y, int z) {
3        if (y < 0 || z == 0) return 0;
4        if (y == 0) return 1 % z;
5        int half = powMod(x, y >> 1, z);
6        half *= half;
7        if ((y & 1) == 0) { // 偶數
8            return half % z;
9        } else { // 奇數
10            return (half * (x % z)) % z;
11        }
12    }
13}

1public class Pow {
2    public static int powMod(int x, int y, int z) {
3        if (y < 0 || z == 0) return 0;
4        int res = 1 % z;
5        x %= z;
6        while (y > 0) {
7            if ((y & 1) == 1) {
8                // 如果最後一個二進位位是1，就累乘上x
9                res = (res * x) % z;
10            }
11            x = (x * x) % z;
12            // 捨棄掉最後一個二進位位
13            y >>= 1;
14        }
15        return res;
16    }
17}