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

第 16 题：数值的整数次方（快速幂）

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

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

注意：

不会出现底数和指数同为 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