LeetCode，Leetcode:Pow(x,n)

2023-11-18 阅读 31 评论 0

摘要：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 i

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 };