使数组和能被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套接字是关闭的,如果要使用需要人为开启的。 比…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...
