剑指 Offer 16. 数值的整数次方
摘要
剑指 Offer 16. 数值的整数次方
本题的方法被称为快速幂算法,有递归和迭代两个版本。这篇题解会从递归版本的开始讲起,再逐步引出迭代的版本。当指数n为负数时,我们可以计算 x^(-n)再取倒数得到结果,因此我们只需要考虑n为自然数的情况。
一:快速幂 + 递归
快速幂算法的本质是分治算法。举个例子,如果我们要计算x^64,我们可以按照:
的顺序,从x开始,每次直接把上一次的结果进行平方,计算6次就可以得到 x^(64)的值,而不需要对 x乘 63次x。再举一个例子,如果我们要计算 x^77,我们可以按照:
的顺序,在 x→x^2,x2→x^4,x19→x^38 这些步骤中,我们直接把上一次的结果进行平方,而在 x4→x^9,x9→x19,x38→x77这些步骤中,把上一次的结果进行平方后,还要额外乘一个 x。直接从左到右进行推导看上去很困难,因为在每一步中,我们不知道在将上一次的结果平方之后,还需不需要额外乘 xx。但如果我们从右往左看,分治的思想就十分明显了:
- 当我们要计算 x^n时,我们可以先递归地计算出 y=x⌊n/2⌋,其中⌊a⌋表示对a进行下取整;
- 根据递归计算的结果,如果 n为偶数,那么 x^n=y^2;如果n为奇数,那么 x^n=y^2×x;
- 递归的边界为n=0,任意数的0次方均为1。
由于每次递归都会使得指数减少一半,因此递归的层数为 O(logn),算法可以在很快的时间内得到结果。
class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}
}
复杂度分析
- 时间复杂度:O(logn),即为递归的层数。
- 空间复杂度:O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。
二、快速幂 + 迭代
由于递归需要使用额外的栈空间,我们试着将递归转写为迭代。在方法一中,我们也提到过,从左到右进行推导是不容易的,因为我们不知道是否需要额外乘x。但我们不妨找一找规律,看看哪些地方额外乘了x,并且它们对答案产生了什么影响。
class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1,那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可N /= 2;}return ans;}
}
复杂度分析
-
时间复杂度:O(logn),即为对n进行二进制拆分的时间复杂度。
-
空间复杂度:O(1)。
博文参考
《leetcode》
相关文章:

剑指 Offer 16. 数值的整数次方
摘要 剑指 Offer 16. 数值的整数次方 本题的方法被称为快速幂算法,有递归和迭代两个版本。这篇题解会从递归版本的开始讲起,再逐步引出迭代的版本。当指数n为负数时,我们可以计算 x^(-n)再取倒数得到结果,因此我们只需要考虑n为…...

在苹果电脑 mac 上安装原神(playCover)
该方法只能在 M1、M2 mac 上安装原神 目录前言一、首先下载安装 playCover1. playCover 下载2. playCover 安装安装出现问题解决方法二、下载安装原神1.安装包下载2.安装原神三、登录、键盘映射及版本更新等问题登录键盘映射版本更新前言 最近买了新的mac,作者本人…...

数据结构考研习题精选
1 A假设比较t次,由于换或不换,则必然有2^t种可能。又设有n个关键字,n!排列组合,则必然有2^t&…...

linux常用命令介绍 04 篇——uniq命令使用介绍(Linux重复数据的统计处理)
linux常用命令介绍 04 篇——uniq命令使用介绍(Linux重复数据的统计处理)1. uniq 使用语法2. sort 简单效果3. uniq 使用例子3.1 不加任何选项3.1.1 不用 sort 效果3.1.2 uniq 结合 sort 一起使用3.2 使用选项例子3.2.1 去重打印(或打印不重复…...

网站打不开数据库错误等常见问题解决方法
1、“主机开设成功!”上传数据后显示此内容,是因为西部数码默认放置的index.htm内容,需要核实wwwroot目录里面是否有自己的程序文件,可以删除index.htm。 2、恭喜,lanmp安装成功!这个页面是wdcp的默认页面&…...

爬虫实战进阶版【1】——某眼专业版实时票房接口破解
某眼专业版-实时票房接口破解 某眼票房接口:https://piaofang.maoyan.com/dashboard-ajax 前言 当我们想根据某眼的接口获取票房信息的时候,发现它的接口处的参数是加密的,如下图: 红色框框的参数都是动态变化的,且signKey明显是加密的一个参数。对于这种加密的参数,我们需要…...

大话数据结构-普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)
5 最小生成树 构造连通网的最小代价生成树称为最小生成树,即Minimum Cost Spanning Tree,最小生成树通常是基于无向网/有向网构造的。 找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。 5.1 普里姆ÿ…...

