Pow(x, n)

原題鏈接Pow(x, n)

給定一個數，求n次方。n次方可以分解成兩個n/2次方相乘，所以遞歸即可。

class Solution { public:double myPow(double x, int n) {bool negative = n < 0;double res = helper(x, n);return negative ? 1 / res : res;} private:double helper(int x, int n){if(n == 0)return 1;if(n == 1)return x;if(n % 2){double res = helper(x, n / 2);return res * res * x;}else{double res = helper(x, n / 2);return res * res;}} };

---

Super Pow

原題鏈接Super Pow

同樣是求某個數的n次方，但是n存在數組中，如[1, 0]代表n為10。而且數組代表的n會非常大，有可能會超過int的范圍，所以直接還原n然后計算n次方的方法基本是沒戲了。
既然這樣，就只能從每位下手，有這樣一個公式

(a * b) % k = (a % k) * (b % k) % k

以數組為[1, 2, 3, 4, 5, 6, 7]為例，表示a的1234567次方，因為有

a ^ 1234567 = (a ^ 1234560) * (a ^ 7)

所以

(a ^ 1234567) % k = (((a ^ 1234560) % k) * ((a ^ 7) % k)) % k

而

(a ^ 1234560) % k = ((a ^ 123456) ^ 10) % k = (((a ^ 123456) % k) ^ 10 ) % k

所以

(a ^ 1234567) % k = (((((a ^ 123456) % k) ^ 10 ) % k) * ((a ^ 7) % k)) % k

將a ^ n % k抽象為f(a, n)函數，那么上式可以寫成

f(a, 1234567) = f(f(a, 123456), 10) * f(a, 7) % k

可以發現，每次都可以把n的最后一位去除，從而減少n，當n為1或為0時返回即可。不過注意上面的式子對于n為[0 : 10]內的數都不需要再調用f函數了，直接求就可以，也就是將外層f改為pown

f(a, 1234567) = pown(f(a, 123456), 10) * pown(a, 7) % k class Solution { public:int superPow(int a, vector<int>& b) {if(b.empty())return 1;int back = b.back();b.pop_back();return pown(superPow(a, b), 10) * pown(a, back) % base_;} private:int pown(int n, int k){/* * 因為n可能很大，這里實現取模防止在for循環result * n中溢出* 比如result為第二次for循環后的某個數，而n為INT_MAX，乘完直接溢出*/n %= base_;int result = 1;for(int i = 0; i < k; ++i)result = (result * n) % base_;return result;}const int base_ = 1337; };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----求一个数的n次方，n是很大很大的数，n用数组存储着的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。