算法通关村十三关-白银:数字与数学高频问题
有很多解题技巧,需要持续积累
1.数组实现加法专题
如果让你用数组来表示一个数,如何实现加法呢?
理论上仍然从数组末尾向前挨着计算就行了,但是实现的时候会发现很多问题,例如需要进位该怎么办?
进一步拓展,两个数相加,一个用数组存储,另一个是普通的整数,如何处理?
再拓展,如果两个整数使用字符串表示呢?如果是要按照二进制加法的规则来呢?
1.1数组实现整数加法
LeetCode66
https://leetcode.cn/problems/plus-one/
思路分析
从后向前一直加就行,如果有进位就需要进位
重点关注:当进位导致数组长度变化的情况,如 [9,9,9],加1后变为[1,0,0,0],数组长度发生变化
代码实现
Java中巧妙处理数组长度变化
digits = new int[len+1];
digits[0] = 1
def plusOne(digits):n = len(digits)for i in range(n - 1, -1, -1):digits[i] += 1digits[i] %= 10if digits[i] != 0:return digitsreturn [1] + digits
def plusOne(digits):n = len(digits)for i in range(n - 1, -1, -1):if digits[i] < 9:digits[i] += 1return digitsdigits[i] = 0digits.insert(0, 1)return digits
1.2字符串加法
给定两个字符串形式的非负整数 num1 和 num2,计算它们的和并同样以字符串形式返回
思路分析
从低到高逐位相加,如果当前和超过10,则向高位进一位
通过代码写出来
定义两个指针i和j,分别指向num1和num2的末尾,即最低位
定义一个变量add维护当前是否有进位
从末尾到开头逐位相加
注:两个数组位数不同,补0处理
代码实现
def addString(num1, num2):i, j = len(num1) - 1, len(num2) - 1,ans = ""add = 0while i >= 0 or j >= 0 or add:x = num1[i] if i >= 0 else '0'y = num2[j] if j >= 0 else '0'result = int(x) + int(y) + addans = str(result % 10) + ansadd = result // 10i -= 1j -= 1return ans
1.3二进制加法
LeetCode67
https://leetcode.cn/problems/add-binary/
思路分析
方法1:中规中矩,参考上面字符串加法
方法2:先将其转换成十进制,加完之后转换成二进制
这么做实现非常容易,而且可以使用语言提供的方法直接转换
工程里可以这么干,稳定可靠,但是算法里不行,太简单了
代码实现
方法1:
def addBinary(a, b):i, j = len(a) - 1, len(b) - 1,ans = []add = 0while i >= 0 or j >= 0 or add:result = addresult += int(a[i]) if i >= 0 else 0result += int(b[j]) if j >= 0 else 0ans.append(str(result % 2))add = result // 2i -= 1j -= 1ans.reverse()return "".join(ans)if __name__ == '__main__':print(addBinary('100', '111'))
2.幂运算
形式 a^b ,a的b次方,a为底数,b为指数
合法,不会出现a=0且b<=0的情况
关注底数和指数的数据类型和取值范围
如有的问题中,底数是正整数,指数是非负整数
有的问题中,底数是实数,指数是整数
LeetCode中,幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂,以及快速幂的处理
2.1求2的幂
LeetCode 231 2 的幂
https://leetcode.cn/problems/power-of-two/
思路分析
如果存在一个整数x,使得 2^x = n,则认为n是2的幂次方
方法1:除法
用除法逐步缩小n的值
首先判断 n 是否是正整数,n为0或者为负整数,返回false
n 是正整数,连续对n进行除以2的操作,直到n不能被2整除,如果 n==1,返回true,否则返回false
方法2:位运算
该方法与前面统计数字转换成二进制之后1的个数思路一致
当 n>0 时,考虑 n 的二进制表示
如果 n = 2^k,则n的二进制表示为1后面跟 k 个0
仅当 n 的二进制表示中只有最高位是1,其余位都是0,此时满足 n&(n-1)=0
代码实现
class Solution:def isPowerOfTwo(self, n: int) -> bool:# 方法1:除法if n <= 0:return Falsewhile n % 2 == 0:n //= 2return n == 1
class Solution:def isPowerOfTwo(self, n: int) -> bool:# 方法2:位运算return n>0 and n&(n-1) == 0
2.2求3的幂
LeetCode326
https://leetcode.cn/problems/power-of-three/
思路分析
方法1:除法
同上面求2的幂
方法2:技巧
给定的n是int型,其最大值为 2^31-1
不超过 2^31 的最大的3的幂是 3^19 = 1162261467
如果在 1~2^31-1内的数,如果是3的幂,则一定是能被 1162261467 整除
代码实现
方法1:除法
class Solution:def isPowerOfThree(self, n: int) -> bool:# 方法1:除法if n<=0:return Falsewhile n%3==0:n//=3return n == 1
方法2:技巧
class Solution:def isPowerOfThree(self, n: int) -> bool:# 方法2:技巧return n>0 and 3**19 % n == 0
拓展思考
这里将3换成 4,5,6,7,8,9可以吗?如果不可以,那如果只针对素数 3,5,7,11,13可以吗?
2.4求4的幂
LeetCode342
https://leetcode.cn/problems/power-of-four/submissions/
思路分析
方法1:除法
与求2的幂思路一致,数学方法一直除
方法2:利用2的次幂进行拓展来优化
如果n是4的幂,那么n一定是2的幂 满足 n&(n-1)==0
如果n是4的幂,n的二进制表示只有1个1,1后面必须有偶数个0,且1出现在从低位开始(从0开始)的第偶数个二进制位上
如 16 的二进制表示 10000
n为32为有符号整数,构建辅助二进制数
MASK = 1010 1010 1010 1010 1010 1010 1010 1010
MASK = AAAAAAAA 16进制
方法3:取模
4^x≡(3+1) ^x ≡1^x≡1(mod 3)
如果 n是2的幂却不是 2 的幂,那么它可以表示成 4^× * 2,它除以3的余数一定为2。
因此我们可以通过n除以 3 的余数是否为 1来判断 n 是否是 4 的幂。
代码实现
方法1:
class Solution:def isPowerOfFour(self, n: int) -> bool:# 方法1:除法if n<= 0:return Falsewhile n % 4 == 0:n //= 4return n == 1
方法2:
class Solution:def isPowerOfFour(self, n: int) -> bool:# 方法2:2的幂的拓展return n>0 and n&(n-1)==0 and n&(0xaaaaaaaa) == 0
方法3:
class Solution:def isPowerOfFour(self, n: int) -> bool:# 方法3:取模return n>0 and n&(n-1)==0 and n % 3 == 1
相关文章:
算法通关村十三关-白银:数字与数学高频问题
有很多解题技巧,需要持续积累 1.数组实现加法专题 如果让你用数组来表示一个数,如何实现加法呢? 理论上仍然从数组末尾向前挨着计算就行了,但是实现的时候会发现很多问题,例如需要进位该怎么办? 进一步拓…...

