快速幂模拟 pow(x,n) 幂函数实现

题目链接-来源：力扣（LeetCode）

给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词指字母相同，但排列不同的字符串。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路：

常规的 n 次累乘时间复杂度为 O(n)，我们考虑对其进行优化。
容易发现，如果采用分治的方法，计算 pow(x, n) 时，只需将 pow(x, n / 2) 的结果进行平方… 即可在 O(logn) 的时间内完成计算。当然，分治过程中有许多细节要处理，比如 n 为奇数时，我们要先单独乘一次 x，让 n 变为偶数后才能继续分治。
为了高效完成分治，考虑快速幂的实现。我们将 n 视为二进制数，每次以其最低位为参考，若最低位为 1，表示当前 n 为奇数，我们就在结果中乘上 x；然后不论奇偶，我们都将 x 平方，并将 n 右移继续处理下一位，这个操作表示 n （从最低位算起的）的第 i 位，对应着我们需要计算的是 x^(2i)。
为了同一处理，n 为负数时我们将其取相反数，并将 x 取倒数即可。唯一的边界条件是 n = -2^31 的情况，没有对应的正数，我们单独处理即可。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double myPow(double x, int n) {
        double res = 1.0;
        if (n == Integer.MIN_VALUE) {
            res /= x;
            n++;
        }
        
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        
        while (n != 0) {
            if ((n & 1) == 1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}