leetcode算法题--数值的整数次方

原题链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/?envType=study-plan-v2&envId=coding-interviews

使用快速幂算法

1、递归写法

func myPow(x float64, n int) float64 {
    if n >= 0 {
        return dfs(x, n)
    }
    return 1.0 / dfs(x, -n)
}

func dfs(x float64, n int) float64 {
    if n == 0 {
        return 1.0
    }
    r := dfs(x, n/2)
    if n%2 == 1 {
       return r * r * x 
    }
    return r * r
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

迭代写法

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1 
    }
    m := n
    if n < 0 {
       m = -1 * n 
    }
    var res float64 = 1 
    c := x
    for m > 0 {
        if m % 2 == 1 {
            res *= c 
        }
        c *= c 
        m /= 2
    }
    if n < 0 {
        res = 1 / res
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22