C++斩题录|递归专题 | leetcode50. Pow(x, n)

个人主页：平行线也会相交
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

一、题目描述

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

示例一：

输入：x = 2.00000, n = 10
输出：1024.00000

示例二：

输入：x = 2.10000, n = 3
输出：9.26100

示例三：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

二、解题思路

我们本题使用递归思想来解决问题。

解题过程分为3个步骤：① 相同子问题（确定函数头是什么）、② 明确每个子问题在做些什么、③ 考虑递归出口（当n等于0的时候）。

解题思路：在pow函数中，首先判断n是否等于0，如果是，则返回1.0，因为任何数的0次幂都等于1.0。 然后，计算tmp为pow(x, n / 2)，即x的n/2次幂。这一步使用递归来计算较小的次幂。 接着，判断n是否为偶数，如果是偶数，则返回tmp的平方，即tmp * tmp。如果n为奇数，则返回tmp的平方再乘以x，即tmp * tmp * x。

注意细节问题：在本题中主要有两个细节问题，第一点就是n为的负数的时候，第二点就是一定要注意n的取值范围。

最后我们根据细节问题进行一定的特殊处理即可（比如n为负数时，我们需要把n强转为long long类型）。

三、解题代码

class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
    }

    double pow(double x,long long n){
        if(n == 0) return 1.0;
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

最后就通过啦：