当前位置: 首页 > news >正文

算法:974.和可以被K整除的子数组

题目

链接:leetcode链接

在这里插入图片描述

思路分析(前缀和 + 同余定理)

首先,我们要了解一下什么是同余定理

同余定理:
如果(a - b)/ p = k …… 0
则 a % p == b % p

证明我写在草稿纸上,如下图:
在这里插入图片描述

初此之外,我们还需要理解一个问题
在C++/java中负数取模会怎么样呢?
比如 - 2 % 5等于多少呢?
按道理来说应该是3,但是C++/java里的答案是-2
这明显是需要进行修正的

如何进行修正呢?
我们只需要( a % p + p)% p
这样,无论是正数取模还是负数取模都不会出现问题。

OK,到这里前置知识讲完了,我们就正式开始讲思路了。

需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。

和这道题的思路非常相似
传送门:560.和为k的子数组

我们利用滚动数组去求前缀和,
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中(一定要是先查找在插入)

细节:
(1)什么时候插入hash表
一定要是先查找,在插入
(2)对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样,我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章

代码

//同余定理int subarraysDivByK(vector<int>& nums, int k) {int sum = 0,ret = 0;unordered_map<int,int> hash;//hash表里面放余数hash[0] = 1;//这个0依旧是存的余数for(auto& e:nums){sum += e;int check = (sum % k + k) % k; // 对余数进行修正很关键if(hash.count(check))  ret += hash[check]; hash[check]++;}return ret;}

相关文章:

算法:974.和可以被K整除的子数组

题目 链接:leetcode链接 思路分析&#xff08;前缀和 同余定理&#xff09; 首先&#xff0c;我们要了解一下什么是同余定理 同余定理&#xff1a; 如果&#xff08;a - b&#xff09;/ p k …… 0 则 a % p b % p 证明我写在草稿纸上&#xff0c;如下图&#xff1a; 初…...

QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)

本节学习&#xff1a;HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 ‍ 一、font 标签 用途&#xff1a;定义文本的字体大小、颜色和 face&#xff08;字体类型&#xff09;。 示例 <!DOCTYPE html> <html><head><meta cha…...

红米Turbo 3工程固件预览 修复底层 体验原生态系统 默认开启diag端口

红米Turbo 3机型代码:peridot 国外版本:POCO F6 用于以下型号的小米机型:24069RA21C, 24069PC21G, 24069PC21I。搭载1.5K OLED屏、骁龙8s处理器、5000mAh电池+90W快充、5000万像素主摄。 通过博文了解 1💝💝💝-----此机型工程固件的资源刷写注意事项 2💝💝�…...

sql的调优指南及高级sql技巧

SQL调优是优化数据库性能的重要手段&#xff0c;涉及编写高效的SQL查询、合理设计索引、优化数据库结构等。以下是一些SQL调优指南和高级技巧&#xff1a; SQL调优指南 选择合适的查询方式&#xff1a; **避免使用SELECT ***&#xff1a;仅选择所需的列&#xff0c;减少数据传…...

生成式专题的第一节课---GAN图像生成

一、GAN的起源与发展 1.GAN的起源 GAN &#xff08;生成式对抗网络&#xff09;诞生于 2014 年&#xff0c;由 Ian Goodfellow 提出&#xff0c;是用于生成数据的深度学习模型&#xff0c;创新点是对抗性训练&#xff0c;即生成器与判别器的竞争关系&#xff0c;为图像生成、…...

中科星图GVE(案例)——AI实现建筑用地变化前后对比情况

目录 简介 函数 gve.Services.AI.ConstructionLandChangeExtraction(image1,image2) 代码 结果 知识星球 机器学习 简介 AI可以通过分析卫星图像、航拍影像或其他地理信息数据&#xff0c;实现建筑用地变化前后对比。以下是一种可能的实现方法&#xff1a; 数据获取&am…...

Spring Boot中获取application.yml中属性的几种方式

在Spring Boot应用程序中&#xff0c;可以通过多种方式从application.yml文件中获取配置属性。以下是几种常见的方法&#xff1a; 1. 使用Value注解 你可以使用Value注解将application.yml中的属性注入到Spring管理的bean中。 application.yml app:name: MySpringBootAppve…...

YOLO11改进 | 注意力机制 | 结合静态和动态上下文信息的注意力机制

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 上下文Transformer&#xff08;CoT&…...

Python中函数的使用方法

1 问题 在python的学习中&#xff0c;一个相同的程序可能会有多种不同的代码输入方式&#xff0c;那么函数这种方式是否方便快捷呢&#xff1f;今天我们来简单介绍函数的部分使用方法。 2 方法 定义函数&#xff1a;代码清单1Def function name (arguments):return result在上面…...

遨游智能终端赋能“危急特”场景,力推北斗技术规模化应用!

