[Leetcode] Pow(x, n) 实现乘方函数

mating 发布于2019-08-14 12:32 / 563人阅读

摘要：递归法复杂度时间空间思路通过一点点数学推导我们可以知道，如果是偶数如果是奇数根据这几条原则递归，我们就不用将相乘次，而只要次就行了注意在递归函数中处理的奇偶问题，在主函数中处理的正负问题代码为负返回倒数为正直接返回结果递归终止条件根据奇数

Pow(x, n)

Implement pow(x, n)

递归法 复杂度

时间 O(logN) 空间 O(logN)

思路

通过一点点数学推导我们可以知道，如果n是偶数
$$ x^nx^n = x^{2n}$$
如果n是奇数
$$ x^nx^nx = x^{2n+1}$$
根据这几条原则递归，我们就不用将x相乘n次，而只要logN次就行了

注意

在递归函数中处理n的奇偶问题，在主函数中处理n的正负问题

代码

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
        // n为负返回倒数
            return 1/pow(x, -n);
        } else {
        // n为正直接返回结果
            return pow(x, n);
        }
    }
    
    private double pow(double x, int n){
        // 递归终止条件
        if(n == 0){
            return 1.0;
        } 
        if(n == 1){
            return x;
        }
        double val = pow(x, n/2);
        // 根据奇数还是偶数返回不同的值
        if(n % 2 == 0){
            return val * val;
        } else {
            return val * val * x;
        }
    }
}

云服务器 GPU云服务器虚函数实现原理 POW asp pow() LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64543.html

Python强大的语法支持

摘要：浮点数计算不光对整数运算提供了支持，同样对我们俗称的小数也提供了便利的运算。但要注意的一点是有些版本对于浮点数是位数限制的对比下面两张图，所以可能会出现溢出或者未知报错，在真正开发的过程中，尽量不要写这种代码否则背锅。学习任何一种编程语言，包括但不限于C、C++、Java、Python，我...

adie 2021-11-25 09:43 评论0 收藏0
Python基础之(五)语句

摘要：逻辑运算符假设，运算符描述实例布尔与如果为，返回，否则它返回的计算值。布尔或如果是，它返回，否则它返回的计算值。以为例，说明语句。逗号表示打印在同一行本来，在语句中，字符串后面会接一个符号。运算符算术运算符前面已经讲过了四则运算，其中涉及到一些运算符：加减乘除，对应的符号分别是：+ - * /，此外，还有求余数的：%。这些都是算术运算符。其实，算术运算符不止这些。根据中学数...

alaege 2019-07-25 10:53 评论0 收藏0
leetcode50 Pow(x, n)自定义实现指数运算

摘要：题目要求此处为题目链接即用自己的代码实现指数运算。指数为负数即求其倒数。思路一二分法计算这题的思路我之前的一篇博客思路基本相同。所以在能转换为循环的情况下还是最好使用循环来解决。题目要求此处为题目链接即用自己的代码实现指数运算。指数运算一般有两种情况，即指数为整数和指数为负数的情况。指数为负数即求其倒数。思路一：二分法计算这题的思路我之前的一篇博客思路基本相同。有兴趣的可以直接...

DoINsiSt 2019-08-16 10:32 评论0 收藏0
小李飞刀：leetcode我又来啦~

摘要：在拖完地板之后，想想还是补上今天的题解吧感谢小佳扬推荐的题目，默默的复习了一把递归第一题难度中等实现，即计算的次幂函数。因为是次幂，如果直接循环，复杂度就是了。次幂可以拆解为的方式。每次拆解，最后最小的单位应该为。写在前面年前嘛，就是各种涣散的状态。在拖完地板之后，想想还是补上今天的题解吧~感谢小佳扬推荐的题目，默默的复习了一把递归~ 第一题 50. Pow(x, n)难度：中等 ...

zhangxiangliang 2019-07-31 10:02 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0