算法通关村十三关-白银:数字与数学高频问题
有很多解题技巧,需要持续积累
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…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...

向量几何的二元性:叉乘模长与内积投影的深层联系
在数学与物理的空间世界中,向量运算构成了理解几何结构的基石。叉乘(外积)与点积(内积)作为向量代数的两大支柱,表面上呈现出截然不同的几何意义与代数形式,却在深层次上揭示了向量间相互作用的…...