☆打卡算法☆LeetCode 50、Pow(x, n) 算法

发表于

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“实现函数，计算x的n次幂。”

题目链接：

来源：力扣（LeetCode）

链接：50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

1
2
3
ini复制代码示例 1：
输入： x = 2.00000, n = 10
输出： 1024.00000
1
2
3
ini复制代码示例 2：
输入： x = 2.10000, n = 3
输出： 9.26100

二、解题

1、思路分析

这道题可以使用快速幂+递归的方法解题。

快速幂算法，本质就是分治算法，将大问题分解成小问题，然后递归解决。

快速幂算法：

比如要计算x8，可以按照x → x2 → x4 → x8的顺序，从x开始，每次将上一次的结果进行平方，3次后就可以得到x8的结果，而不需要对x乘8次x。

如果幂是偶数，比如x9，可以按照x → x2 → x4 → x9的顺序，这些步骤中，还是按照将上一次结果平方，而在x4 → x9的步骤中，需要将上一个结果进行平方，还需要额外乘一个x。

综上所述，可以推到出规律，如果要计算xn，首先判断n的奇偶：

  • n为偶数，那么xn=yn
  • n为奇数，那么xn=yn * x

接着就可以递归地得到结果了。

2、代码实现

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
csharp复制代码public class Solution {
    //递归
    public double MyPow(double x, int n) {
        return (n >= 0) ? res(x, n) : 1 / res(x, n);
    }
    private double res(double x, int n)
    {
        if(n == 0)
            return 1;
        double y = res(x, n / 2);
        return (n % 2 == 0) ? y * y :y * y * x;
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(log n)

其中n为遍历的层数。

空间复杂度： O(log n)

其中n为遍历的层数。

三、总结

这道题还有更秀的一行解题法：

1
2
3
4
5
csharp复制代码public class Solution {
    public double MyPow(double x, int n) {
        return Math.Pow(x,n);
    }
}

是不是秀的头皮发麻。。。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%