[LeetCode]Pow(x,n)

题目链接

Brute force的解法O(n)大数据肯定是超时的。每次先分成n / 2，然后合并，如果是奇数就再乘以一个x。注意要把n转化为正数，这个方法才能进行，x变成1 / x即可，注意越界。时间复杂度O(log n)，空间复杂度O(log n), 代码如下：


后来还看了Code Ganker的解法，觉得是个十分不错的解法，并且可以推广到其他题目上。首先因为1，2，4....2^k....，可以表示任意的整数，所以我们可以把pow(x, n)中的n拆分成，k0 * 2^0 + k1 * 2^1 + k2 * 2^2.....，其中ki == 0或者1。所以pow(x, n)的结果为 x^(ki * 2^i)的乘积。

时间复杂度log(n)，因为我们只check每一位，代码如下：