使数组和能被P整除[同余定理+同余定理变形]
同余定理+同余定理变形
- 前言
- 一、使数组和能被P整除
- 二、同余定理+变形
- 总结
- 参考资料
前言
同余定理非常经典,采用前缀和 + map,当两个余数前缀和为一个值时,则中间一段子数组刚好对P整除。但是能否找到前面是否有一段子数组和可以对P整除呐?反向思考,找map[P - mod]就知道中间一段子数组和对P取余为mod,前面一段子数组和对P取余为0.
一、使数组和能被P整除
二、同余定理+变形
- 基本思路
// 前缀和+map,记录前面除p多余的情况a,a属于[0,p)
// 有一样的余数,不就能整除了嘛,记录余数+位置,同余定理。 - 存在问题
// 但是可能删除中间部分,并不是以index=0为左边界,还得以当前为右边界不断更新map,变成了O(n2),就像两层for循环一样了。
// 但O(n2)显然超时,回到map,可不可以不for循环更新map,直接反向思考,前面为0,那中间那部分余数就算多余的。
func minSubarray(nums []int, p int) int {// 求整个数组和对p的余数sum := getMod(nums,p)// 前缀和记录,可以正向+反向使用前缀和prefix := map[int]int{0:-1}pre,m := 0,len(nums) // 前缀和,最小删除子数组的长度for i,n := range nums {mod := (n + pre) % p // 正向余数x := (p - sum + mod) % p // 反向余数,可得到中间一段子数组和为sum// 正向余数,同余定理,删除最前面的一截。if v,ok := prefix[sum];ok { m = min(m,v + 1)}// 反向余数,以当前位置为需要删除子数组的右边界,寻找符合要求的左边界。if v,ok := prefix[x];ok {m = min(m,i - v)}prefix[mod] = ipre = mod}// 没有寻找到可删除的子数组。if m == len(nums) {return -1}return m
}
func getMod(nums []int,p int) int {sum := 0for _,n := range nums {sum += nsum %= p}return sum
}
func min(x,y int) int {if x < y {return x}return y
}
总结
1)同余定理,可以O(N)复杂度求到子数组和对P整除,基于此多多思考其本质,才能另辟蹊径,做到其变形解法。
参考资料
[1] LeetCode 使数组和能被P整除
相关文章:
使数组和能被P整除[同余定理+同余定理变形]
同余定理同余定理变形前言一、使数组和能被P整除二、同余定理变形总结参考资料前言 同余定理非常经典,采用前缀和 map,当两个余数前缀和为一个值时,则中间一段子数组刚好对P整除。但是能否找到前面是否有一段子数组和可以对P整除呐…...
25k的Java开发常问的Synchronized问题有哪些?
前言:面试高频的Synchronized问题大多集中在应用场景、底层实现原理、锁的升级过程。 文章目录 Synchronized定义应用场景对象加锁实现原理JDK6以前JDK6版本及以后对象从无锁到偏向锁转化的过程(大概讲五分钟)轻量级锁升级的过程(大概讲五分钟)自旋锁策略(大概讲五分钟)…...
ES增量同步方案
1 基于业务代码嵌入式的增量同步方式在Java业务代码要修改业务数据的地方,增加调用写入ES数据的方法优点:1、实现方式简单,可控粒度高;2、不依赖第三方数据同步框架;3、数据库不用做特殊配置和部署;缺点&am…...
计算器--课后程序(Python程序开发案例教程-黑马程序员编著-第6章-课后作业)
实例1:计算器 计算器极大地提高了人们进行数字计算的效率与准确性,无论是超市的收银台,还是集市的小摊位,都能够看到计算器的身影。计算器最基本的功能是四则运算。本实例要求编写程序,实现计算器的四则运算功能。 实…...
YOLOv5中添加SE模块详解——原理+代码
目录一、SENet1. 设计原理2. SE Block2.1 Squeeze:Global Information Embedding2.2 Excitation:Adaptive Recalibration3. SE-Inception and SE-ResNet二、YOLOv5中添加SENet1.修改common.py2.修改yolo.py3.修改yolov5s.yaml参考文章一、SENet 论文地址:Squeeze-a…...
arcgispro3.1(账号登陆)
ArcGIS Pro 3.1 更新中文概览专注于 制图、GIS、Python前言:本次更新给了我两个惊喜,一个是本来 ArcMap 就有的功能,另一个明显是学习的 QGIS,嘿嘿,大家往下看吧。整理翻译了一下官方的 ArcGIS Pro 3.1 新特性更新概览…...
VB6换个思路解决微信下载文件只读的问题(含源码)
日期:2023年3月10日 作者:Commas 签名:(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释:如果您觉得有所帮助,帮忙点个赞,也可以关注我,我们一起成长;如果有不对的地方…...
Allegro如何知道组合操作命令的拼写
Allegro如何知道组合操作命令的拼写 前面介绍了如何知道单个操作命令的拼写,但如果是复合命令,就无法直观的通过命令来了解,如下图 Snap Pick to -Segment这个命令拼写是什么 如何知道,具体操作如下 点击File点击Script 出现Scripting窗口...
CDO高效处理气象数据
基础命令,只需要在终端输入命令按enter运行即可 ####### 查看文件信息 cdo infos xxx.nc #显示nc文件中的变量名 cdo showname sst.nc #读文件夹下的数据 for i in $(ls);do echo processing $i ;done #线性插值 cdo remapbil,经度纬度 input.nc output.nc ;done ##…...
1. Qt Designer Studio界面介绍
1. 说明: Qt当中的Qt Quick框架使用QML语言来快速搭建优美的界面,但是对于单纯做界面的设计人员并不是很友好,还要让界面设计人员去消耗时间成本学习QML语法。Qt Designer Studio软件就是为了解决这个问题而设计的,工作人员不需要…...
elementUI+vue_vue-admin-template框架
目录安装版本管理文件mock文件夹---模拟数据permission.js --- 登录权限控制文件安装 克隆项目git clone https://gitee.com/panjiachen/vue-admin-template.git进入项目目录cd vue-element-admin安装依赖npm install启动服务npm run dev版本管理 由于我们之前的项目是直接从…...
SpringBoot项目使用Schedule注释创建定时任务
文章目录知识讲解相关注释(主要两个,EnableScheduling和Scheduled)scheduled的cron语法代码项目目录结构启动类(Application)定时任务类(Task)配置类(application.properties)pom依赖展望(Quart…...
学习 Python 之 Pygame 开发魂斗罗(十一)
学习 Python 之 Pygame 开发魂斗罗(十一)继续编写魂斗罗1. 改写主类函数中的代码顺序2. 修改玩家初始化3. 显示玩家生命值4. 设置玩家碰到敌人死亡5. 设置敌人子弹击中玩家6. 修改updatePlayerPosition()函数逻辑继续编写魂斗罗 在上次的博客学习 Pytho…...
Linux驱动开发
一、驱动分类Linux中包含三大类驱动:字符设备驱动、块设备驱动和网络设备驱动。其中字符设备驱动是最大的一类驱动,因为字符设备最多,从led到I2C、SPI、音频等都属于字符设备驱动。块设备驱动和网络设备驱动都要比字符设备驱动复杂。因为其比…...
32--Vue-前端开发-Vue语法之组件化开发
一、vue语法回顾 购物车的例子 eg1:计算商品价格(掌握对象的迭代方法) <!DOCTYPE html> <html lang="en"> <head>...
打怪升级之CFileDialog类介绍
CFileDialog类 CFileDialog封装用于文件打开操作或文件保存操作的常见对话框。信息来源自Windows官方文档:https://learn.microsoft.com/zh-cn/cpp/mfc/reference/cfiledialog-class?viewmsvc-170 这里重点介绍几个常用的函数功能: 构造函数 explic…...
配天智造自主原创数字工厂:百余名员工人均创收122万
配天智造(832223)2022年度报告显示,报告期内公司实现营业收入1.3亿元,同比增长52%,归属于挂牌公司股东的净利润3867万元,同比增长28.11%。而这家公司全部在职员工仅有107人,人均创收约为122万。…...
COLMAP
简介:在使用instant-ngp过程中需要使用COLMAP得到模型的必要输入,比如模型需要的相机外参我们就可以通过COLMAP中的sparse reconstruction稀疏重建得到;而对于depth map深度图我们则需要dense reconstruction稠密重建得到,下面我们…...
2023-3-8 刷题情况
礼盒的最大甜蜜度 题目描述 给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。 返回礼盒的 最大 甜蜜度。…...
关于长连接服务器和客户端之间要加入心跳的一些讨论
在之前的章节里深入浅出TCPIP之深入浅出TCPIP之TCP重传机制 我们都知道了TCPIP协议栈有个默认的TCP心跳机制,这个心跳机制是和socket绑定的,可以对指定的套接字开启协议栈的心跳检测机制。默认情况下,协议栈的心跳机制对socket套接字是关闭的,如果要使用需要人为开启的。 比…...
LeetCode——1590. 使数组和能被 P 整除
一、题目 给你一个正整数数组 nums,请你移除 最短 子数组(可以为 空),使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。 请你返回你需要移除的最短子数组的长度,如果无法满足题目要求,返回 -1…...
12N65-ASEMI高压MOS管12N65
编辑-Z 12N65在TO-220封装里的静态漏极源导通电阻(RDS(ON))为0.68Ω,是一款N沟道高压MOS管。12N65的最大脉冲正向电流ISM为48A,零栅极电压漏极电流(IDSS)为10uA,其工作时耐温度范围为-55~150摄氏度。12N65功耗&#x…...
cushy-serial 一个轻量级Python serial库
本文自笔者博客: https://www.blog.zeeland.cn/archives/rgoihgxcoci3 简介 cushy-serial是一个轻量级的Serial框架,初衷是希望使Serial编程变得更加简单、快捷,因此,相较于传统的pyserial,该框架可以更加快速地构建起一个serial…...
音视频开发系列(7)——Opengl常用Api介绍part1
GLES20.glTexParameteri GLES20.glTexParameteri是OpenGL ES 2.0用于设置纹理过滤器和纹理包装模式的函数。它有三个参数: target参数 target参数指定要设置纹理参数的纹理目标,根据不同的target值,glTexParameteri函数的行为也会有所不同…...
linux时间的特殊用法
今天介绍linux下Date时间命令相关的特殊用法 date (当前的时间) 修改系统当前时间: date -s "2022-6-20 9:33:50" 昨天的时间是我们比较常用的: date -d "yesterday" %Y%m%d ( 昨天的时间) date -d "1 day ago" %Y%m%d …...
axios 封装,API接口统一管理
分享一个自己封装的 axios 网络请求 主要的功能及其优点: 将所有的接口放在一个文件夹中管理(api.js)。并且可以支持动态接口,就是 api.js 文件中定义的接口可以使用 :xx 占位,根据需要动态的改变。动态接口用法模仿…...
SpringBoot使用Redis实现缓存
目录 实现步骤 1. 在 pom.xml 配置文件中添加如下依赖 2. 在 application.properties 中添加如下配置 3. 新建 RedisConfig.class,继承 CachingConfigurerSupport,添加如下方法 4. 新建 RedisService.class 添加如下方法 注意:cacheKey…...
[失业前端恶补算法]JavaScript leetcode刷题top100(三)
专栏声明:只求用最简单的,容易理解的方法通过,不求优化,不喜勿喷 今天更新五个 easy 难度题目: 相交链表 题面 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个…...
Spark RDD的设计与运行原理
一、Spark RDD概念 一个RDD就是一个分布式对象集合,本质上是一个只读的分区记录集合,每个RDD可以分成多个分区,每个分区就是一个数据集片段,并且一个RDD的不同分区可以被保存到集群中不同的节点上,从而可以在集群中的…...
Golang的下载与安装
Windows系统 进入golang官方下载网站:所有版本 - Go 编程语言如图所示 下载后打开您下载的 MSI 文件,然后按照提示安装 Go。 验证是否已安装 Go。...
广州蓝景分享—8大Web前端开发的趋势
2023 年 1 月 11 日,2022 年度 StateOfJS 调查结果正式公布!StateOfJS 是前端生态圈中比较有影响力的且规模较大的数据调查。本文就来解读一下 2022 年 StateOfJS 的调查结果! JavaScript 发展很快,但似乎 JavaScript 开发人员的…...
Java学习-MySQL-创建数据库表
Java学习-MySQL-创建数据库表 SHOW DATABASESUSE school CREATE TABLE IF NOT EXISTS student( id INT(10) NOT NULL AUTO_INCREMENT COMMENT 学号, name VARCHAR(30) NOT NULL DEFAULT 匿名 COMMENT 姓名, pws VARCHAR(20) NOT NULL DEFAULT 123456 COMMENT 密码, sex VARCHA…...
Ethercat学习-GD32以太网学习
文章目录1、GD32F4以太网简介2、以太网模框图简介3、以太网主要模块介绍SMI接口RMII接口与MII接口DMA控制器4、以太网配置流程5、其他1、GD32F4以太网简介 GD32F4系列以太网模块包含10/100Mbps以太网MAC,数据的收发都通过DMA进行操作,支持MII࿰…...
项目规模估算如何精准 4大注意事项
项目报价,需要首先进行项目规模估算,如何估算更精准,6大注意事项。 1、项目范围规划 在项目估算前,需要对项目范围进行规划,这包括所有活动以及开发可交付产品所需的流程。范围规划是前提,它明确定义了项目…...
低代码:助力乡村振兴事业开启“智慧模式”
伴随着脱贫攻坚目标任务的全面完成,我国“三农”工作重心历史性地转向全面推进乡村振兴,这也标志着我国农业农村工作迈上了一个新台阶。 什么是乡村振兴? 乡村振兴是新时代“三农”工作的总抓手,坚持农业农村优先发展,…...
Flutter——Isolate主线机制
简述 在DartFlutter应用程序启动时,会启动一个主线程其实也就是Root Isolate,在Root Isolate内部运行一个EventLoop事件循环。所以所有的Dart代码都是运行在Isolate之中的,它就像是机器上的一个小空间,具有自己的私有内存块和一个运行事件循…...
提取游戏《Limbus Company》(边狱公司)内素材
授人以鱼,不如授人以渔。 目录 注意事项 寻找音频文件 .bytes转为.fsb 必备工具 步骤 解决乱码 必备工具 步骤 提取.fsb文件 必备工具 可备工具 步骤 注意事项 文章关于出现乱码的处理方法和与编码相关的部分有误,已于2023/3/10更正。 相关…...
学生信息表
目录 一、功能说明 二、核心思想 三、所用知识回顾 四、基本框架 五、js功能实现部分 一、功能说明 (1)输入对应的信息,点击录入可以为下面的表格添加一条记录,注意当所填信息不完整时不允许进行提交。 (2&…...
FOTA在AUTOSAR中的应用
FOTA介绍 FOTA(Firmware Over-The-Air)移动终端的空中下载软件升级,指通过云端升级技术,为具有连网功能的设备:例如手机、平板电脑、便携式媒体播放器、移动互联网设备等提供固件升级服务,用户使用网络以按需、易扩展的方式获取智能终端系统升级包,并通过FOTA进行云端升…...
2023/3/10 Vue核心知识的学习- Vue - v-model双向绑定原理
https://www.jianshu.com/p/2682b5a26869 定义:vue中双向绑定就是指v-model指令,可以绑定一个响应式数据到视图,同时视图中变化能同步改变该值。 通过Object.defineProperty( )对属性设置一个set函数,当数据改变了就会来触发这个…...
面朝大海,春暖花开丨2023年Kaadas凯迪仕全国经销商大会成功召开
3月8日,We——2023年Kaadas凯迪仕全国经销商大会将在中国青岛星光岛会议中心隆重举行,盛会汇聚了超过1000名优秀合作伙伴,规模空前。Kaadas凯迪仕品牌创始人&集团总裁苏志勇先生、集团董事长苏祺云先生以及各高层领导均莅临现场。 大会伊…...
【ubuntu】安装cuda+anaconda的docker环境,并用Vscode远程访问
目录下载英伟达docker配置docker的基本安装环境为vscode安装ssh服务安装anaconda下载英伟达docker docker pull nvidia/cuda配置docker的基本安装环境 apt-get install sudo sudo apt-get update sudo apt-get install wget sudo ps -e|grep ssh为vscode安装ssh服务 sudo ap…...
Python(青铜时代)——容器类的公共方法
内置函数 内置函数:不需要使用 import 导入库,就可以直接使用的函数 函数描述备注len()计算容器中元素个数del( )删除变量max( )返回容器中元素最大值如果是字典,只针对key比较min( )返回容器中元素最小值如果是字典,…...
利用canvas给图片添加水印
前言前两天给个人网站添加了一个小功能,就是在文章编辑上传图片的时候自动给图片加上水印。给网页图片添加水印是个常见的功能,也是互联网内容作者保护自己版权的方法之一。本文简单记录一下借助canvas在前端实现图片添加水印的实现方法。canvas元素其实…...
保姆级使用PyTorch训练与评估自己的MobileViT网络教程
文章目录前言0. 环境搭建&快速开始1. 数据集制作1.1 标签文件制作1.2 数据集划分1.3 数据集信息文件制作2. 修改参数文件3. 训练4. 评估5. 其他教程前言 项目地址:https://github.com/Fafa-DL/Awesome-Backbones 操作教程:https://www.bilibili.co…...
Giscus,由 GitHub Discussions驱动的评论系统
在创建网站或博客时,许多人都希望能够为其内容提供评论功能,以与用户进行交流和互动。然而,实现这一点可能会非常复杂,需要处理许多不同的问题,如身份验证、反垃圾邮件、跨站脚本攻击等。为了帮助解决这些问题…...
【JSON文件解析】JSON文件
文章目录概要:本期主要介绍Qt解析JSON数据格式文件的方式。一、JSON数据格式1.JSON类似于XML,在JSON文件中,有且只有一个根节点2.JSON有两种主流包含型构造字符:{对象}、[数组]3.JSON的值主要包括:对象、数组、数字、字…...
OpenGL超级宝典学习笔记:纹理
前言 本篇在讲什么 本篇章记录对OpenGL中纹理使用的学习 本篇适合什么 适合初学OpenGL的小白 本篇需要什么 对C语法有简单认知 对OpenGL有简单认知 最好是有OpenGL超级宝典蓝宝书 依赖Visual Studio编辑器 本篇的特色 具有全流程的图文教学 重实践,轻理…...
主辅助服务市场出清模型研究【旋转备用】(Matlab代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
不用费劲,这5款效率工具为你解决学习工作烦恼
今天我要向大家推荐5款超级好用的效率软件,无论是在学习还是办公中都能够极大地提高效率。这些软件可以帮助你解决许多问题,而且每个都是真正的神器。 1.键盘仿真鼠标——NeatMouse NeatMouse 是一个小型的工具能够使用鼠标光标控制指针。当你的鼠标不…...