剑指offer | 面试题13：数值的整数次方

千羽

发布于 2021-12-29 13:12:25

2730

发布于 2021-12-29 13:12:25

文章被收录于专栏：程序员千羽

死磕算法系列文章

数值的整数次方

“Leetcode : https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_13_myPow/Solution.java

题目描述：

实现 pow(x, n)，即计算 x 的 n 次幂函数（即，x^n ）。不得使用库函数，同时不需要考虑大数问题。

示例 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/2^2 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

快速幂解析（二分法角度）：

“快速幂实际上是二分思想的一种应用。

转化为位运算：

向下整除 n // 2 等价于 右移一位 n >> 1 ；
取余数 n % 2等价于判断二进制最右一位值 n & 1；

算法流程：

当 x = 0 时：直接返回 0 （避免后续 x = 1 / x操作报错）。
初始化 res = 1 ；
当 n < 0 时：把问题转化至n ≥ 0 的范围内，即执行 x = 1/x ，n = - n ；
循环计算：当 n = 0时跳出；
1. 当 n & 1 = 1 时：将当前 x 乘入 res （即 res *= x ）；
2. 执行 x = x^2 （即 x *= x ）；
3. 执行 n 右移一位（即 n >>= 1）。
返回 res。

复杂度分析：

时间复杂度 O(log_2 n) ： 二分的时间复杂度为对数级别。
空间复杂度 O(1) ： res, b 等变量占用常数大小额外空间。

代码：

“Java 代码中 int32 变量 n 属于 n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。

package com.nateshao.sword_offer.topic_13_myPow;

/**
 * @date Created by 邵桐杰 on 2021/11/21 10:48
 * @微信公众号 程序员千羽
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:  剑指 Offer 16. 数值的整数次方
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 */
public class Solution {
    public static void main(String[] args) {
        double v = myPow1(2, 3);
        System.out.println("v = " + v);
    }

    public static double myPow1(double x, int n) {
        if (n == 0 || x == 1.0) return 1.0;
        if (n == 1) return x;
        if (n == -1) return 1.0 / x;

        double res = myPow1(x, n / 2);
        res = res * res;

        //如果是奇数
        if ((n & 1) == 1 && n > 0) res = res * x; // 就是判断奇偶，=1为奇数，比%效率更高
        if ((n & 1) == 1 && n < 0) res = res * 1 / x;

        return res;

    }

    public double myPow2(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        if (n == -1) return 1 / x;
        double half = myPow2(x, n >> 1); // n>>1就是n/2，但是右移效率更高
        double rest = myPow2(x, n & 1);
        return half * half * rest;
    }
}