Description: Implement pow(x,?n).
分析: 求冪次運算,典型的分治算法來解。 因為pow(x,n/2)*pow(x,n/2) 有著重復運算,分治法就會非常快O(log n)
1 class Solution { 2 public: 3 double findval(double x,int n) 4 { 5 if(n==0) return 1; 6 if(n==1) return x; 7 double value = pow(x,n/2); 8 if(n%2) return value*value*x; 9 else return value*value; 10 } 11 double pow(double x, int n) { 12 bool flag = false; 13 if(n<0) 14 { 15 n=-n; 16 flag = true; 17 } 18 double value = findval(x,n); 19 if(flag) return 1/value; 20 else return value; 21 22 } 23 };
LeetCode、?