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

leetcode剑指 Offer 16. 数值的整数次方

  • 题目描述
  • 解题思路
  • 执行结果
leetcode .


题目描述

实现 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/problems/shu-zhi-de-zheng-shu-ci-fang-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

计算x^n

法1

循环相乘
r*=x循环n次

  • 时间复杂度(O(n))
  • 空间复杂度(O(1))

法2

快速幂\

  1. 举个例子n^4=n^2*n^2
  2. n^8=n^4*n^4
  3. 这样我们可以减少循环的次数只需要计算n^2,n^4...n^2^m就行了
  4. 比如x^10=x^8*x^2,我们只需要计算到x^8就可以了,

具体实现过程

令一个中间变量t=x
t*=t
当n&1==1时执行
r*=t
循环执行n>>1直到n==0为止\

  • 时间复杂度(O(logn))
  • 空间复杂度(O(1))

法3

  • 时间复杂度(O())
  • 空间复杂度(O())

执行结果

快速幂

快速幂算法

// 快速幂
func myPow(x float64, n int) (r float64) {
 if n < 0 {//当n为负数的时候,我们将x=x^-1进行计算就不用定义新的计算方法了
  x = 1 / x
  n = -n
 }
 r = 1
 for t := x; n > 0; {
  if n&1 == 1 {
   r *= t//当为1时计算入值
  }
  t *= t//幂的叠加
  n >>= 1
 }
 return
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗: 1.9 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例: 304 / 304

本文由 mdnice 多平台发布

相关文章:

leetcode剑指 Offer 16. 数值的整数次方

题目描述解题思路执行结果leetcode .题目描述 实现 pow(x, n) &#xff0c;即计算 x 的 n 次幂函数&#xff08;即&#xff0c;xn&#xff09;。不得使用库函数&#xff0c;同时不需要考虑大数问题。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1…...

漏洞挖掘相关-信息收集

一、常见端口以及漏洞 1.FTP&#xff1a;文件传输协议 TCP端口20、21&#xff0c;20用于传输数据&#xff0c;21用于传输控制信息 (1) ftp基础爆破: owasp的Bruter,hydra以及msf中的ftp爆破模块。 (2) ftp匿名访问:用户名: anonymous密码:为空或者任意邮箱 (3) vsftpd后门: …...

海外分支如何加速访问国内总部办公系统?海域网发布 Sea-WAN解决方案

近年来&#xff0c;一大批优秀的中国企业走向世界&#xff0c;品牌越来越响亮&#xff0c;海外影响力越来越大&#xff0c;比如名创优品&#xff0c;国货之光“花西子”&#xff0c;安科创新等&#xff0c;很多企业在海外设立分支机构为当地客户服务&#xff0c;与此同时&#…...

js设计模式——责任链模式

一、概述 责任链是一种行为设计模式&#xff0c;它允许将请求沿着处理链传递&#xff0c;直到有一个处理器可以处理该请求。在这种模式中&#xff0c;每个处理器都有机会处理请求&#xff0c;如果没有一个处理器能够处理请求&#xff0c;那么请求最终将被忽略。这种模式可以帮…...

接口组成更新

接口组成更新概述&#xff1a; 接口的组成&#xff1a; 常量 public static final 抽象方法 public abstract 默认方法java8 静态方法java8 私有方法java9 接口中默认方法 接口中默认方法的定义格式&#xff1a; 格式&#xff1a;public default 返回值类型 方法名&#x…...

int(1) 和 int(10)区别

有个表的要加个user_id字段&#xff0c;user_id字段可能很大&#xff0c; alter table xxx ADD user_id int(1)。 int(1)怕是不够用吧&#xff0c;接下来是一通解释。 我们知道在mysql中 int占4个字节&#xff0c;那么对于无符号的int&#xff0c;最大值是2^32-1 4294967295&a…...

华为OD机试-组合出合法最小数-2022Q4 A卷-Py/Java/JS

给一个数组,数组里面都是代表非负整数的字符串,将数组里所有的数值排列组合拼接起来组成一个数字,输出拼成的最小的数字。 输入描述 一个数组,数组不为空,数组里面都是代表非负整数的字符串,可以是0开头,例如:[”13","045","09","56&qu…...

ChatGPT中文在线官网-如何与chat GPT对话

怎么下载ChatGPT中文版 ChatGPT是一种基于Transformer架构的自然语言处理技术&#xff0c;其中包含了多个预训练的中文语言模型。这些中文ChatGPT模型大多数发布在Github上&#xff0c;可以通过Github的源码库来下载并使用&#xff0c;包括以下几种方式&#xff1a; 下载预训练…...

macOS 13.3.1 (22E261)With OpenCore 0.9.2开发版 and winPE双引导分区原版镜像

镜像特点 原文来源于黑果魏叔官网&#xff0c;转载需注明出处。&#xff08;下载请直接百度黑果魏叔&#xff09; 完全由黑果魏叔官方制作&#xff0c;针对各种机型进行默认配置&#xff0c;让黑苹果安装不再困难。系统镜像设置为双引导分区&#xff0c;全面去除clover引导分…...

《iTOP-3568开发板快速测试手册》第7章 Yocto系统外设功能测试(1)

瑞芯微RK3568芯片是一款定位中高端的通用型SOC&#xff0c;采用22nm制程工艺&#xff0c;搭载一颗四核Cortex-A55处理器和Mali G52 2EE 图形处理器。RK3568 支持4K 解码和 1080P 编码&#xff0c;支持SATA/PCIE/USB3.0 外围接口。RK3568内置独立NPU&#xff0c;可用于轻量级人工…...

【周末闲谈】AI的旅途

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️周末闲谈】 系列目录 ✨第一周 二进制VS三进制 ✨第二周 文心一言&#xff0c;模仿还是超越&#xff1f; ✨第二周 畅想AR 文章目录系列目录前言AIAI的开端第一个AI程序AI的寒冬关于AI的思考末尾前言…...

回溯算法--01背包问题

目录 回溯算法--01背包问题 [算法描述] [回溯法基本思想] 法一&#xff1a; 法二&#xff1a; 代码&#xff1a; 运行结果 代码改进 回溯算法--01背包问题 [算法描述] 0-1背包问题是子集选取问题。一般情况下&#xff0c;0-1背包问题是NP完全问题。0-1背包问题的解空…...

Spring MVC请求处理流程分析

Spring MVC请求处理流程分析一 Spring MVC 请求处理流程二 Spring MVC 请求处理流程源码分析2.1架构图解2.2 重要时机点分析2.3核心步骤分析2.3.1 getHandler⽅法剖析2.3.2 getHandlerAdapter⽅法剖析2.3.3 ha.handle⽅法剖析2.3.4 processDispatchResult⽅法剖析三 Spring MVC…...

Python高阶知识之属性管理

本文主要介绍Python高阶知识中的属性管理&#xff0c;这部分知识在常规Python编程中用的很少&#xff0c;但对于想深度了解Python甚至有志于自己编写实用框架的人&#xff0c;还是很有必要的&#xff0c;并且如果掌握了&#xff0c;对日常的代码学习等也会有一定好处。 本文结…...

【Linux】创建目录文件,并完成删除,拷贝,移动,比较等操作

操作前&#xff1a; 1.创建目录 mkdir命令 格式&#xff1a; mkdir 目录名 示例&#xff1a; 点击主文件夹查看 2.创建文件夹 touch命令 格式&#xff1a; touch 文件夹名 示例&#xff1a; 3.重命名文件 mv命令 格式 &#xff1a; mv 123.txt abc.txt 示…...

python http服务搭建教程

作为互联网时代的基础技术之一&#xff0c; HTTP是一个简单的 HTTP协议&#xff0c;它包含了请求、应答和超文本传输控制等机制。HTTP协议由 TCP/IP协议族定义&#xff0c;其中包括了三个基本的服务&#xff1a;发送、接收、存储。客户端和服务器之间传输信息时&#xff0c;数据…...

高速数字信号VS射频信号,到底哪个更难设计?

一博高速先生成员&#xff1a;黄刚熟悉高速先生的小伙伴们会知道&#xff0c;我们是以研究高速数字信号为主的团队&#xff0c;从不到1G到目前在研究的112G&#xff0c;高速先生就这样一直研究过来的&#xff0c;分享的案例也大多是以高速数字信号为主的案例。最近受到我们粉丝…...

相对路径读取json文件 labelme_shapes_to_label 标签

直接读取&#xff1a; import jsonwith open(file.json, r, encodingutf-8) as f:data json.load(f) 忽略错误读取&#xff1a; import jsonimport codecs with codecs.open(file.json, r, encodingutf-8, errorsignore) as f:data json.load(f) labelme_shapes_to_labe…...

IDEA工具避坑指南(十一):git导入SpringBoot后|不识别依赖 |大量爆红 | 无法启动

一、前言 使用在IDEA2019中&#xff0c;使用Git工具导入SpringBoot项目后&#xff0c;java类的依赖包大量爆红、不能启动SpringBoot&#xff0c;不能自动识别启动类。 提示&#xff1a;如果刚拉取的项目&#xff0c;只有.git和.idea文件&#xff0c;没有src或java目录&#xff…...

管道命令(sort、uniq、tr、cut、eval命令)

一、sort命令 1、作用 以行为单位对文件内容进行排序也可以根据不同的数据类型来排序 2、语法格式 sort [选项] 参数cat file | sort 选项3、常用选项 -f∶ 忽略大小写&#xff0c;会将小写字母都转换为大写字母来进行比较&#xff1b; -b∶ 忽略每行前面的空格&#xff1b…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...