UNet-肝脏肿瘤图像语义分割
目录 一. 语义分割 二. 数据集 三. 数据增强 图像数据处理步骤 CT图像增强方法 :windowing方法 直方图均衡化 获取掩膜图像深度 在肿瘤CT图中提取肿瘤 保存肿瘤数据 四. 数据加载 数据批处理 编辑编辑 数据集加载 五. UNet神经网络模型搭建 单张图片…...

三周爆赚千万 电竞选手在无聊猿游戏赢麻了
如何用3个星期赚到1千万?普通人做梦都不敢想的事,电竞职业选手Mongraal却用几把游戏轻易完成,赚钱地点是蓝筹NFT项目Bored Ape Yacht Club(BAYC无聊猿)出品的新游戏Dookey Dash。 这款游戏类似《神庙逃亡》࿰…...

BERT学习
非精读BERT-b站有讲解视频(跟着李沐学AI) (大佬好厉害,讲的比直接看论文容易懂得多) 写在前面 在计算MLM预训练任务的损失函数的时候,参与计算的Tokens有哪些?是全部的15%的词汇还是15%词汇中真…...

大话数据结构-图的深度优先遍历和广度优先遍历
4 图的遍历 图的遍历分为深度优先遍历和广度优先遍历两种。 4.1 深度优先遍历 深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS,深度优先遍历,是指从某一个顶点开始,按照一定的规…...

c语言指针怎么理解 第一部分
不理解指针,是因为有人教错了你。 有人告诉你,指针是“指向”某某某的,那就是误导你,给你挖了个坑。初学者小心不要误读这“指向”二字。 第一,“指针”通常用于保存一个地址,这个地址的数据类型在定义指…...

计算机网络安全基础知识2:http超文本传输协议,请求request消息的get和post,响应response消息的格式,响应状态码
计算机网络安全基础知识: 2022找工作是学历、能力和运气的超强结合体,遇到寒冬,大厂不招人,可能很多算法学生都得去找开发,测开 测开的话,你就得学数据库,sql,oracle,尤…...

Pytest自动化框架~权威教程03-原有TestSuite的执行方法
前言TestSuite一直是unittest的灵活与精髓之处, 在繁多的测试用例中, 可以任意挑选和组合各种用例集, 比如smoke用例集, level1用例集, webtest用例集, bug回归用例集等等, 当然这些TestSuite需要我们提前定义好, 并把用例加载进去.Pytest采取的是完全不同的用例组织和运行方式…...

web自动化 基于python+Selenium+PHP+Ftp实现的轻量级web自动化测试框架
1、 开发环境 win7 64 PyCharm 4.0.5 setuptools-29.0.1.zip 下载地址:setuptools-29.0.1.zip_免费高速下载|百度网盘-分享无限制 官方下载地址:setuptools PyPI python 3.3.2 mysql-connector-python-2.1.4-py3.3-win64 下载地址:mysq…...

【MyBatis】源码学习 05 - 关于 xml 文件解析的分析
文章目录前言参考目录学习笔记1、章节目录概览2、14.3:SqlSourceBuilder 类与 StaticSqlSource 类3、14.4.2:ResultMapResolver 类3.1、测试代码说明3.2、结果集 userMap 解析流程3.3、结果集 getGirl 解析流程3.4、鉴别器 discriminator 解析流程4、14.…...

代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小子数组、59.螺旋矩阵II
977 有序数组的平方题目链接:977 有序数组的平方介绍给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。思路看到题目的第一反应,首先负数的平方跟正数的平方是相同的&…...

Ethercat系列(10)用QT实现SOEM主站
首先将SOEM编译成静态Lib库可以参考前面的博文(83条消息) VS2017下编译SOEM(Simle Open EtherCAT Master)_soem vs_CoderIsArt的博客-CSDN博客make_libsoem_lib.bat "C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Auxiliary\Build" x86用QT创建…...

论文投稿指南——中文核心期刊推荐(科学、科学研究)
【前言】 🚀 想发论文怎么办?手把手教你论文如何投稿!那么,首先要搞懂投稿目标——论文期刊 🎄 在期刊论文的分布中,存在一种普遍现象:即对于某一特定的学科或专业来说,少数期刊所含…...
jQuery属性操作prop()、attr()和data()
jQuery 提供了一些属性操作的方法,主要包括 prop()、attr() 和 data() 等。通过这些方法,能够实现不同的需求。下面我们分别进行详细讲解。 1.prop() 方法 prop0 方法用来设置或获取元素固有属性值。元素固有属性是指元素本身自带的属性,如 …...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...