[LeetCode]Pow(x,n)

题目链接

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

	class Solution {
	public:
	double myPow(double x, int n) {
	if(!n)return 1;
	if(n == 1)return x;
	long pow = n;
	pow = abs(pow);
	double half = myPow(x, pow / 2), res = half * half;
	if(pow % 2)res *= x;
	return n < 0? 1 / res: res;
	}
	};

view raw Pow(x, n).cpp hosted with ❤ by GitHub

后来还看了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每一位，代码如下：

	class Solution {
	public:
	double myPow(double x, int n) {
	if(!x)return x;
	if(!n)return 1;
	long pow = n;
	pow = abs(pow);
	if(n < 0)x = 1 / x;
	double res = 1;
	//n = k0 * 2^0 + k1 * 2^1 + ... + ki * 2^i (kj == 0/1)
	//res = x^(k0 * 2^0) * x^(k1 * 2^1) * ... * x^(ki * 2^i)
	while(pow)
	{
	if(pow & 1)res *= x;
	x *= x;
	pow >>= 1;
	}
	return res;
	}
	};

view raw Pow(x, n)_2.cpp hosted with ❤ by GitHub