50. Pow(x, n)

题目描述

链接: https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode/
实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 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

二分快速幂

• 递归版本
  注意点: 需要提前判断n是否小于0, 如果小于0, 则需要1 / res.
  思路:
  a是偶数次: x^a = x^(a/2) * x^(a/2)
  a是奇数次: x^a = x^(a/2) * x^(a/2) * a
  但x ^ 0 = 1, 所以可以直接用递归进行求解.

  class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            return 1.0 / fastPow(x, -n);
        } else {
            return fastPow(x, n);
        }
    }
  
    public double fastPow(double x, int n) {
        if (n == 0) return 1.0;
        double temp = myPow(x, n/2);
        temp = temp * temp;
        if (n % 2 == 1) {
            temp = temp * x;
        }
        return temp;
    }
  }

• 循环版本
  循环版本利用二进制进行分解, 如11 -> 1011, 1^1 * 2^1 * 8^1

  class Solution {
    public double myPow(double x, int n) {
        long N = Math.abs((long) n);
        double result = 1.0;
        while (N != 0) {
            if ((N & 1) == 1) result *= x;
            x *= x;
            N >>= 1;
        }
        return n < 0 ? 1/result : result;
    }
  }