leetcode-数值的整数次方

刷leetcode《剑指offer》中第十五题"数值的整数次方"，以下记录解题思路。

题目

实现函数double Power(double base, int exponent)，求base的exponent次方。
不得使用库函数，同时不需要考虑大数问题。

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

解析

1. 快速幂法，利用分治法，将n次方分两部分，不断分。

2. 利用右移，不断累乘。

注意

1. 右移过程记得防止整数溢出。
2. 将n划分时候，需要分为偶数奇数，还有正负数。

具体代码实现

第一种方法

class Solution {
   public double myPow(double x, int n) {
       // 底数为0
       if (x == 0) {
            return 0;
        }
       // n为正数
        if (n > 0) {
            return power(x, n);
        }
       // n为负数
        return power(1 / x, -n);
    }

    private double power(double x, int n) {
        // 当n为0
        if (n == 0) {
            return 1;
        }
        // 将n划分两部分
        double r = power(x, n / 2);
        // 判断n是否为奇数，奇数需要多乘一个x
        // 可改为 n&1 == 1
        if (n > 0 ? n % 2 == 1 : (-n) % 2 == 1) {
            return r * r * x;
        } else {
            // 偶数不需要多乘底数
            return r * r;
        }
    }
}

第二种方法

class Solution {
   public double myPow(double x, int n) {
        long n_copy = n;
        // n为负数
        if (n_copy < 0) {
            x = 1 / x;
            n_copy *= -1;
        }
        double result = 1;
        // 进行乘于自身操作
        while (n_copy > 0) {
            // n为奇数
            if (n_copy % 2 == 1) {
                result *= x;
            }
            x *= x;
            n_copy /= 2;
        }
        return result;
   }
}