devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leetcode 50.Pow(x,n)

作者：从前慢现在也慢 | 2024-04-14 08:06:49

赞

踩

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 是一个整数
  • 要么 x 不为零，要么 n > 0 。
  • -104 <= xn <= 104

一、信息

1.实现数学中的幂函数。

2.三个示例

二、分析

条件1：告诉我此次的目的

条件2：告诉我这个函数结果保留小数点后五位

三、步骤

第一步 接收x和n

第二步 n赋值给循环的次数，x赋给每次要乘的数

第三步 循环相乘

第三步 return 即可

流程图：

四、遇到问题

1.由于n如果时负数那么我们显然累乘将失效，因为此时的x已经是它的倒数的累乘了而计算机其实根本不认识负幂数，所以我们得分类讨论。

分类讨论——四种情况：

分析：

1.情况1和情况2都不需要对x进行操作直接累乘就行了

2.情况3和情况4则首先需要判断n是否为负数如果是负数那么我们就先对x取倒数然后再进行累乘。

3.其次这样的话就不能直接把n赋给x了

五、实现

错误代码：

第一次错误——应该把num赋给i而不是原始的n：

  1. double myPow(double x, int n){
  2. 	int i,num=n;
  3. 	double factor,answer=1;
  4. 	factor=x;
  5. 	if(num<0){
  6. 		num=-num;
  7. 		factor=1/x;
  8. 	}
  9. 	for(i=1;i<=n;i++){
  10. 		answer=answer*factor;
  11. 	}
  12. 	return answer;
  13. }

当 n 是负数时，你已经将 num 转换为了正数，并且相应地调整了 factor。但是在循环中，你使用的是原始的 n，而不是调整后的 num。这会导致在 n 为负数时循环不执行。 

第二次错误——超时了+溢出：

  1. double myPow(double x, int n){
  2. 	int i,num=n;
  3. 	double factor,answer=1;
  4. 	factor=x;
  5. 	if(num<0){
  6. 		num=-num;
  7. 		factor=1/x;
  8. 	}
  9. 	for(i=1;i<=num;i++){
  10. 		answer=answer*factor;
  11. 	}
  12. 	return answer;
  13. }

当 n 是负数时，由于 int 类型的范围是 −2,147,483,648 到 2,147,483,647，所以当 n 等于 -2,147,483,648 时，转换为正数会导致溢出。为了避免这个问题，我应该使用 long long 类型来存储 num。 

运行结果：

六、更正后我的答案 

### 题目描述：
计算 `x` 的 `n` 次幂，即求 `x^n`。

### 思考过程：
1. **基本情况：** 
    - 如果 `n` 等于 0，对于任何 `x`（除了0），`x^0` 都是 1。
    - 如果 `x` 等于 1 或 -1，并且 `n` 是负数，我们要计算的是 `1/x` 的正 `n` 次幂。

2. **负指数处理：**
    - 如果 `n` 是负数，我们可以计算 `1/x` 的正 `n` 次幂。

3. **快速幂算法：**
    - 快速幂算法的基本思想是将问题分解为更小的部分。例如，`x^8` 可以分解为 `(x^4)^2`。
    - 我们可以利用这个性质，将 `n` 进行二进制分解，从而将原问题分解为若干个子问题，并利用已解决的子问题来解决更大的问题。
    - 对于每一个二进制位，如果该位是1，我们就将当前的 `x` 乘到结果中。

### C语言实现：

  1. #include <stdio.h>
  2.  
  3. double myPow(double x, int n) {
  4.     // 使用 long long 避免整数溢出
  5.     long long N = n;
  6.     double ans = 1.0;
  7.     
  8.     // 处理负指数的情况
  9.     if(N < 0) {
  10.         x = 1 / x;
  11.         N = -N;
  12.     }
  13.     
  14.     // 快速幂算法
  15.     while(N > 0) {
  16.         if(N % 2 == 1) {
  17.             ans *= x; // 如果当前位是1，乘到结果中
  18.         }
  19.         x *= x; // 计算下一位
  20.         N /= 2; // 移动到下一位
  21.     }
  22.     return ans;
  23. }
  24.  
  25. int main() {
  26.     double x = 2.0;
  27.     int n = -2;
  28.     printf("%lf\n", myPow(x, n)); // 输出：0.25
  29.     return 0;
  30. }

