当前位置: 首页 > news >正文

【面试经典150 | 数学】Pow(x, n)

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:快速幂-递归
    • 方法二:快速幂-迭代
  • 其他语言
    • python3
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【快速幂】


题目来源

50. Pow(x, n)


题目解读

计算一个数的整数次幂。


解题思路

计算一个数的整数次幂有朴素的方法和二分的方法,朴素的方法就是一个一个的乘起来,时间复杂度为 O ( n ) O(n) O(n) n n n 指的是幂指数。接下来要介绍的是二分法,即快速幂,有递归和迭代两种解法。建议读者掌握快速幂的方法,该方法是一些题目计算的一个重要工具。

方法一:快速幂-递归

写递归代码的一个重要思想,坚信自己写的递归就是对的,可以直接调用。用快速幂求解一个数的整数次幂是一种二分的递归,比如我们要计算 x n x^n xn 时:

  • 我们可以先递归的计算 y = x ⌊ n / 2 ⌋ y = x^{\lfloor{n / 2} \rfloor} y=xn/2
  • 如果 n 是偶数,那么 x n = y 2 x^n=y^2 xn=y2;如果 n n n 是奇数,那么 x n = y 2 × x x^n=y^2 \times x xn=y2×x;
  • 递归的边界(递归出口)为 n = 0,因为任意数的 0 次方均为 1

实现代码

class Solution {
public:double quickMul(double x, long long N) {if (N == 0) return 1.0;double y = quickMul(x, N/2);return N & 1 ? y * y * x : y * y;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};

复杂度分析

时间复杂度: O ( l o g n ) O(logn) O(logn) n n n 为幂指数。因为每次递归都会使指数减少一半,因此递归的层数为 O ( l o g n ) O(logn) O(logn),时间复杂度也为 O ( l o g n ) O(logn) O(logn)

空间复杂度: O ( l o g n ) O(logn) O(logn)

方法二:快速幂-迭代

在完全理解了递归的思想后,会发现递归真简单,但是完全理解递归之前还是觉得迭代简单容易理解。现在就来看看迭代解法。

我们依旧是使用二分来计算幂:

  • 如果指数为奇数,则累乘答案,即 res *= x
  • 然后更新 x *= x
  • 最后返回 res 即可。

实现代码

class Solution {
public:double quickMul(double x, long long n) {double res = 1.0;for (; n; n /= 2) {if (n & 1) {res *= x;}x *= x;}return res;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};

复杂度分析

时间复杂度: O ( l o g n ) O(logn) O(logn) n n n 为幂指数。

空间复杂度: O ( 1 ) O(1) O(1)


其他语言

python3

在 Python 中,可以使用内置的 pow 函数来进行快速幂的计算。pow 函数的签名如下:

pow(x, y, z=None, /)

其中,x 为底数,y 为指数,z 为模数(如果指定了模数,则返回 x**y % z)。这个函数的时间复杂度较低,因为它采用了快速幂的算法。

以下是一个示例:

# 计算 2 的 10 次方
result = pow(2, 10)# 输出结果
print(result)

上述代码会输出 1024,即 2 的 10 次方的结果。在这个例子中,pow 函数的参数分别为底数、指数,没有指定模数。


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

相关文章:

【面试经典150 | 数学】Pow(x, n)

文章目录 写在前面Tag题目来源题目解读解题思路方法一:快速幂-递归方法二:快速幂-迭代 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主…...

封装比较好的登录页面

封装比较好的登录页面 只在setup()函数中写流程&#xff0c;将逻辑代码抽离出来 <template><div class"wrapper"><img class"wrapper__img" srchttp://www.dell-lee.com/imgs/vue3/user.png /><div class"wrapper__input"&…...

如何使用Flask request对象处理请求

在 Flask 中&#xff0c;request 对象是处理 HTTP 请求的重要工具之一。它提供了许多属性和方法&#xff0c;可以帮助我们获取请求的相关信息和数据。本文将向你介绍 request 对象的常用方法以及如何在 Flask 应用程序中使用它。 1. 获取请求方法 首先&#xff0c;让我们看一…...

快速搜索多个word、excel等文件中内容

如何快速搜索多个word、excel等文件中内容 操作方法 以win11系统为介绍对象。 首先我们打开“我的电脑”-->“文件夹选项”-->“搜索”标签页,在“搜索内容”下方选择&#xff1a;"始终搜索文件名和内容&#xff08;此过程可能需要几分钟&#xff09;"。然后…...

Minio安装

环境 centos8&#xff0c;关闭防火墙 minio-20231101183725版本 参考官网&#xff1a;部署 MinIO&#xff1a;单节点单硬盘 — 适用于 Linux 的 MinIO 对象存储 单例 下载rpm&#xff0c;用中国镜像 wget https://dl.minio.org.cn/server/minio/release/linux-amd64/arch…...

Spring初识

未来的几周时间&#xff0c;大概率我会更新一下Spring家族的一些简单知识。而什么是Spring家族&#xff0c;好多同学还不是很清楚&#xff0c;我先来简单介绍一下吧&#xff1a; 所谓Spring家族&#xff0c;它其实就是一个框架&#xff0c;是基于Servlet再次进行封装的内容。为…...

2023全新付费进群系统源码 带定位完整版 附教程

这源码是我付费花钱买的分享给大家&#xff0c;功能完整。 搭建教程 Nginx1.2 PHP5.6-7.2均可 最好是7.2 第一步上传文件程序到网站根目录解压 第二步导入数据库&#xff08;58soho.cn.sql&#xff09; 第三步修改/config/database.php里面的数据库地址 第四步修改/conf…...

C# LINQ使用介绍

LINQ&#xff08;Language-Integrated Query&#xff09;是C#语言的一个强大特性&#xff0c;它允许开发者用声明性的方式查询和操作数据。LINQ提供了一致的查询体验&#xff0c;无论是操作内存中的对象&#xff08;如数组或集合&#xff09;&#xff0c;还是操作外部数据源&am…...

【c++】——类和对象(中)——实现完整的日期类(优化)万字详细解疑答惑

作者:chlorine 专栏:c专栏 赋值运算符重载()()():实现完整的日期类(上) 我走的很慢&#xff0c;但我从不后退。 【学习目标】 日期(- - --)天数重载运算符 日期-日期 返回天数 对日期类函数进行优化(不符合常理的日期&#xff0c;负数&#xff0c;const成员)c中重载输入cin和输…...

开源与闭源:大模型时代的技术交融与商业平衡

一、开源和闭源的优劣势比较 1.1 开源 优势&#xff1a; 1.技术共享与吸引人才&#xff1a; 开源促进了技术共享&#xff0c;吸引了全球范围内的人才参与大模型的发展&#xff0c;形成了庞大的开发者社区。 2.推动创新&#xff1a; 开源模式鼓励开发者共同参与&#xff0c;推动…...

C#开发的OpenRA游戏之属性BodyOrientation(6)

C#开发的OpenRA游戏之属性BodyOrientation(6) 在顶层定义里会发现这个属性: ^SpriteActor: BodyOrientation: QuantizeFacingsFromSequence: RenderSprites: SpriteActor是用来定义角色的基本属性,它的第一个属性就是BodyOrientation,这个属性主要用来描述角色的身体的…...

Linux shell编程学习笔记27:tputs

除了stty命令&#xff0c;我们还可以使用tput命令来更改终端的参数和功能。 1 tput 命令的功能 tput 命令的主要功能有&#xff1a;移动更改光标、更改文本显示属性&#xff08;如颜色、下划线、粗体&#xff09;&#xff0c;清除屏幕特定区域等。 2 tput 命令格式 tput [选…...

【计算机网络笔记】IPv6简介

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…...

c语言-数据结构-堆

目录 一、二叉树 1、二叉树的概念 2、完全二叉树和满二叉树 3、完全二叉树的顺序存储 二、堆 2、堆的概念与结构 3、堆的创建及初始化 4、堆的插入&#xff08;小堆&#xff09; 5、堆的删除 6、显示堆顶元素 7、显示堆里的元素个数 8、测试堆的各个功能 9、 实现堆…...

ROS基础—关于参数服务器的操作

1、rosparam list 获取参数服务器的所有参数。 2、rosparam get /run_id 获取参数的值...

Sql Server 2017主从配置之:事务日志传送

使用事务日志传送模式搭建Sql Server 2017主从同步&#xff0c;该模式有一定的延迟&#xff0c;是通过3个不同的定时任务&#xff0c;将主库的日志同步到从库进行恢复来实现数据库同步操作。 环境准备 两台服务器&#xff0c;配置都是8g2核&#xff0c;50g硬盘&#xff0c;操…...

每日OJ题_算法_双指针_力扣283. 移动零+力扣1089. 复写零

力扣283. 移动零 283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 难度 简单 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例…...

WebGl-Blender:建模 / 想象成形 / Blender概念词汇表 / 快捷键

一、理解Blender 欢迎来到Blender&#xff01;Blender是一款免费开源的3D创作套件。 使用Blender&#xff0c;您可以创建3D可视化效果&#xff0c;例如建模、静态图像&#xff0c;3D动画&#xff0c;VFX&#xff08;视觉特效&#xff09;快照和视频编辑。它非常适合那些受益于…...

【C++】【Opencv】cv::warpAffine()仿射变换函数详解,实现平移、缩放和旋转等功能

仿射变换是一种二维变换&#xff0c;它可以将一个二维图形映射到另一个二维图形上&#xff0c;保持了图形的“形状”和“大小”不变&#xff0c;但可能会改变图形的方向和位置。仿射变换可以用一个线性变换矩阵来表示&#xff0c;该矩阵包含了六个参数&#xff0c;可以进行平移…...

WPF实现右键菜单

在WPF中&#xff0c;创建上下文菜单&#xff08;通常称为“右键菜单”&#xff09;是通过使用ContextMenu控件来实现的。你可以在XAML中声明上下文菜单&#xff0c;并将其关联到任何FrameworkElement。以下是如何在WPF中实现上下文菜单的基本步骤&#xff1a; 1. 在XAML中定义…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...