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

【leetcode 力扣刷题】数学题之计算次幂//次方:快速幂

利用乘法求解次幂问题—快速幂

  • 50. Pow(x, n)
  • 372. 超级次方

50. Pow(x, n)

题目链接:50. Pow(x, n)
题目内容:
在这里插入图片描述
题目就是要求我们去实现计算x的n次方的功能函数,类似c++的power()函数。但是我们不能使用power()函数直接得到答案,那样这道题就失去了考察的意义。
前面提到乘法a*b可以看作是b个a相加,用加法来完成乘法;x的n次方,就是n个x相乘,那么同样可以用乘法来代替次幂计算,我们称之为快速幂。比如5^7,就是7个5相乘,快速幂的过程如下:
在这里插入图片描述
第一轮是乘以5,第二轮乘以5*5,第三轮乘以(5*5)*(5*5),也就是每一轮乘的数都在加倍,这样就能够在log^n的时间复杂度内完成x^n的计算。代码实现如下(C++):


class Solution {
public:double myPow(double x, int n) {//先处理特殊情况if(x == 0) return 0.0;if(x == 1) return 1.0;if(n == 0) return 1.0;bool flage = false;long _n = n;//如果n是负数,x^n = 1/(x^|n|)if(_n < 0){flage = true;_n = -_n;}double ans = 1;double mul = x;//快速幂主体过程while(_n){  if(_n&1)  //如果n末位为1,就乘以mulans *= mul;      mul *= mul; //mul翻倍_n >>= 1; //n右移一位}return flage ? 1.0/ans : ans; //判断是否需要变成倒数}
};

372. 超级次方

题目链接:372. 超级次方
题目内容:
在这里插入图片描述
看起来和上一题是差不多的,但是由于b是一个非常大的正整数,以数组形式给出[1,0,3,4]就表示1034【末位是个位,然后是十位,然后是百位,最前面的是最高位】。其中1 <= b.length <= 2000说明b可以达到10^1999的程度,根本没法用double、long long等数据类型来存储这么大的数,所以在运算过程中也不能直接把b转换成一个数或者每一位转换成一个数,需要其他方法:
在这里插入图片描述
将每一位b[i]的数值b[i]*10^(m-1-i)【其中m是b.length】分解成b[i]和10^(m-1-i)两部分,每次先求a^(10^(m-1-i))得到A,再求A^b[i]。a^(10^(m-1-i))随着i的减小越来越大,但是可以看作是上一轮的A^10。
由于每次次幂结果都要mod 1337,所以结果是不会溢出的,a^(10^(m-1-i))每一次用上一轮的A^10来表示就解决了b很大的问题。另外需要注意的是(a*b) mod k =( (a mod k) * (b mod k) ) mod k。
a^(10^(m-1-i))和A^b[i]以及A^10都用快速幂求解。快速幂过程中根据(a*b) mod k =( (a mod k) * (b mod k) ) mod k加上求模操作。代码如下(C++):

class Solution {
public://快速幂long quick_pow(int a, int n){int ans = 1;int mul = a;while(n){if(n&1)//加上求模操作ans = ( (ans % 1337) * (mul % 1337)) % 1337;//mul也加上求模操作mul = ((mul % 1337) * (mul % 1337)) % 1337;n>>=1;}return ans;}int superPow(int a, vector<int>& b) {int ans = 1;        for(int j = b.size() - 1; j >= 0; j--){ans =( (ans % 1337) * (quick_pow(a,b[j]) % 1337) ) % 1337;//每次a都在上一次的基础上,变成其10次方a = quick_pow(a, 10);}return ans;}
};

相关文章:

【leetcode 力扣刷题】数学题之计算次幂//次方:快速幂

利用乘法求解次幂问题—快速幂 50. Pow(x, n)372. 超级次方 50. Pow(x, n) 题目链接&#xff1a;50. Pow(x, n) 题目内容&#xff1a; 题目就是要求我们去实现计算x的n次方的功能函数&#xff0c;类似c的power()函数。但是我们不能使用power()函数直接得到答案&#xff0c;那…...

【核心复现】基于改进灰狼算法的并网交流微电网经济优化调度(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Cannal监听binlog

文章目录 一、canal概念二、canal使用场景四、Canal工作原理Mysql主从复制原理 binlog中的二进制日志binlog格式选择 Canal消费方式应用实践总结 一、canal概念 canal是用java开发的基于数据库增量日志解析&#xff0c;提供增量数据订阅&消费的中间件。目前&#xff0c;ca…...

从零开发JavaWeb入门项目--十天掌握

原文网址&#xff1a;从零开发JavaWeb入门项目--十天掌握_IT利刃出鞘的博客-CSDN博客 简介 这是一个靠谱的JavaWeb入门项目实战&#xff0c;名字叫蚂蚁爱购。从零开发项目&#xff0c;视频加文档&#xff0c;十天就能学会开发JavaWeb项目&#xff0c;教程路线是&#xff1a;搭…...

数据结构——哈希表

哈希表 这里没有讲哈希表底层的概念&#xff0c;什么转红黑树&#xff0c;什么链表的&#xff0c;这篇文章主要讲的是如何用C实现哈希表&#xff0c;以及哈希表的基本概念。后面我会出一篇文章来讲C中hashmap中的底层逻辑的知识。 哈希表的概念 哈希表是一种数据结构&#xff0…...

Kafka3.0.0版本——手动调整分区副本示例

目录 一、服务器信息二、启动zookeeper和kafka集群2.1、先启动zookeeper集群2.2、再启动kafka集群 三、手动调整分区副本3.1、手动调整分区副本的前提条件3.2、手动调整分区副本的示例需求3.3、手动调整分区副本的示例 一、服务器信息 四台服务器 原始服务器名称原始服务器ip节…...

玩客云 线刷Armbian 搭配Alist 阿里云盘 Jellyfin NovaVideoPlayer搞电视墙

啰嗦的背景 喜欢看电影&#xff0c;买了个投影仪&#xff0c;是这一切折腾的开端。 投影仪虽然有当贝系统&#xff0c;但是想看的电影总是需要**电视会员&#xff0c;那我肯定是不用的。因为有爱腾优的会员&#xff0c;最开始都是使用手机投屏&#xff0c;当呗的投影仪好就好…...

9月1日,每日信息差

1、华大智造&#xff1a;已实现海外基因测序仪和测序试剂的量产&#xff0c;实现了海外基因测序仪和测序试剂的量产 2、邮储银行下调定存利率。价格表显示&#xff0c;整存整取&#xff0c;一年期存款年利率为1.58%&#xff0c;二年期年利率为1.85%&#xff0c;三年期年利率为…...

【大数据】Flink 详解(六):源码篇 Ⅰ

Flink 详解&#xff08;六&#xff09;&#xff1a;源码篇 Ⅰ 55、Flink 作业的提交流程&#xff1f;56、Flink 作业提交分为几种方式&#xff1f;57、Flink JobGraph 是在什么时候生成的&#xff1f;58、那在 JobGraph 提交集群之前都经历哪些过程&#xff1f;59、看你提到 Pi…...

ShardingSphere——弹性伸缩原理

摘要 支持自定义分片算法&#xff0c;减少数据伸缩及迁移时的业务影响&#xff0c;提供一站式的通用弹性伸缩解决方案&#xff0c;是 Apache ShardingSphere 弹性伸缩的主要设计目标。对于使用单数据库运行的系统来说&#xff0c;如何安全简单地将数据迁移至水平分片的数据库上…...

Linux项目自动化构建工具-make/Makefile

一、什么是make和makefile make是一条指令 Makefile是当前目录下的一个文件 二、makefile文件编写 依赖关系&#xff1a;:前为要目标文件&#xff0c;后为其依赖的文件 依赖方法&#xff1a;用依赖文件生成目标文件的具体指令 简便写法&#xff1a; $:表示目标文件 $^:表示…...

Python爬虫实战:自动化数据采集与分析

在大数据时代&#xff0c;数据采集与分析已经成为了许多行业的核心竞争力。Python作为一门广泛应用的编程语言&#xff0c;拥有丰富的爬虫库&#xff0c;使得我们能够轻松实现自动化数据采集与分析。本文将通过一个简单的示例&#xff0c;带您了解如何使用Python进行爬虫实战。…...

视频智能分析平台EasyCVR安防视频汇聚平台助力森林公园防火安全的应用方案

一、研发背景 随着经济的发展和人们生活水平的提高&#xff0c;越来越多的人喜欢在周末去周边的森林公园旅游&#xff0c;享受大自然的美景&#xff0c;并进行野炊和烧烤等娱乐活动。然而&#xff0c;近年来由于烟蒂和烧烤碳渣等人为因素&#xff0c;森林公园火灾频繁发生。森…...

跨境做独立站,如何低成本引流?

大家都知道&#xff0c;海外的消费习惯与国内不同&#xff0c;独立站一向是海外消费者的最喜欢的购物方式之一&#xff0c;这也吸引了许多跨境商家开设独立站。 独立站不同于其他的第三方平台&#xff0c;其他平台可以靠平台自身流量来获得转化&#xff0c;而独立站本身没有流…...

leetcode55.跳跃游戏 【贪心】

题目&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例…...

探秘C语言扫雷游戏实现技巧

本篇博客会讲解&#xff0c;如何使用C语言实现扫雷小游戏。 0.思路及准备工作 使用2个二维数组mine和show&#xff0c;分别来存储雷的位置信息和排查出来的雷的信息&#xff0c;前者隐藏&#xff0c;后者展示给玩家。假设盘面大小是99&#xff0c;这2个二维数组都要开大一圈…...

Leetcode112. 路径总和

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 t…...

生成12位短id,自增且不连续,永不重复,不依赖数据库

基本思路&#xff1a; 设计模式&#xff1a;单例模式 是否加锁&#xff1a;是 synchronized 获取最后一次生成的时间戳值T0 限定初始时间为2023-08-01 00:00:00,获取当前时间时间戳T1,T1与初始时间的毫秒差值T2,转为16进制&#xff0c;转为字符串为r1,获取该字符串的长度L1…...

Zip压缩文件夹php打包函数代码

Zip压缩文件夹php打包函数代码,Zip相关函数是PHP的扩展功能,此函数可以直接复制使用。 以下是代码: <?php # 将文件夹的文件压缩到文件里 class Zip {/*** 将目标文件夹下的内容压缩到zip中(zip包含文件夹目录)* @param $sourcePath *文件夹路径 例: /home/test* @p…...

RISC-V交叉工具链riscv-gnu-toolchain编译

文章目录 1、下载2、编译1. 依赖安装2. 编译 3、运行 1、下载 $ sudo apt-get install git wget build-essential $ git clone https://github.com/riscv-collab/riscv-gnu-toolchain $ git checkout 2023.06.02注意上面 clone 的仓库&#xff0c;我们称其为构建脚本仓库&…...

Cesium 三维地图开发实战:主流在线底图(天地图、高德、百度等)的集成与坐标纠偏方案

1. 三维地图开发中的底图选择困境 第一次用Cesium加载国内在线地图时&#xff0c;我被满屏错位的道路和建筑搞懵了。明明在二维地图里精准对齐的学校操场&#xff0c;在三维场景里却飘到了隔壁小区。这种"灵魂出窍"般的偏移现象&#xff0c;其实是不同坐标系之间的&q…...

超越GUI:用Tcl命令流高效编辑Tessent DftSpecification的三种进阶玩法

超越GUI&#xff1a;用Tcl命令流高效编辑Tessent DftSpecification的三种进阶玩法 在大型SoC项目中&#xff0c;频繁修改IJTAG网络结构是每位资深DFT工程师的日常。当设计迭代进入深水区&#xff0c;图形界面操作和手动文本编辑的效率瓶颈会愈发明显——每次增减SIB、调整TDR位…...

如何用Win11Debloat让你的Windows系统速度提升70%:终极优化指南

如何用Win11Debloat让你的Windows系统速度提升70%&#xff1a;终极优化指南 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutt…...

智能处理与开源工具:突破传统背景抠图限制的实时解决方案

智能处理与开源工具&#xff1a;突破传统背景抠图限制的实时解决方案 【免费下载链接】obs-backgroundremoval An OBS plugin for removing background in portrait images (video), making it easy to replace the background when recording or streaming. 项目地址: https…...

资源获取的技术突围:res-downloader的跨平台解决方案

资源获取的技术突围&#xff1a;res-downloader的跨平台解决方案 【免费下载链接】res-downloader 视频号、小程序、抖音、快手、小红书、直播流、m3u8、酷狗、QQ音乐等常见网络资源下载! 项目地址: https://gitcode.com/GitHub_Trending/re/res-downloader 在数字内容爆…...

深度解析:Element Plus架构设计与实现原理

深度解析&#xff1a;Element Plus架构设计与实现原理 【免费下载链接】element-plus &#x1f389; A Vue.js 3 UI Library made by Element team 项目地址: https://gitcode.com/GitHub_Trending/el/element-plus Element Plus作为Vue.js 3生态中最具影响力的企业级UI…...

【大英赛】2009-2026年大英赛ABCD类历年真题、样卷、听力音频及答案PDF电子版

2026年大英赛将于4月12日9:00—11:00举行&#xff0c;开始倒计时啦&#xff01;小编整理了最新的2009-2026年大学生英语竞赛&#xff08;大英赛NECCS&#xff09;ABCD类历年真题、样卷、听力音频及答案解析&#xff0c;PDF电子版&#xff0c;可下载打印&#xff01; 资料下载&a…...

ICLR 2025论文解读│PointOBB-v2:单点监督下的高效有向目标检测新突破

1. PointOBB-v2&#xff1a;单点监督的革命性突破 有向目标检测一直是计算机视觉领域的重要研究方向&#xff0c;特别是在遥感图像分析、自动驾驶和工业检测等实际应用中。传统的有向边界框&#xff08;OBB&#xff09;标注需要人工精确标注目标的旋转角度和四个顶点坐标&…...

Android 离线语音合成技术选型指南:从MaryTTS到TensorFlowTTS

1. 为什么需要离线语音合成技术&#xff1f; 最近几年&#xff0c;越来越多的应用开始集成语音合成功能。你可能见过导航软件里实时播报路况的电子女声&#xff0c;或者听书App里流畅朗读小说的AI配音。这些场景背后&#xff0c;都离不开TTS&#xff08;Text-To-Speech&#x…...

手把手教你用AI超分镜像:低清图片3倍放大,细节修复超简单

手把手教你用AI超分镜像&#xff1a;低清图片3倍放大&#xff0c;细节修复超简单 1. 为什么你需要这个AI超分工具&#xff1f; 你是不是也遇到过这些头疼的情况&#xff1f; 翻出十几年前的老照片&#xff0c;想打印出来&#xff0c;却发现画面模糊得像蒙了一层雾。从网上下…...