首页 > 代码库 > 【leetcode刷题笔记】Pow(x, n)

【leetcode刷题笔记】Pow(x, n)

2024-07-13 01:50:57   218人阅读

Implement pow(x, n).

 

题解：注意两点：

  1. 普通的递归把n降为n-1会超时，要用二分的方法，每次把xn = x[n/2] * x[n/2] * xn-[n/2]*2, [n/2]表示n除以2下取整。
  2. n有可能取负数，负数的时候，先计算pow(x,-n)，然后返回1/pow(x,-n);

代码如下：

 1 public class Solution { 2     public double pow(double x, int n) { 3         if(n == 0) 4             return 1; 5         if(n == 1) 6             return x; 7          8         boolean isNeg = false; 9         10         //if n is negative,we first caculate 1/pow(x,n) = pow(x,-n)11         if(n<0){12             isNeg = true;13             n *= -1;14         }15         16         //binary17         int mid = n /2;18         int left = n - mid*2;19         double front = pow(x, mid);20         double end = pow(x, left);21         22         if(isNeg)23             return 1/(front*front*end);24         else {25             return front*front*end;26         }27     }28 }


联系
我们