50-Pow(x，n)

50、Pow(x，n)

题目：

题解：

分治法本质刨析 （暂时并未看懂）：

https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/

​ 快速幂解法，当计算比如 pow(2, 16)时，最笨的方法是215次2，如果使用快速幂解法的思想，就是：2\2 = 2^2、2^2 * 2^2 = 2^4 、2^4 * 2^4 = 2^8、2^8 * 2^8 = 2^16。快速幂解法只需要4次运算即可得出结果。将时间复杂度降低至从 O(n)降到 O(logn)

​ 上述例子是n是偶数时，如果n是奇数时最少的运算次数就需要从x^n往前推。x^n 的n如果是偶数： x^n = x^(2/n) * x^(2/n)；如果n是奇数：x^n = x^(2/n) * x^(2/n) * x。直到推到n等于0时结束。这种解法大佬们称其为分治法，使用递归实现。

​ 这里有个小坑就是题目规定n是32位有符号整数，为了处理n是负数的情况，我在myPow中判断了一下n的正负，如果为负只需要将幂结果取个倒数即可。但测试中有一个n为INT_MIN的用例，-INT_MIN = INT_MAX + 1，因此超出了int的范围，所以需要使用一个长整型long long类型来存储，这样就可以容纳INT_MAX+1的数值了。

快速幂分治解法，从结果递归逆推，暂未学透。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? fenzhi(x, N) : 1.0 / fenzhi(x, -N);
    }
    double fenzhi(double x, long long n) {
        if(n == 0) {
            return 1.0;
        }
        double y = fenzhi(x, n/2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
};

上一篇：4、CSS语言

下一篇：49-字母异位词分组