第 16 題：數(shù)值的整數(shù)次方（快速冪）
傳送門：AcWing：數(shù)值的整數(shù)次方闰靴，牛客網(wǎng) online judge 地址卦溢。
實現(xiàn)函數(shù)double Power(double base, int exponent)改艇，求base的 exponent次方。
不得使用庫函數(shù)故痊，同時不需要考慮大數(shù)問題。
注意：
- 不會出現(xiàn)底數(shù)和指數(shù)同為 0 的情況
樣例1：
輸入：10 玖姑，2
輸出：100
樣例2：
輸入：10 愕秫，-2
輸出：0.01
分析：數(shù)值的整數(shù)次方，要處理一些細節(jié)問題焰络，加法變成乘法戴甩。考慮底數(shù)為 的時候闪彼，指數(shù)不能為負數(shù)甜孤。
思路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)
# 如果是奇數(shù)
if exponent & 1:
return base * self.Power(base, exponent - 1)
return self.Power(base * base, exponent >> 1)
思路2：非遞歸的寫法，把 exponent 想象成二進制畏腕。
Python 代碼：在理解的基礎(chǔ)上記住這個寫法
class Solution(object):
def Power(self, base, exponent):
"""
:type base: float
:type exponent: int
:rtype: float
"""
if exponent < 0:
base = 1 / base
# 負數(shù)變成正數(shù)
exponent = -exponent
res = 1
while exponent:
if exponent & 1:
res *= base
base *= base
exponent >>= 1
return res
給定一個 double 類型的浮點數(shù) base 和 int 類型的整數(shù) exponent 缴川。求 base 的 exponent 次方。
求解思路與關(guān)鍵
注意分類討論與與遞歸函數(shù)的設(shè)計描馅。
關(guān)鍵：將循環(huán)變成遞歸操作把夸，每次折半求值，避免死板做循環(huán)铭污，這種感覺像加法變乘法恋日。
注意細節(jié)：底數(shù)為 0 的時候，指數(shù)為負數(shù)是沒有意義的
精確計算况凉，轉(zhuǎn)成浮點數(shù) 0.125：
System.out.println((double) 1 / 8);
- 右移 1 位運算等價于“除以 2”：
// exponent 指數(shù)谚鄙，exponent >> 1 表示將指數(shù)除以 2
System.out.println(exponent >> 1);
- 使用位運算的 與 運算符代替了求余數(shù)運算，來判斷一個數(shù)是奇數(shù)還是偶數(shù)：
if ((exponent & 1) == 0) {
Java 代碼：
public class Solution {
public double Power(double base, int exponent) {
// 先把極端情況考慮到
// 不能用 == 比較兩個浮點數(shù)是否相等刁绒，因為有誤差
if (equals(base, 0) && exponent < 0) {
throw new IllegalArgumentException("當?shù)讛?shù)為 0 的時候闷营，指數(shù)為負數(shù)沒有意義");
}
if (exponent == 0) {
return 1.0;
}
// 下面將指數(shù)的兩種情況合并成一種情況考慮
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);
}
// 使用位運算的 與 運算符代替了求余數(shù)運算，來判斷一個數(shù)是奇數(shù)還是偶數(shù)
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 指數(shù)，exponent >> 1 表示將指數(shù)除以 2
System.out.println(exponent >> 1);
}
}
LeetCode 第 50 題：)
傳送門：50. Pow(x, n)傻盟。
實現(xiàn) pow(x, n) 速蕊，即計算 x 的 n 次冪函數(shù)。
示例 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 位有符號整數(shù)娘赴，其數(shù)值范圍是 [?231, 231 ? 1] 规哲。
思路1：使用循環(huán)，把指數(shù) 想成二進制
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：將循環(huán)變成遞歸操作诽表，每次折半求值唉锌，避免死板做循環(huán)，這種感覺像加法變乘法竿奏。（腦子里回憶公式）袄简。注意細節(jié)：底數(shù)為 的時候，指數(shù)為負數(shù)是沒有意義的泛啸。
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
模板寫法1：
模板寫法2：
