1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 16 题] “数值的整数次方”做题记录

[剑指 Offer 第 2 版第 16 题] “数值的整数次方”做题记录

第 16 题:数值的整数次方(快速幂)

传送门:AcWing:数值的整数次方牛客网 online judge 地址

实现函数double Power(double base, int exponent),求baseexponent次方。

不得使用库函数,同时不需要考虑大数问题。

注意:

  • 不会出现底数和指数同为 0 的情况

样例1:

输入:10 ,2

输出:100

样例2:

输入:10 ,-2

输出:0.01

分析:数值的整数次方,要处理一些细节问题,加法变成乘法。考虑底数为 0 的时候,指数不能为负数。

思路1:使用递归

Python 代码:

  class Solution(object):
        def Power(self, base, exponent):
            """
            :type base: float
            :type exponent: int
            :rtype: float
            """

            if exponent == 0:
                return 1

            if exponent < 0:
                return 1 / self.Power(base, -exponent)

            # 如果是奇数
            if exponent & 1:
                return base * self.Power(base, exponent - 1)
            return self.Power(base * base, exponent >> 1)

思路2:非递归的写法,把 exponent 想象成二进制。

Python 代码:在理解的基础上记住这个写法

  class Solution(object):
        def Power(self, base, exponent):
            """
            :type base: float
            :type exponent: int
            :rtype: float
            """

            if exponent < 0:
                base = 1 / base
                # 负数变成正数
                exponent = -exponent

            res = 1
            while exponent:
                if exponent & 1:
                    res *= base
                base *= base
                exponent >>= 1
            return res

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent 。求 base 的 exponent 次方。

求解思路与关键

  • 注意分类讨论与与递归函数的设计。
  • 关键:将循环变成递归操作,每次折半求值,避免死板做循环,这种感觉像加法变乘法。
  • 注意细节:底数为 0 的时候,指数为负数是没有意义的
  • 精确计算,转成浮点数 0.125:
  System.out.println((double) 1 / 8);

  • 右移 1 位运算等价于“除以 2”:
  // exponent 指数,exponent >> 1 表示将指数除以 2
    System.out.println(exponent >> 1);

  • 使用位运算的 与 运算符代替了求余数运算,来判断一个数是奇数还是偶数:
  if ((exponent & 1) == 0) {

Java 代码:

  public class Solution {

        public double Power(double base, int exponent) {
            // 先把极端情况考虑到
            // 不能用 == 比较两个浮点数是否相等,因为有误差
            if (equals(base, 0) && exponent < 0) {
                throw new IllegalArgumentException("当底数为 0 的时候,指数为负数没有意义");
            }
            if (exponent == 0) {
                return 1.0;
            }
            // 下面将指数的两种情况合并成一种情况考虑
            if (exponent > 0) {
                return power(base, exponent);
            } else {
                return power(1 / base, -exponent);
            }
        }

        public double power(double base, int exponent) {
            if (exponent == 0) {
                return 1.0;
            }
            if (exponent % 2 == 0) {
                double square = power(base, exponent / 2);
                return square * square;
            } else {
                double square = power(base, (exponent - 1) / 2);
                return square * square * base;
            }
        }

        private boolean equals(double num1, double num2) {
            return num1 - num2 < 0.000001 && num1 - num2 > -0.000001;
        }
    }

Java 代码:

  public class Solution {

        public double Power(double base, int exponent) {
            if (exponent == 0) {
                return 1;
            }
            if (exponent < 0) {
                return 1 / Power(base, -exponent);
            }
            // 使用位运算的 与 运算符代替了求余数运算,来判断一个数是奇数还是偶数
            if ((exponent & 1) == 0) {
                double square = Power(base, exponent >> 1);
                return square * square;
            } else {
                double square = Power(base, (exponent - 1) >> 1);
                return square * square * base;
            }
        }

        public static void main(String[] args) {
            int base = 3;
            int exponent = -3;
            Solution solution = new Solution();
            double result1 = solution.Power(base, exponent);
            System.out.println(result1);
            exponent = 6;
            double result2 = solution.Power(base, exponent);
            System.out.println(result2);
            // exponent 指数,exponent >> 1 表示将指数除以 2
            System.out.println(exponent >> 1);
        }
    }

LeetCode 第 50 题:Pow(x, n)

传送门:50. Pow(x, n)

实现 pow(x, n) ,即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10 输出: 1024.00000

示例 2:

输入: 2.10000, 3 输出: 9.26100

示例 3:

输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

思路1:使用循环,把指数 n 想成二进制

Python 代码:

  class Solution:
        def myPow(self, x, n):
            """
            :type x: float
            :type n: int
            :rtype: float
            """


            if n < 0:
                x = 1 / x
                n = - n
            res = 1
            while n:
                if n & 1 == 1:
                    res *= x
                # 注意:这里不要写成  res *= res
                x *= x 
                n >>= 1
            return res

思路2:将循环变成递归操作,每次折半求值,避免死板做循环,这种感觉像加法变乘法。(脑子里回忆公式)。注意细节:底数为 0 的时候,指数为负数是没有意义的。

Python 代码:递归写法:注意边界条件

  class Solution:
        def myPow(self, x, n):
            """
            :type x: float
            :type n: int
            :rtype: float
            """
            # 对 x = 0 , n < 0 还要做特判
            if n == 0:
                return 1
            if n < 0:
                return 1 / self.myPow(x, -n)

            if n & 1:
                return x * self.myPow(x, n - 1)
            return self.myPow(x * x, n // 2)

基本的写法:

https://blog.csdn.net/happyaaaaaaaaaaa/article/details/76552127

liwei201910111_1.png

模板写法1:

liwei201910110_2.png

模板写法2:

liwei20191017_3.png

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 16 题] “数值的整数次方”做题记录

链接:https://www.javajike.com/article/3266.html

« [剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录
[剑指 Offer 第 2 版第 18 题] “删除链表中重复的结点”做题记录»

相关推荐

QR code