随着《北斗规模应用三年行动计划&#xff08;2023-2025&#xff09;》的发布&#xff0c;北京、湖北、重庆等多地出台北斗支持政策&#xff0c;北斗系统正稳步迈向“安全可控&#xff0c;泛在融合&#xff0c;开放兼容&#xff0c;服务全球”的发展目标。遨游通讯紧跟国家战略步…...

构建流媒体管道:利用 Docker 部署 Nginx-RTMP 从 FFmpeg RTMP 推流到 HLS 播放的完整流程

最近要实现一个类似导播台的功能&#xff0c;于是我先用 FFmpeg 实现一个参考对照的 Demo&#xff0c;我将其整理为一篇文章&#xff0c;方便后续大家或者和自己参考&#xff01; 1、软件工具介绍 本次部署相关软件 / 工具如下&#xff1a; FFmpeg&#xff1a;全称是 Fast Fo…...

【汇编语言】寄存器(CPU工作原理)(六)—— 修改CS,IP的指令以及代码段

文章目录 前言1. 修改CS、IP的指令2. 问题分析:CPU运行的流程3. 代码段小结结语 前言 &#x1f4cc; 汇编语言是很多相关课程&#xff08;如数据结构、操作系统、微机原理&#xff09;的重要基础。但仅仅从课程的角度出发就太片面了&#xff0c;其实学习汇编语言可以深入理解计…...

机器学习与神经网络:从技术前沿到诺贝尔奖的跨越与未来展望

近日&#xff0c;2024年诺贝尔物理学奖颁发给了机器学习与神经网络领域的研究者&#xff0c;这是历史上首次出现这样的情况。这项奖项原本只授予对自然现象和物质的物理学研究作出重大贡献的科学家&#xff0c;如今却将全球范围内对机器学习和神经网络的研究和开发作为了一种能…...

java 洛谷题单【数据结构1-2】二叉树

P4715 【深基16.例1】淘汰赛 解题思路 半区分配&#xff1a;将前半部分国家分配到左半区&#xff0c;后半部分国家分配到右半区&#xff0c;分别找到两个半区的最强国家。决赛和亚军确定&#xff1a;最后比较两个半区最强国家的能力值&#xff0c;失败者即为亚军&#xff0c;输…...

项目优化内容及实战

文章目录 事前思考Prometheus 普罗米修斯概述架构安装及使用 Grafana可视化数据库读写分离实战1-PrometheusGrafanaspringboot 事前思考 需要了解清楚&#xff1a;需要从哪些角度去分析实现&#xff1f;使用了缓存&#xff0c;就需要把缓存命中率数据进行收集&#xff1b;使用…...

科研绘图系列:R语言蝴蝶图(Butterfly Chart)

文章目录 介绍加载R包数据函数画图系统信息介绍 蝴蝶图(Butterfly Chart),也被称为龙卷风图(Tornado Chart)或双轴图(Dual-Axis Chart),是一种用于展示两组对比数据的图表。这种图表通过在中心轴两侧分别展示两组数据的条形图,形似蝴蝶的翅膀,因此得名。蝴蝶图的特点…...

【FPGA开发】Modelsim如何给信号分组

前面已经发布过了一篇关于 Modelsim 的入门使用教程&#xff0c;针对的基本是只有一个源文件加一个仿真tb文件的情况&#xff0c;而实际的工程应用中&#xff0c;往往是顶层加多个底层的源文件结构&#xff0c;如果不对信号进行一定的分组&#xff0c;就会显得杂乱不堪&#xf…...

Apache SeaTunnel 9月份社区发展记录

各位热爱 SeaTunnel 的小伙伴们&#xff0c;9月份社区月报来啦&#xff01;这里将定期更新SeaTunnel社区每个月的重大进展&#xff0c;欢迎关注&#xff01; 月度Merge Stars 感谢以下小伙伴上个月为 Apache SeaTunnel 做的精彩贡献&#xff08;排名不分先后&#xff09;&…...

系统架构设计师:数据库系统相关考题预测

作为系统架构设计师,在准备数据库系统相关的考试时,可以预期到的一些关键知识点包括但不限于以下几个方面: 数据库类型: 关系型数据库(RDBMS)与非关系型数据库(NoSQL)的区别及其适用场景。数据库管理系统(DBMS)的功能及组成部分。数据模型: 如何设计ER模型(实体-关…...

污水排放口细粒度检测数据集,污-水排放口的类型包括10类目标,10000余张图像,yolo格式目标检测,9GB数据量。

污水排放口细粒度检测数据集&#xff0c;污-水排放口的类型包括10类目标&#xff08;1 合流下水道&#xff0c;2 雨水&#xff0c;3 工业废水&#xff0c;4 农业排水&#xff0c;5 牲畜养殖&#xff0c;6 水产养殖&#xff0c;7 地表径流&#xff0c;8 废水处理厂&…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...