Leetcode 50.Pow(x,n)

news/2025/2/22 15:49:44/

 

实现 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：

double myPow(double x, int n){int i,num=n;double factor,answer=1;factor=x;if(num<0){num=-num;factor=1/x;}for(i=1;i<=n;i++){answer=answer*factor;}return answer;
}

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

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

double myPow(double x, int n){int i,num=n;double factor,answer=1;factor=x;if(num<0){num=-num;factor=1/x;}for(i=1;i<=num;i++){answer=answer*factor;}return answer;
}

当 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语言实现：

#include <stdio.h>double myPow(double x, int n) {// 使用 long long 避免整数溢出long long N = n;double ans = 1.0;// 处理负指数的情况if(N < 0) {x = 1 / x;N = -N;}// 快速幂算法while(N > 0) {if(N % 2 == 1) {ans *= x; // 如果当前位是1，乘到结果中}x *= x; // 计算下一位N /= 2; // 移动到下一位}return ans;
}int main() {double x = 2.0;int n = -2;printf("%lf\n", myPow(x, n)); // 输出：0.25return 0;
}

### C++ 实现：

#include <iostream>
using namespace std;class Solution {
public:double myPow(double x, long long n) {if(n < 0) {x = 1 / x;n = -n;}double ans = 1.0;while(n > 0) {if(n & 1) {ans *= x;}x *= x;n >>= 1;}return ans;}
};int main() {Solution s;double x = 2.0;int n = -2;cout << s.myPow(x, n) << endl;  // 输出：0.25return 0;
}

### Java 实现：

public class Solution {public double myPow(double x, int n) {long N = n; // 使用 long 避免整数溢出if (N < 0) {x = 1 / x;N = -N;}double ans = 1.0;while (N > 0) {if ((N & 1) == 1) {ans *= x;}x *= x;N >>= 1;}return ans;}public static void main(String[] args) {Solution s = new Solution();double x = 2.0;int n = -2;System.out.println(s.myPow(x, n));  // 输出：0.25}
}

这两个实现基本上是相同的，主要的区别在于语法。注意在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：

​
class Solution {
public:double quickMul(double x, long long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};​

JAVA题解：

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}
}

方法2：

C++题解：

class Solution {
public:double quickMul(double x, long long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};

JAVA题解：

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;}
}

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

大师的评价

我的代码和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. **数学知识的运用**
这个问题还涉及到一些数学知识，比如指数和幂的性质。对基础数学知识的理解能帮助我们更好地理解问题和设计算法。

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


http://www.ppmy.cn/news/1131634.html

相关文章

vue前端项目中添加独立的静态资源

vue前端项目中添加独立的静态资源

如果想要在vue项目中放一些独立的静态资源&#xff0c;比如html文件或者用于下载的业务模板或其他文件等&#xff0c;需要在vue打包的时候指定一下静态资源的位置和打包后的目标位置。 使用的是 copy-webpack-plugin 插件&#xff0c;如果没有安装则需要先安装一下&#xff0c;…
阅读更多...
Spring的注解开发-依赖注入相关注解

Spring的注解开发-依赖注入相关注解

在之前的学习中&#xff0c;Bean的依赖注入主要是通过xml配置文件中<property>来完成属性的注入操作&#xff0c;在往期的bean创建的文章中&#xff0c;都是以xml方式来完成bean对象的配置。 Spring主要提供以下注解&#xff0c;用于Bean内部进行属性注入 注解用途Autow…
阅读更多...
wvp-GB28181-pro windows系统编译安装的坑：录像功能不能正常使用

wvp-GB28181-pro windows系统编译安装的坑：录像功能不能正常使用

说明 wvp-GB28181-pro 只是包含了实时视频的接入功能&#xff1b; GitHub - 648540858/wvp-GB28181-pro: WEB VIDEO PLATFORM是一个基于GB28181-2016标准实现的网络视频平台&#xff0c;支持NAT穿透&#xff0c;支持海康、大华、宇视等品牌的IPC、NVR、DVR接入。支持国标级联…
阅读更多...
ROS2 中的轻量级、自动化、受控回放

ROS2 中的轻量级、自动化、受控回放

一、说明 这篇文章描述了一种在 ROS2 中实现受控重播器的轻量级方法。用以测试中将现象重新播放一遍&#xff0c;以实现调参或故障定位的目的。所有源代码都可以在这里找到。该帖子也可在此处获得。 二、问题&#xff1a;不同步重播 任何曾经认真开发过 ROS2 的人都会知道这个问…
阅读更多...
Kafka：安装与简单使用

Kafka：安装与简单使用

文章目录 下载安装windows安装目录结构启动服务器创建主题发送一些消息启动消费者设置多代理集群常见问题 工具kafka tool 常用指令topic查看topic删除topic 常见问题参考文献 下载安装 下载地址&#xff1a;kafka-download windows安装 下载完后&#xff0c;找一个目录解压…
阅读更多...
Arcgis克里金插值报错：ERROR 010079: 无法估算半变异函数。 执行(Kriging)失败。

Arcgis克里金插值报错：ERROR 010079: 无法估算半变异函数。 执行(Kriging)失败。

Arcgis克里金插值报错&#xff1a;ERROR 010079: 无法估算半变异函数。 执行(Kriging)失败。 问题描述&#xff1a; 原因&#xff1a; shape文件的问题&#xff0c;此图可以看出&#xff0c;待插值的点有好几个都超出了地理范围之外&#xff0c;这个不知道是坐标系配准的问…
阅读更多...
网络-Ajax

网络-Ajax

文章目录 前言一、Ajax优点&#xff1a;缺点&#xff1a; 二、使用步骤XNLHttpRequest对象完整代码 总结 前言 本文主要记录Ajax技术的简介&#xff0c;以及用法。 一、Ajax Ajax是一组用于在Web浏览器和Web服务器之间进行异步通信的Web开发技术。 它代表着Asynchronous Java…
阅读更多...
2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版

2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版

#Go 1.21新增的 log/slog 完美解决了以上问题&#xff0c;并且带来了很多其他很实用的特性。 本次编译不使用log/slog 包 su - echo $GOPATH ;echo $GOROOT; cd /tmp; busybox wget --no-check-certificate https://go.dev/dl/go1.18.linux-amd64.tar.gz;\ which tar&&am…
阅读更多...
最新文章

Copyright @ 2022~2023