专栏首页大白技术控的技术自留地C++版 - 剑指Offer 面试题11:数的整数次方(Leetcode50. Pow(x, n))【C库函数pow模拟】题解

C++版 - 剑指Offer 面试题11:数的整数次方(Leetcode50. Pow(x, n))【C库函数pow模拟】题解

面试题:数的整数次方

温馨提示:本技术博客的相关代码将会在github(https://github.com/yanglr)中同步更新,敬请star和fork...

题目:实现函数double Power(double base, int exponent), 求base的exponent次方。不得使用库函数,同时不需要考虑大数问题

其中base为浮点数,而exponent为整数(可正可负,可为0).

提交网址: http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165

分析:

二分求幂(时间复杂度为log n),使用二分法则问题可转化为:

此公式并不能很好的反映情况,且用n=2k+1表示奇数时,

故以上公式可改进成如下公式:

其中

不论n是奇是偶,对其折半后下取整即可得到k,而在编程语言中如果变量类型为整型,k=n/2,如果用弱数据类型的语言(比如:PHP、Python、JavaScript等)实现此方法,需自行ceiling或ceil进行下取整!

当选取某种强数据类型的编程语言,且上述公式中的变量n类型为整型时,可继续简化:

这样,比较容易理解,也有利于写出清晰结构的代码...

非递归实现 AC代码:

#include<cstdio>
using namespace std;
class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent < 0)  // 将指数exponent<0的情形规约为exponent>0的情形
        {
            exponent = -exponent;
            base = 1.0/base;
        }
        double res = 1.0;
        for(; exponent > 0; exponent >>= 1)  // 指数每次折半,进行迭代
        {
            if((exponent & 0x1) == 1)  res *= base;  // a & 0x1 等价于 a%2,用来判断a的奇偶性, 位运算优先级低于关系运算符, 记得加括号!
            base *= base;  // 底数base替换为base^2
        }
        return res;
    }
};

// 以下为测试
int main()
{
	Solution sol;
	double num1=sol.Power(20, 2);
	double num2=sol.Power(13, -2);
	double num3=sol.Power(-10, 3);
	double num4=sol.Power(0, 0);	
	printf("%f\n",num1); 
	printf("%f\n",num2);
	printf("%f\n",num3);		
	printf("%d\n",num4);		
	return 0;
}

剑指offer上不需要考虑大数问题,可是Leetcode上需要考虑大数问题、边界值问题...

50. Pow(x, n)

Total Accepted: 90298 Total Submissions: 323977 Difficulty: Medium    ACrate: 27.9%

Implement pow(x, n).

提交网址: https://leetcode.com/problems/powx-n/

刚开始Leetcode上越界条件怎么都过不去,每次都是 299 / 300 test cases passed....

输入输出样例:

Input: 2.00000 -2147483648 Output: 0.00000 ---------------- Input: 1.00000 -2147483648 Output: 1.00000 ---------------- Input: -1.00000 2147483647 Output: -1.00000 ---------------- Input: -1.00000 -2147483648 Output: 1.00000 ---------------- Input: 2.00000 -2147483648 Output: 0.00000 LeetCode 已AC代码:

#include<cstdio>
#include<climits>     // INT_MAX和INT_MAX在C语言limits.h中定义,而float.h 定义了double、float类型数的最大最小值 
using namespace std;
class Solution {
public:
    double myPow(double x, int n)
    {
        if(x==0 && n==0) return 1;    
        if((n<=INT_MIN || n>=INT_MAX) && (x>1 || x<-1)) return 0;
        if(x==1 && n==INT_MIN) return 1;  // 加的超强补丁   
        if(n>=INT_MAX && (x==1 || x==-1)) return x;
        if(n<=INT_MIN && (x==1 || x==-1)) return -x;

        if(n < 0)
        {
            n = -n;
            x = 1.0/x;
        }
        double res = 1.0;
        for(; n > 0; n >>= 1)
        {
            if((n & 0x1) == 1)  res *= x;
            x *= x;  // 底数x替换为x^2
        }
        return res;
    }
};

// 以下为测试
int main()
{
	Solution sol;
	double res1=sol.myPow(0, 0);	
	double res2=sol.myPow(13, -2);
	double res3=sol.myPow(-10, 0);
	double res4=sol.myPow(20, 2);	
	double res5=sol.myPow(2.00000,-2147483648);
	double res6=sol.myPow(1.00000,-2147483648);
	double res7=sol.myPow(-1.00000,2147483647);
	double res8=sol.myPow(-1.00000,-2147483648);
	double res9=sol.myPow(2.00000,-2147483648);
		
	printf("%f\n", res1); 
	printf("%f\n", res2);
	printf("%f\n", res3);		
	printf("%f\n", res4);
	printf("%f\n", res5);
	printf("%f\n", res6);		
	printf("%f\n", res7);
	printf("%f\n", res8);
	printf("%f\n", res9);				
	return 0;
}

相关链接:

剑指offer-面试题11:数值的整数次方 https://www.douban.com/note/355223813/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Oracle】-【体系结构-DBWR】-DBWR进程相关理解

    首先从名称上,DBWR全称是Database Writer Process,属于Oracle后台进程的一种,有的地方也叫DBWn,我想这里是出于DBWR进程个数...

    bisal
  • MeanShift算法C++解析(一)

    毕业设计的核心是MeanShift算法,作为一个小本,默默先抛开高端的MeanShift纯理论来研究一下程序对图像都做了什么吧。然后回过头去看数学理论会轻松很...

    钱塘小甲子
  • 《Monkey Java》课程6.2之访问权限

    GitOPEN
  • 【Oracle】-【LRU和DBWR】-LRU算法与DBWR中的应用

    Oracle体系结构中经常看到LRU算法,Least Recently Used,也有叫“最近最少使用页面置换算法”,简单讲...

    bisal
  • 【每日一摩斯】-Shared Pool优化和Library Cache Latch冲突优化 (1523934.1)-系列2

    在有完整的统计信息并且SQL语句在predicate(限定条件)中使用具体值时,基于成本的优化器 (CBO)能工作的最好。比较下面

    bisal
  • MeanShift算法C++解析(五)

    最近四旋翼高空坠落几乎完全报废,阻碍了四旋翼飞行平台的进展,于是顺便开始写论文和思考一下Mean shift算法的改进。觉得核函数是一个很值得改进的地方,于是...

    钱塘小甲子
  • MeanShift算法C++解析(二)

    当在视频流界面按下按键“P”的时候呢,画面就会停止,点击两下鼠标,分别作为追踪目标选择的左上角和右下角,如此,就可确定追踪目标。在鼠标选择完毕之后,回调函数o...

    钱塘小甲子
  • Android M (API23) 中对权限的授权处理

    Android M的发布,最重要的提升就是权限的控制,这么多年来Android App的权限滥用状况将逐步得到改善。

    GitOPEN
  • 视频追踪之目标选择(一)------边缘检测值函数准备

    视频跟踪(video tracking)第一步往往是人工的目标选取,当然在特定场合,也可以用动态检测来实现目标的自动选择。人工选择的情况下,往往是从某一fra...

    钱塘小甲子
  • 聊聊flink Table的Joins

    flink-table_2.11-1.7.0-sources.jar!/org/apache/flink/table/api/table.scala

    codecraft

扫码关注云+社区

领取腾讯云代金券