### C++ 实现：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class Solution {
  5. public:
  6.     double myPow(double x, long long n) {
  7.         if(n < 0) {
  8.             x = 1 / x;
  9.             n = -n;
  10.         }
  11.         
  12.         double ans = 1.0;
  13.         while(n > 0) {
  14.             if(n & 1) {
  15.                 ans *= x;
  16.             }
  17.             x *= x;
  18.             n >>= 1;
  19.         }
  20.         return ans;
  21.     }
  22. };
  23.  
  24. int main() {
  25.     Solution s;
  26.     double x = 2.0;
  27.     int n = -2;
  28.     cout << s.myPow(x, n) << endl;  // 输出：0.25
  29.     return 0;
  30. }

### Java 实现：

  1. public class Solution {
  2.     public double myPow(double x, int n) {
  3.         long N = n; // 使用 long 避免整数溢出
  4.         if (N < 0) {
  5.             x = 1 / x;
  6.             N = -N;
  7.         }
  8.  
  9.         double ans = 1.0;
  10.         while (N > 0) {
  11.             if ((N & 1) == 1) {
  12.                 ans *= x;
  13.             }
  14.             x *= x;
  15.             N >>= 1;
  16.         }
  17.         return ans;
  18.     }
  19.  
  20.     public static void main(String[] args) {
  21.         Solution s = new Solution();
  22.         double x = 2.0;
  23.         int n = -2;
  24.         System.out.println(s.myPow(x, n));  // 输出：0.25
  25.     }
  26. }

这两个实现基本上是相同的，主要的区别在于语法。注意在Java实现中，我们使用了`long`来避免`int`溢出的问题，因为`int`在Java中是有固定大小的（32位）。在C++实现中，我们使用了`long long`来确保足够的位数，因为`int`和`long`在C++中的大小可能会因编译器和平台而异。

 

### 分析过程：
1. **时间复杂度：**
   - 由于每次循环 `n` 都会除以 2，所以循环的次数是 `O(log n)`。
   - 因此，这个算法的时间复杂度是 `O(log n)`。

2. **空间复杂度：**
   - 这个算法只使用了几个变量来存储中间结果，因此空间复杂度是 `O(1)`。

### 结论：
这个快速幂算法是求幂问题的一种高效解决方案，它通过减少所需的乘法次数来提高效率，并具有较低的时间和空间复杂度。

Leetcode官方题解：

方法1：

  1. ​
  2. class Solution {
  3. public:
  4.     double quickMul(double x, long long N) {
  5.         if (N == 0) {
  6.             return 1.0;
  7.         }
  8.         double y = quickMul(x, N / 2);
  9.         return N % 2 == 0 ? y * y : y * y * x;
  10.     }
  11.  
  12.     double myPow(double x, int n) {
  13.         long long N = n;
  14.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  15.     }
  16. };
  17.  
  18.  
  19. ​

JAVA题解：

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         long N = n;
  4.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  5.     }
  6.  
  7.     public double quickMul(double x, long N) {
  8.         if (N == 0) {
  9.             return 1.0;
  10.         }
  11.         double y = quickMul(x, N / 2);
  12.         return N % 2 == 0 ? y * y : y * y * x;
  13.     }
  14. }
  15.

方法2：

C++题解：

  1. class Solution {
  2. public:
  3.     double quickMul(double x, long long N) {
  4.         double ans = 1.0;
  5.         // 贡献的初始值为 x
  6.         double x_contribute = x;
  7.         // 在对 N 进行二进制拆分的同时计算答案
  8.         while (N > 0) {
  9.             if (N % 2 == 1) {
  10.                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
  11.                 ans *= x_contribute;
  12.             }
  13.             // 将贡献不断地平方
  14.             x_contribute *= x_contribute;
  15.             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
  16.             N /= 2;
  17.         }
  18.         return ans;
  19.     }
  20.  
  21.     double myPow(double x, int n) {
  22.         long long N = n;
  23.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  24.     }
  25. };
  26.