【Linux】线程安全-互斥同步
文章目录 线程安全问题的引入线程互斥互斥概念互斥锁互斥锁的计数器当中如何保证原子性互斥锁基础API初始化互斥锁变量函数动态初始化静态初始化 加锁函数阻塞加锁非阻塞加锁带有超时时间的加锁 解锁函数销毁互斥锁函数 线程同步线程同步的必要性条件变量条件变量的使用原理条件…...

1.初识爬虫
爬虫是批量模拟网络请求的程序,想百度谷歌这种搜索类网站本质上就是爬虫 使用爬虫的时候不应该对别人的网站有严重的影响,比如你爬的频率太高了,让人家的网站崩溃了。不应该爬取网页上显示不到的内容,比如有一个直播的网站&#…...

TLA+学习记录1——hello world
0x01 TLA是个好工具 编程人员一个好习惯是凡事都想偷懒,当然是指要科学地偷懒,而不是真的偷懒。一直想找到一种能检验写出的代码,做出的设计是否真的完全正确,而不是靠经验检视、代码Review、反复测试去检验。因为上述方法不管怎…...

基于QWebEngine实现无头浏览器
无头浏览器 无头浏览器(Headless Browser)是一种没有图形用户界面(GUI)的浏览器。它通过在内存中渲染页面,然后将结果发送回请求它的用户或程序来实现对网页的访问,而不会在屏幕上显示网页。这种方式使得无…...
编译Micropython固件For树莓派Raspberry Pi Pico
1. 前言 由于想把自己编写的py文件打包的固件中,所以记录下如何编译micropython固件和打包。 2. 编译 最简单的方式就是在你的树莓派上进行,我用的是RP Pi2 下载所需文件: $ cd ~/ $ mkdir pico $ cd pico $ git clone -b pico https://gi…...

