leetcode 难题 Pow(x,n) 的以下 2 个解决方案之间有什么区别

Question

我正在做题为 Pow(x,n)(https://leetcode.com/problems/powx-n/) 的 LeetCode 第 50 题。它要求我 return x 的 n 次方。以下是我最初的分而治之解决方案。

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


    if(n>0)
    {
        if(n%2 == 1)
        {
            return (myPow(x,n/2)*myPow(x,n/2)*x);
        }
        else
        {
            return (myPow(x,n/2)*myPow(x,n/2));
        }
    }
    else if((n<0)&&(n>Integer.MIN_VALUE))
    {
        return (1/myPow(x,-n));
    }
    else return (1/(x*myPow(x,-n-1)));


  }
}

问题是对于一个非常大的n，这个解决方案有一个Time Limit Exceeded 问题。但是，如果我把代码改成下面这样，超时问题就解决了：

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


    if(n>0)
    {
        if(n%2 == 1)
        {
            double sub = myPow(x,n/2);
            return sub*sub*x;
        }
        else
        {
            double sub = myPow(x,n/2);
            return sub*sub;            }
    }
    else if((n<0)&&(n>Integer.MIN_VALUE))
    {
        return (1/myPow(x,-n));
    }
    else return (1/(x*myPow(x,-n-1)));


}
}

为什么给子结果赋值可以解决超时问题？有什么区别？

Answer 1

因为JVM不知道你的两个myPow(x,n/2)会做完全一样的事情，所以会计算两次。将它分配给局部变量可以消除这种惩罚，因此您的执行时间大致减半减少到 1/2^n 时间。那就不再超时了。

leetcode 难题 Pow(x,n) 的以下 2 个解决方案之间有什么区别

What is the difference between the following 2 solutions of the leetcode puzzle Pow(x,n)

java

return-value

pow