Leetcode 50. Pow(x, n)( 分治递归避免傻乘，注意溢出)

妖狐艹你老母 2022-08-31 00:50 41阅读 0赞

#### 题目重述 ####

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

##### 示例 1： #####

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

##### 示例 2： #####

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

##### 示例 3： #####

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

提示：

\-100.0 < x < 100.0  
\-231 <= n <= 231-1  
\-104 <= xn <= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/powx-n  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路实现 ####

本题的暴力解法是n个x循环相乘，我们可以利用分治法 去递归，能够减少乘的次数，从而提高时间复杂度。

但注意一定要用long去接一下int，即把n转成long

这是因为当n为Integer,MIN\_VALUE(-2147483648)时候, 去调用-n会变成2147483648，也就是-2147483648, 不断地调用，那么就会溢出

#### Java实现 ####

class Solution {
        
        public double myPow(double x, int n) {
        
            long ln = n;
            return pow2(x,ln);
        }
        public double pow2(double x ,long n)
        {
        
            if(n == 0)
            {
        
                return 1;
            }
            if(n == 1)
            {
        
                return x;
            }
            // 考虑负数
            if(n < 0)
            {
        
                return 1/pow2(x,-n);
            }
            // 偶数
            if(n%2==0)
            {
        
                return pow2(x*x,n/2);
            }
            return x * pow2(x,n-1);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关递归求n的阶乘

求n的阶乘(不考虑溢出) 递归思路： 1的阶乘还是1。而n的阶乘是 n\(n-1) \ (n-1-1)……2 \1 所有的阶乘都会乘到1这个数 ![在这里插

爱被打了一巴掌/ 2024年04月06日 11:42/ 0 赞/ 142 阅读

相关 LeetCode:50. Pow(x, n)(快速幂+递归)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。示例 1： > 输入：x = 2.00000, n = 10 > 输出：1024.0000

àì夳堔傛蜴生んèń/ 2024年04月03日 11:43/ 0 赞/ 102 阅读

相关 Java实现：计算n的阶乘（递归、分治法）

Java实现：计算n的阶乘n! （递归）（分治法）文章目录 Java实现：计算n的阶乘n! （递归）（分治法） 1. 问题 2.

偏执的太偏执、/ 2024年03月31日 15:53/ 0 赞/ 117 阅读

相关 C语言实现：计算n的阶乘（递归、分治法）

C语言实现：计算n的阶乘n! （递归）（分治法）文章目录 C语言实现：计算n的阶乘n! （递归）（分治法） 1. 问题 2. 解决

灰太狼/ 2024年03月31日 15:46/ 0 赞/ 125 阅读

相关 LeetCode_快速幂_递归_中等_50.Pow(x, n)

目录 1.题目 2.思路 3.代码实现（Java） 1.题目实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。示

╰+哭是因爲堅強的太久メ/ 2023年10月06日 23:02/ 0 赞/ 52 阅读

相关【递归】 LeetCode51. N皇后

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

分手后的思念是犯贱/ 2022年12月03日 05:21/ 0 赞/ 244 阅读

相关 Leetcode 50. Pow(x, n)( 分治递归避免傻乘，注意溢出)

题目重述实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。示例 1：输入：x = 2.00000, n = 10 输出：1024.0

妖狐艹你老母/ 2022年08月31日 00:50/ 0 赞/ 42 阅读

相关 N的阶乘递归算法

> /\\ > > \ N 的阶乘递归算法 > > \ @param n(int型的整数) > > \/ > > public static int digui(int

古城微笑少年丶/ 2022年05月17日 03:06/ 0 赞/ 285 阅读

相关递归求N的阶乘

递归计算N的阶乘以下为源代码： include<stdio.h> include<iostream> using namespace st

偏执的太偏执、/ 2022年05月03日 11:58/ 0 赞/ 363 阅读

相关递归方法求n!阶乘

递归的定义：在定义一个过程或函数时，出现调用本过程或者是本函数的成分，称之为递归。通常需要用到递归的方法： 1. 定义是递归的。（例如n!,Fibonacci数列问题）

朴灿烈づ我的快乐病毒、/ 2022年03月15日 15:19/ 0 赞/ 366 阅读