当前位置: 首页 > 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;我们称其为构建脚本仓库&…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...