JAVA题解：

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         long N = n;
  4.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  5.     }
  6.  
  7.     public double quickMul(double x, long N) {
  8.         double ans = 1.0;
  9.         // 贡献的初始值为 x
  10.         double x_contribute = x;
  11.         // 在对 N 进行二进制拆分的同时计算答案
  12.         while (N > 0) {
  13.             if (N % 2 == 1) {
  14.                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
  15.                 ans *= x_contribute;
  16.             }
  17.             // 将贡献不断地平方
  18.             x_contribute *= x_contribute;
  19.             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
  20.             N /= 2;
  21.         }
  22.         return ans;
  23.     }
  24. }
  25.

七、复盘对我分析思考过程的评价

大师的评价

我的代码和Leetcode题解的方法和代码的比较:

这个题解提供了两种解决方案：快速幂+递归和快速幂+迭代。

1. 快速幂 + 递归

这种方法采用分治的思想，每次将幂次减半。它用递归来实现，所以空间复杂度为O(logn)。这个方法的优势在于它的简洁性和直观性，对于理解问题很有帮助。但是，由于递归的开销，当n非常大时，可能会造成堆栈溢出。

2. 快速幂 + 迭代

这种方法将递归方法转化为迭代，消除了递归带来的堆栈溢出的风险，空间复杂度为O(1)，比递归方法更加高效。它通过观察n的二进制表示中1的位置来计算x的幂，实际应用中更为常用。

对比你的方法

你的方法是直接循环n次来计算x的n次方。这种方法的时间复杂度是O(n)。当n非常大时，这会是一个很低效的算法。而且，你的方法没有处理n为负数的情况，直接循环会造成死循环。

总结

  1. 优势

    • 快速幂方法，无论是递归还是迭代，时间复杂度都是O(logn)，非常高效。
    • 迭代方法的空间复杂度为O(1)，对于空间敏感的场合非常适用。

  2. 劣势

    • 递归方法的空间复杂度为O(logn)，在幂次非常大时可能会有堆栈溢出的风险。
    • 递归方法的理解和实现相对迭代方法更复杂一些。

  3. 改进你的方法

    • 你的方法可以通过实现快速幂来减少时间复杂度到O(logn)。
    • 处理n为负数的情况，可以通过计算x的正n次方，然后取倒数来得到结果。

八、反思总结

学到了什么：

通过这道题目，我们能学到以下几点：

### 1. **算法优化的重要性**
这道题目展示了相同问题的不同解决方案会有很大的效率差异。对于初学者来说，很容易想到暴力解法，即直接计算x的n次方，但这种方法的时间复杂度是O(n)，在n很大时效率很低。而快速幂方法，无论是递归还是迭代，时间复杂度都可以优化到O(logn)，大大提高了算法的效率。

### 2. **不同解法的优劣**
- **递归**：易于理解和实现，但可能有堆栈溢出的风险，且空间复杂度较高。
- **迭代**：迭代版本可以消除递归带来的堆栈溢出风险，且空间复杂度为O(1)。

学会权衡不同解法的优劣，并根据实际情况选择最合适的解法，是解决问题的关键。

### 3. **边界条件和特殊情况的处理**
这道题目要求处理n为负数的情况。处理特殊和边界情况是算法设计中很重要的一步，否则可能导致程序错误或者无法处理某些输入。

### 4. **二进制和位运算的应用**
快速幂算法利用了n的二进制表示来高效地计算x的n次方。通过观察n的二进制表示中1的位置，我们可以减少不必要的计算。这显示了二进制和位运算在算法设计中的重要应用。

### 5. **算法设计的灵活性和多样性**
这道题目通过展示递归和迭代两种不同的解法，体现了算法设计的灵活性和多样性。掌握多种解法并能灵活运用，可以帮助我们更好地解决实际问题。

### 6. **数学知识的运用**
这个问题还涉及到一些数学知识，比如指数和幂的性质。对基础数学知识的理解能帮助我们更好地理解问题和设计算法。

### 总结
综上所述，这道题目不仅能帮助我们学习和巩固快速幂算法，还能够加深我们对于递归、迭代、位运算、数学知识运用等方面的理解，让我们更加灵活和深入地去思考和解决问题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/421040?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号