badEgg > leetcode - Pow(x, n)

leetcode - Pow(x, n)

2020-01-06

算法, leetcode

leetcode: Pow(x, n)

实现 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

首先，我们就试试暴力破解

出错了，卡在了测试样例0.00001 2147483647

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """

        if n < 0:
            x = 1 / x
            n = -n
        temp = 1
        for i in range(n):
            temp = temp * x
        
        return temp

为什么，内存错误（溢出），这个数字太小了，想想溢出才是正常的吧

1
2
def myPow(self, x: float, n: int) -> float:
    return x**n

差点忘了python可以直接求幂啊。

然后看看题解的快速幂方法，我记得洛谷好像空耳为卡速米

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double fastPow(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
};

通过不断分解幂达到快速计算幂的效果

放假啦，回家啦，不想回家啊艹

想去实习下学期又有课，想做项目又没有路子，脑壳疼，还是再闲两天吧，学学日语，看看要不要考个教师资格证，当老师其实也挺好。压力不大还能余一点时间学代码。

不想这么多了，收拾收拾回家了= =