leetcode 50. Pow(x, n)-细说边界问题 - lovechara - 博客频道 - CSDN.NET

leetcode 50. Pow(x, n)-细说边界问题 - lovechara - 博客频道 - CSDN.NET

【思路1-Java】递归实现

采用递归实现，那么本题的终止条件是 n == 0 和 n == 1。这里不采用下面的做法：

public class Solution {     public double myPow(double x, int n) {         if(n == 0) return 1;         if(n == 1) return x;         return myPow(x, n-1) * x;     } }

因为时间复杂度为 O(n)，加上题目的限制会超时。但同时我们也不采用下面的做法：

public class Solution {     public double myPow(double x, int n) {         if(n == 0) return 1;         if(n == 1) return x;         return myPow(x, n / 2) * myPow(x, n / 2);     } }

时间复杂度真的下降为 O(logn)了吗？非也，由于递归的特性——无法记录下中间结果， myPow(x, n / 2) 被计算了两次，因此复杂度为 O(log(2^n)) = O(n)，也会超时。
我们最好用一个值两记录下中间变量，充分利用好中间结果，克服这种毛病。

另外，本题的难点主要是在边界条件：如果 n < 0，是不是 n = -n， x = 1 / x ，再进行递归就能解决了呢？如果 n = Intege.MIN_VALUE，n = -n 会出现溢出，怎么办呢？我们可以先将 n / 2 赋值给 t，再将 t = -n，就不会出现溢出问题。

public class Solution { 

Read full article from leetcode 50. Pow(x, n)-细说边界问题 - lovechara - 博客频道 - CSDN.NET