16. 数值的整数次方

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9816.%20%E6%95%B0%E5%80%BC%E7%9A%84%E6%95%B4%E6%95%B0%E6%AC%A1%E6%96%B9/README.md

面试题 16. 数值的整数次方

题目描述

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

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

提示：

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

注意：本题与主站 50 题相同：https://leetcode.cn/problems/powx-n/

解法

方法一：数学（快速幂）

快速幂算法的核心思想是将幂指数 $n$ 拆分为若干个二进制位上的 $1$ 的和，然后将 $x$ 的 $n$ 次幂转化为 $x$ 的若干个幂的乘积。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为幂指数。

2的5次方=2的［101］2进制次方=2的［2的0次方+2的2次方］，其中2的2次方 是 （2的0次方）的2次方a*=a

Python3

class Solution:def myPow(self, x: float, n: int) -> float:def qpow(a: float, n: int) -> float:ans = 1while n:if n & 1:ans *= aa *= an >>= 1return ansreturn qpow(x, n) if n >= 0 else 1 / qpow(x, -n)

Java

class Solution {public double myPow(double x, int n) {return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long) n);}private double qpow(double a, long n) {double ans = 1;for (; n > 0; n >>= 1) {if ((n & 1) == 1) {ans = ans * a;}a = a * a;}return ans;}
}

C++

class Solution {
public:double myPow(double x, int n) {auto qpow = [](double a, long long n) {double ans = 1;for (; n; n >>= 1) {if (n & 1) {ans *= a;}a *= a;}return ans;};return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long) n);}
};

Go

func myPow(x float64, n int) float64 {qpow := func(a float64, n int) float64 {ans := 1.0for ; n > 0; n >>= 1 {if n&1 == 1 {ans *= a}a *= a}return ans}if n >= 0 {return qpow(x, n)}return 1 / qpow(x, -n)
}

TypeScript

function myPow(x: number, n: number): number {const qpow = (a: number, n: number): number => {let ans = 1;for (; n; n >>>= 1) {if (n & 1) {ans *= a;}a *= a;}return ans;};return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
}

Rust

impl Solution {#[allow(dead_code)]pub fn my_pow(x: f64, n: i32) -> f64 {let mut x = x;let n = n as i64;if n >= 0 {Self::quick_pow(&mut x, n)} else {1.0 / Self::quick_pow(&mut x, -n)}}#[allow(dead_code)]fn quick_pow(x: &mut f64, mut n: i64) -> f64 {// `n` should greater or equal to zerolet mut ret = 1.0;while n != 0 {if (n & 0x1) == 1 {ret *= *x;}*x *= *x;n >>= 1;}ret}
}

JavaScript

/*** @param {number} x* @param {number} n* @return {number}*/
var myPow = function (x, n) {const qpow = (a, n) => {let ans = 1;for (; n; n >>>= 1) {if (n & 1) {ans *= a;}a *= a;}return ans;};return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
};

C#

public class Solution {public double MyPow(double x, int n) {return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long)n);}private double qpow(double a, long n) {double ans = 1;for (; n > 0; n >>= 1) {if ((n & 1) == 1) {ans *= a;}a *= a;}return ans;}
}

Swift

class Solution {func myPow(_ x: Double, _ n: Int) -> Double {return n >= 0 ? qpow(x, Int64(n)) : 1 / qpow(x, -Int64(n))}private func qpow(_ a: Double, _ n: Int64) -> Double {var ans: Double = 1var base: Double = avar exponent: Int64 = nwhile exponent > 0 {if (exponent & 1) == 1 {ans *= base}base *= baseexponent >>= 1}return ans}
}