《剑指 Offer 》—16. 数值的整数次方

《剑指 Offer 》—16. 数值的整数次方

一、题目内容

原题连接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/

题目：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。。

二、个人答案（错误，仅做个人笔记）

超出时间限制（for循环）：

class Solution {
    public double myPow(double x, int n) {
if (n>0){
            double a=x;
            for (int i = n; i >1; i--) {
                x=x*a;
            }
            return x;
        }else if (n==0){
            return 1;
        }else if(n<0){
            double a=x;
            for (int i = -n; i >1; i--) {
                x=x*a;
            }
            return 1/x;
        }
return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

超出时间限制（递归+BigDecimal类）：

import java.math.BigDecimal;
class Solution {
    public double myPow(double x, int n) {
BigDecimal b = BigDecimal.valueOf(x);
        if (n>0){
            BigDecimal dg = dg(b, n);
            double v = dg.doubleValue();
            return v;
        }else if (n==0){
            return 1;
        }else if(n<0){
            BigDecimal dg = dg(b, -n);
            double v = dg.doubleValue();
            return 1/v;
        }
        return 0;
    }
public static BigDecimal dg(BigDecimal b,int n){
        if (n==1){
            return b;
        }else {
            return b.multiply(dg(b, n - 1));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

执行出错（java.lang.StackOverflowError）：

class Solution {
    public double myPow(double x, int n) {
if (n>0){
            double dg = dg(x, n);
            return dg;
        }else if (n==0){
            return 1;
        }else if(n<0){
            double dg = dg(x, -n);
            return 1/dg;
        }
        return 0;
    }

public static double dg(double s,int n){
        if (n==1){
            return s;
        }else {
            return s*dg(s,n-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、官方答案（Java）

官方解释见：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solutions/1398793/shu-zhi-de-zheng-shu-ci-fang-by-leetcode-yoqr/

这里只放代码：

方法一：快速幂 + 递归

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：快速幂 + 迭代

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

四、评论区答案（Java）

class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1 / x;
        double half = myPow(x, n / 2);
        double mod = myPow(x, n % 2);
        return half * half * mod;
    }
}
1
2
3
4
5
6
7
8
9
10