题解 | #数值的整数次方#
数值的整数次方
http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00
算法思想一：直接暴力法
解题思路：
将 exponent 分为正 负数，当为负数时将 exponent 转为正数，并采用循环计算 exponent 次幂，然后将结果转为其倒数
当为正数时，可直接采用循环计算 exponent 次幂
代码展示：
# -*- coding:utf-8 -*- class Solution: def Power(self, base, exponent): # write code here result = 1 # 如果base为0 if base == 0: return 0 # 如果exponent为0，则为0 if exponent == 0: return 1 # 如果exponent为负数，则将其转化为整数计算结果求倒数 if exponent < 0: for i in range(-exponent): result = result * base return 1/result # 循环计算exponent 次方 for i in range(exponent): result = result * base return result
复杂度分析：
时间复杂度O(N)：循环计算只需要根据 exponent 的大小
空间复杂度O(1)：需要常数级空间
算法思想二：递归
如果exponent == 0，返回1
如果exponent < 0，最终结果为 1 / x^{-n}
如果exponent为奇数，最终结果为 x * x ^ {n - 1}
如果exponent为偶数，最终结果为 x ^ {2*(n/2)}
如果exponent < 0，最终结果为 1 / x^{-n}
如果exponent为奇数，最终结果为 x * x ^ {n - 1}
如果exponent为偶数，最终结果为 x ^ {2*(n/2)}
代码展示：
public class Solution {
public double Power(double base, int exponent) {
//如果exponent等于0，直接返回1
if (exponent == 0)
return 1;
//如果exponent小于0，把它改为正数
if (exponent < 0) return Power(1 / base, -exponent); //根据exponent是奇数还是偶数来做不同的处理 递归 return (exponent % 2 == 0) ? Power(base * base, exponent / 2) : base * Power(base * base, exponent / 2); } } 复杂度分析：
时间复杂度：O(logn)：其中n表示exponent
空间复杂度：O(logn)
算法思路三：位运算
算法思想：
循环遍历exponent的每一位
循环的过程中，让base做乘方运算
若当前最低位为1，则将res乘以当前base的值
最后若 exponent 为负数，则将结果转为倒数
代码展示：
class Solution {
public double Power(double base, int exponent) {
double res = 1.0;
for (int i = exponent; i != 0; i /= 2) {
if ((i&1) == 1) {
res *= base;
}
base *= base;
}
if (exponent < 0) {
res = 1 / res;
}
return res;
}
} 复杂度分析：
时间复杂度O(logN)：N为exponent
空间复杂度O(1)：常数空间