2021.10.11 - JZ16.数值的整数次方

文章目录

1. 题目

2021.10.11 - JZ16.数值的整数次方

2. 思路

(1) 模拟法

  • 模拟n个x相乘的过程,时间复杂度较高。

(2) 快速幂

  • 当求x的n次方时,若n为偶数,则x的n次方等于两个x的n/2次方相乘;若n为奇数,则x的n次方等于两个x的(n-1)/2次方相乘再乘以x。如x的16次方等于x的8次方乘以x的8次方,x的15次方等于x的7次方乘以x的7次方乘以x。
  • 利用右移运算代替除以2,利用与运算代替判断奇偶性,利用递归实现快速幂。

3. 代码

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public double myPow(double x, int n) {
        if (x == 1 || n == 0) {
            return 1;
        }
        if (x == -1) {
            return (n & 1) == 0 ? 1 : -1;
        }
        long nl = n;
        if (n < 0) {
            x = 1 / x;
            nl = -nl;
        }
        double res = 1.0;
        while (nl > 0) {
            res = res * x;
            if (res == 0) {
                return 0;
            }
            nl--;
        }
        return res;
    }
}

class Solution1 {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }
        long nl = n;
        if (n < 0) {
            x = 1 / x;
            nl = -nl;
        }
        return myPow(x, nl);
    }

    private double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        double pre = myPow(x, n >> 1);
        pre *= pre;
        if ((n & 1) == 1) {
            pre *= x;
        }
        return pre;
    }
}
上一篇:50. Pow(x, n)


下一篇:剑指 Offer 16. 数值的整数次方