当前位置: 首页 > 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…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...