算法通关村十三关-白银:数字与数学高频问题
有很多解题技巧,需要持续积累
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…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...