当前位置:网站首页>【剑指offer】——16.数值的整数次方
【剑指offer】——16.数值的整数次方
2022-08-03 02:56:00 【努力学习的少年】
- 个人主页:努力学习的少年
- 🤟 版权: 本文由【努力学习的少年】原创、在CSDN首发、需要转载请联系博主
- 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
一. 题目
1.题目描述
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,x^n)。不得使用库函数,同时不需要考虑大数问题。
示例1
输入:x = 2.00000, n = 10
输出:1024.00000
示例2:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25提示:
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-104 <= xn <= 104
2.基础框架
class Solution {
public:
double myPow(double x, int n) {
}
};
3.原题链接
二.解题报告
1.思路
我们将n用二进制的方式进行看待,例如,10 把它看成1010。
定义一个变量a,如果二进制的32位中某个位中1的对应的 十进制是m,那么a=x^m.例如:1010 中的第2位的1表示2,m=2,a=x^2,1010 中的第4位的 1 十进制是8,则 m=8,a=x^8;
定义一个变量res,表示结果值,从1到31遍历n的二进制位,如果其中位置为1,则 res*=a,在让a*=a, a则跳到下一个二进制位。
如果n是负数,则将n取绝对值,按照步骤1,2,3计算res,最后在返回1/res。
因为 -2^31 <= n <= 2^31-1,如果 n==-2^31,则不能将 -2^31 取绝对值,因为 n的正数的最大值是 2^31-1,为了防止这种情况出现,可以将所有n为负数+1,最后返回的时候多除个x即可,1/res/x;
如下:
2.代码详解
class Solution {
public:
double myPow(double x, int n) {
int flag=1;//flag为1是正数,-1是负数
if(n<0){
//如果n小于0,则将其转变为正数
//如果n=2^-31,那么取绝对值还是2^-31,因为正数只能取到2^31-1
n=abs(n+1);
flag=-1;
}
double a=x;
double res=1;
while (n){
if(n&1){
//对应的二进制位是1
res*=a;
}
a*=a;
n>>=1;
}
if(flag==-1){
res=(1/res)/x;
}
return res;
}
};
边栏推荐
猜你喜欢
随机推荐
Auto.js Pro 计算脚本运行时间
Useful Monitoring Scripts What you want part1 in Oracle
C语言实验十二 指针(二)
企业上云规划与云原生环境设计
Mysql-如何进行慢SQL查询
【云原生】灰度发布、蓝绿发布、滚动发布、灰度发布解释
韦东山 数码相框 项目学习(五)libjpeg-turbo的移植
ClickHouse卸载、重安装
Postman如何做接口自动化测试?
网易数帆陈谔:云原生“牵手”低代码,加速企业数字化转型
我终于逃离了互联网,却陷入了迷茫
Rust Web(三)—— 通过sqlx连接数据库(MySQL)
豆瓣评分9.3的好书,文末给大家抽奖送几本!
VS中使用BugTrap定位程序崩溃点
一次偶然的钓鱼文件分析
compose 位移视图
leetcode:149. 直线上最多的点数
05-分布式计算框架
[Static type and dynamic type compile check and run check in Objective-C]
leetcode:139. 单词拆分