Day30 Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）

https://leetcode-cn.com/problems/powx-n/

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

Java解法

思路：

• 先是一个个累乘超时，后面考虑使用递归，省去重复计算 如2^5 = 2^2*22*2

package sj.shimmer.algorithm.ten_3;

/**
 * Created by SJ on 2021/2/23.
 */

class D30 {
    public static void main(String[] args) {
        System.out.println(myPow(-2.00000 ,2));
        System.out.println(myPow(2.0000, -2));
        System.out.println(myPow(2.0000, 10));
        System.out.println(myPow(2.1000, 3));
        System.out.println(myPow(1, 2147483647));
    }

    public static double myPow(double x, int n) {
        if (x==1) {
            return 1;
        }
        if (x==-1) {
            if (n%2==0) {
                return 1;
            }
            return -1;
        }
        if (x == 0) {
            return 0;
        }
        if (n == 0) {
            return x > 0 ? 1 : -1;
        }
        if (n == 1) {
            return x;
        }
        if (n == -1) {
            return 1/x;
        }
        boolean isPostive = n>0;
        int spilt = n / 2;
        double temp = myPow(x, spilt);
        double single = 1;
        if (n % 2!=0) {
           single =  myPow(x, n % 2);
        }
        x = temp*temp * single;

        return x;
    }
}

image

官方解

https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

1. 快速幂 + 递归

   思路差不多，但写法优雅

   public double quickMul(double x, long N) {
       if (N == 0) {
           return 1.0;
       }
       double y = quickMul(x, N / 2);
       return N % 2 == 0 ? y * y : y * y * x;
   }
   
   public double myPow(double x, int n) {
       long N = n;
       return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
   }
   

   • 时间复杂度：O(logn)
   • 空间复杂度：O(logn)

2. 快速幂 + 迭代

   比较难理解，后续再来啃啃