基于googlenet网络的动物种类识别算法matlab仿真
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 ................................................................. % 获取输入层的尺寸 Inp…...

如何用Jmeter编写脚本压测?
随着商业业务不断扩张,调用adsearch服务频率越来越高,所以这次想做个压测,了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具,压测思路如图: 一、日志入参 日志选取的adsearch 的 getads部分…...
SpingMVC之拦截器使用详解
拦截器概述 SpringMVC的处理器拦截器,类似于Servlet开发中的过滤器Filter,用于对处理器进行预处理和后处理。 过滤器和拦截器区别 过滤器:依赖于servlet容器。在实现上基于函数回调,可以对几乎所有请求进行过滤,但是缺点是一个过…...
motionface respeak新的aigc视频与音频对口型数字人
在当今的数字化时代,人工智能(AI)正在逐渐渗透到我们生活的方方面面。其中,AI技术在视频制作和处理领域的应用也日益广泛。本文将探讨如何利用AI技术实现视频中人脸与音频同步对口型的方法,旨在进一步丰富视频制作的效…...

【计算机网络】 静态库与动态库
文章目录 静态库实践使用方法总结 动态库实践使用方法总结 静态库与动态库的优缺点静态库优点缺点 动态库缺点优点 库有两种:静态库(.a、.lib)和动态库(.so、.dll)。所谓静态、动态是指链接。静态库是将整个库文件都拷…...

web端调用本地摄像头麦克风+WebRTC腾讯云,实现直播功能
目录 关于直播直播流程直播视频格式封装推流和拉流 获取摄像头和麦克风权限navigator.getUserMedia()MediaDevices.getUserMedia() WebRTC腾讯云快直播 关于直播 视频直播技术大全、直播架构、技术原理和实现思路方案整理 直播流程 视频采集端: 1、视频采集&#…...

React笔记(八)Redux
一、安装和配置 React 官方并没有提供对应的状态机插件,因此,我们需要下载第三方的状态机插件 —— Redux。 1、下载Redux 在终端中定位到项目根目录,然后执行以下命令下载 Redux npm i redux 2、创建配置文件 在 React 中,…...
数据库 | 数据库概述、关系型数据库、非关系型数据库
目录: 1.数据库:1.1 数据库的含义1.2 数据库的特点 2.数据表3.数据库管理系统4.数据库系统5.关系型数据库 和 非关系型数据库:5.1 关系型数据库5.2 关系型数据库“优势”5.3 非关系型数据库 6.关系型数据库 和 非关系型数据库 的“区别” 1.数…...
【备战csp-j】 csp常考题目详解(4)
四.数值转换与编码 1. 十进制数 11/128 可用二进制数码序列表示为( ) 。 A.1011/1000000 B.1011/100000000 C.0.001011 D.0.0001011 答案:D 解析:暂时未找到解决方法,以后会解决。 2. 算式(2047)10 - (3FF)16 + …...
linux中常见服务端安装
linux安装服务脚本 1、yum安装 # 通过apt安装yum apt install yum # yum安装软件 yum install pam-devel # yum 卸载 yum remove pam-devel2、rpm安装 # 安装 rpm -i example.rpm #安装 example.rpm 包; rpm -iv example.rpm #安装 example.rpm 包并在安装过程…...

L1-058 6翻了(Python实现) 测试点全过
前言: {\color{Blue}前言:} 前言: 本系列题使用的是,“PTA中的团体程序设计天梯赛——练习集”的题库,难度有L1、L2、L3三个等级,分别对应团体程序设计天梯赛的三个难度。更新取决于题目的难度,…...

初学Python记
Python这个编程语言的大名当然听说过了呀,这几年特别火,火的一塌涂地。大家可以回忆一下:朋友圈推荐的广告里经常可以看见python的网课广告。 本学期,学校开设了python课程,这几天学习了一下入了一下门,感…...

计算机竞赛 基于深度学习的目标检测算法
文章目录 1 简介2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 1 简介 ǵ…...
sentinel-core
引入依赖<dependencies><dependency><groupId>com.alibaba.csp</groupId><artifactId>sentinel-core</artifactId></dependency><dependency><groupId>com.alibaba.csp</groupId><artifactId>sentinel-anno…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...

莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...