需要帮助理解解决方案

Question

我是 DSA 的初学者。我正在使用 java 来练习 DSA。最近我尝试解决leetcode上的一个中等水平的问题，当我的解决方案超出时间限制时，我查看了其他人的解决方案。但是我无法理解这个解决方案的一部分。

leetcode 第 50 题）Pow(x,n)

问题陈述：

实现 pow(x, n)，计算 x 的 n 次方（即 xn）。

示例1：

输入：x = 2.00000，n = 10 输出：1024.00000

示例2：

输入：x = 2.10000，n = 3 输出：9.26100

示例3：

输入：x = 2.00000，n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25

限制：

-100.0< x < 100.0 -231 <= n <= 231-1 n is an integer. Either x is not zero or n >0。 -104<= xn <= 104

解决方案代码（提交成功）：

class Solution 
 {
     public double myPow(double x, int n) 
     {
            //edge case
            if(x == 1 || n == 0)
                return 1;
            if(x == 0) 
                return 0;
            if(x == -1) 
                if (n % 2 == 0)
                    return 1 ;
                else
                    return -1 ;
            if(n == 1) 
                return x;
            
            // use long as -Neg max change to Pos max will overflow
            long N = n;
            if(N < 0) 
            {
                N = -N;
                x = 1/x;
            }
            return p(x, N); 
        }
        
        // for loop solution
    double p(double x, long n) 
        {
        double resisual = 1;
        for(long i = n; i > 1; i = i/2)
            {
        if(i%2 == 1)
                {
                    resisual = resisual * x;
                } 
                x = x * x;
        }
            return resisual*x;
    }
}

我能理解

public double myPow(double x, int n)

函数里面的代码。但无法理解后一个函数 double p(double x,long n) :

// for loop solution
    double p(double x, long n) 
        {
        double resisual = 1;
        for(long i = n; i > 1; i = i/2)
            {
        if(i%2 == 1)
                {
                    resisual = resisual * x;
                } 
                x = x * x;
        }
            return resisual*x;
    }

我的疑问是：

1. double resisual = 1;

   到底是用来做什么的？
2. 在 for 循环中为什么使用 i=i/2 以及它如何不会导致计算中的逻辑错误？
3. 为什么使用这个代码片段？

if(i%2 == 1)
{
    resisual = resisual * x;
} 

4. x = x * x

   - 为什么 x 值每次都会改变，而不是像 ans=ans*x 这样的东西？
5. 我们为什么要回来

   return resisual*x

   ？

如果有人可以向我解释这个代码片段，那将会非常有帮助。谢谢。

Answer 1

让我们尝试分解这个问题。你必须找出

x^n

。现在，我们可以有两种情况，

1. n

   是偶数，即

   n = 2k

x^n = x^2k
    = (x^2)^(2k/2)
    = (x^2)^k

2. n

   是奇数，即

   n = 2k + 1

x^n = x^(2k+1)
    = x^(2k) * x
    = (x^2)^(2k/2) * x
    = (x^2)^k * x

您可以看到，在这两种情况下，问题都简化为寻找

(x^2)^k

。但如果

n

是奇数，则必须将

(x^2)^k

的结果与

x

相乘（Q5）。这个额外的

x

就是你的

residual

。您将从乘法恒等式

1

开始，因为如果没有残差，结果将保持

(x^2)^k

(Q1)。如果

n

是奇数，则通过乘以

residual

来更新

x

(Q3)。

现在，找到

(x^2)^k

的问题。您可以看到，这与您开始时遇到的问题相同，只是

x

现在是

x^2

，而

n

现在是

k

，即

n/2

。我想你现在可以理解你的第四个问题了。你继续这样做，直到达到

k = 1

。 （在你的例子中是

i

）

由于

n

是

long

并且

2

是

int

，所以

n/2

基本上是一个整数除法。整数除法是舍去小数部分（余数）的除法。所以，

5/2 = 2

，而不是

2.5

。我想这就是问题 2 的答案。

示例 1：

5^4

在循环开始时。

residual = 1,
x = 5,
i = 4

因为，

4

甚至

if

条件都是假的。所以，在循环的第一次迭代之后

residual = 1, 
x = 5 * 5 = 25,
i = 4 / 2 = 2

2

是偶数，

if

条件将为假。第二次循环迭代后

residual = 1, 
x = 25 * 25 = 625, 
i = 2 / 2 = 1

由于

i > 1

不再为真，循环终止。返回值将是

residual * x = 1 * 625 = 625

示例2：

2^7

在循环开始时。

residual = 1, 
x = 2, 
i = 7

因为，

7

是奇数，所以

if

条件为真。所以，在循环的第一次迭代之后

residual = 1 * 2 = 2, 
x = 2 * 2 = 4, 
i = 7 / 2 = 3

3

是奇数，

if

条件为真。第二次循环迭代后

residual = 2 * 4 = 8, 
x = 4 * 4 = 16, 
i = 3 / 2 = 1

由于

i > 1

不再为真，循环终止。返回值将是

residual * x = 8 * 16 = 128