专栏首页五分钟学算法这道题可太帅了!

这道题可太帅了!

今天是旅游回来的帅吴:)

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题16 . 数值的整数次方

一、题目描述

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

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

第一想法就是利用循环,将 n 个 x 连乘起来立马得到答案,比如 x = 2,n = 11,需要进行 11 次循环的乘法,但基于这种做法实现的代码一提交显示超时,所以我们考虑的方向就是如何缩减计算的次数

当计算到 25 时,它的结果进行平方操作即可得到 210 ,相比较于 25 * (2 * 2 * 2 * 2 * 2)减少了 4 次运算。

面试题 16.数值的整数次方.003

面试题 16.数值的整数次方.005

即 211 = 25 * 25 * 2。

2、规律

如果 n 为奇数,最终结果为 x * xn - 1

如果 n 为偶数,最终结果为 x2 * (n/2)

3、匹配

递归。

4、边界

当 n = 0 时,返回 1。

当 n < 0 时,返回 1/ x-n

同时,Java 代码中 int32 变量的范围是 [−2147483648,2147483647],当n = -2147483648,取绝对值为 2147483648 会发生越界的情况,为避免越界提取一个 x ,把 xn 变成了 x * xn-1,即将 n 变成了 n - 1,这样取绝对值是不会越界。

三、动画描述

四、图片描述

面试题 16.数值的整数次方新.002

面试题 16.数值的整数次方新.003

面试题 16.数值的整数次方新.004

面试题 16.数值的整数次方新.005

面试题 16.数值的整数次方新.006

面试题 16.数值的整数次方新.007

面试题 16.数值的整数次方新.008

面试题 16.数值的整数次方新.009

面试题 16.数值的整数次方新.010

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public double myPow(double x, int n) {
        //当 n = 0 时,返回 1
        if(n == 0){
            return 1;
        }else if(n < 0){
            // 当 n < 0 时,返回 1/ x^-n
            return 1 / (x * myPow(x, - n - 1));
        }else if(n % 2 == 1){
            //为避免越界,提取 x
            return x * myPow(x, n - 1);
        }else{
            return myPow(x * x, n / 2);
        }     
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(logN)。

空间复杂度

空间复杂度为 O(logN)。

七、相关标签

  • 递归

以上就是本期全部内容,你学会了么?我是帅吴,一个用动画刷题的程序员,下期见!

前不久我加了一个群,里面有帅张、帅地、帅北,他们觉得我长得也挺帅的

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:今天是帅吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 这个程序员实在是太帅了

    提起 Linus Torvalds 大家的第一反应是怎样的?是严苛刻薄,还是神级伟大,亦或是孤傲清高?但是他也是“Linux之父”。二十五年来,Linus To...

    IT大咖说
  • 这么帅的 Linux 隧道网络形象大使,VXLAN 太厉害了!

    VXLAN(Virtual eXtensible Local Area Network,虚拟可扩展局域网),是一种虚拟化隧道通信技术。它是一种 Overlay(...

    米开朗基杨
  • 这道算法题太太太太太简单啦

    题目来源于 LeetCode 上第 268 号问题:缺失数字。题目难度为 Easy,目前通过率为 50.2% 。

    五分钟学算法
  • Mysql调优你不知道这几点,就太可惜了

    ​ 1、客户端端与Mysql服务端的连接层建立连接,根据请求类型去选择相应的服务层的请求接口。

    TrueDei
  • 这摩托车太帅了,还是一个购物机器人?

    据外媒报道,日本千叶工业大学研发出了可变形为小型摩托车的机器人“CanguRo”,可以识别人类并跟随行动,还可以自动行驶到指定场所。

    机器人网
  • 别看了,这 17 道面试题因为太难被Google禁用了!

    即使是最成功的公司,它的招聘过程有时也会很不靠谱,经常会出一些奇怪的看似没有答案的面试问题,但标准答案却让应聘者还没来得及接近「起跑线」就被「退赛」了。Goog...

    昱良
  • 这个机器人太可爱了

    第一法则:机器人不得伤害人类,或坐视人类受到伤害; 第二法则:除非违背第一法则,机器人必须服从人类的命令; 第三法则:在不违背第一及第二法则下,机器人必须保护自...

    前朝楚水
  • 如何理解二分查找?生活中还能用来设计骗局?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 一段对话讲完建造者模式

    截止今天,小秋学习Java刚刚满三个月。此刻的小秋感觉自己Java学的还不错,想去帅地面前炫耀一番,于是,就发生了一下一番对话…..

    帅地
  • 这波太炸了!Python脚本可视化居然可以这么玩!

    如同艺术家们用绘画让人们更贴切的感知世界,数据可视化也能让人们更直观的传递数据所要表达的信息。你知道Python脚本可视化有多好看么?就像下图这样,是不是感觉十...

    昱良
  • 高频面试题:什么是B树?为啥文件索引要用B树而不用二叉查找树?

    小秋:树形结构例如想 B 树,B+ 树,二叉查找树都是有序的,所以查询效率很高,可以再 O(logn) 的时间复杂度查找到目标数据。

    帅地
  • 高频面试题:什么是B树?为啥文件索引要用B树而不用二叉查找树?

    小秋:树形结构例如想 B 树,B+ 树,二叉查找树都是有序的,所以查询效率很高,可以再 O(logn) 的时间复杂度查找到目标数据。

    乔戈里
  • 这道算法题太简单?你忽略了时间复杂度的要求!

    忽略时间复杂度的要求的话,so easy !加上了时间复杂度的要求,so hard!

    五分钟学算法
  • 8月反思

    这个月的感受非常不同,虽然大熊市已经持续了半年了,但因为8月份的经历很不一样,让我在区块链行业的飞奔中慢了下来,有更多时间思考和审视自己。

    凌帅出口
  • ❗ 帅小伙花了一个小时,竟把图书馆智慧大屏模仿的有模有样!妙啊~

    帅小伙去图书馆划水,进门的时候被图书馆门口的大屏震惊了,这玩意我也会哈哈哈哈,于是就给它拿下!结果,帅小伙在写博客的时候发现,照片上刚好有帅小伙的名字,帅小伙直...

    小丞同学
  • 大数据告诉你:如何在魔都捕获一只活的高富帅?

    作者:团支书   数据及算法支持:城市数据团   友情数据支持:TalkingData   考上市里的公务员后,学姐的人生目标已完成大半。但一直以来...

    CDA数据分析师
  • 看美女如何利用大数据:在魔都捕获一只活的高富帅?

    考上市里的公务员后,学姐的人生目标已完成大半。但一直以来,她还有一个更为伟大的愿望:嫁入豪门,一步登天。但这个愿望似乎比考公务员更难实现。我经常听到她的抱怨:

    华章科技
  • 我太难了!这些面试问题你遇到了吗?

    传统项目若不是sass这种的,给企业来应用,用户一般在1000左右,并发的话很少出现,一般通过redis缓存、线程这些就可以处理。

    夕梦
  • 从白富美相亲名单看特征选择与预处理(上)

    作者:龙心尘 &&寒小阳 出处: http://blog.csdn.net/longxinchen_ml/article/details/50471682 ...

    机器学习AI算法工程

扫码关注云+社区

领取腾讯云代金券