基础算法之前缀和--Java实现(下)--LeetCode题解:-和为 K 的子数组 - 和可被 K 整除的子数组 -连续数组-矩阵区域和
这里是Themberfue
和为 K 的子数组
题目解析
返回子数组中所有元素的和等于给定k的个数。
算法讲解
· 这题好像是用滑动窗口解决,但其实不能,因为 nums 中的元素可能存在负数,就不能保证其单调性的性质。
· 用前缀和求也不易想到,但是我们应该换个角度看问题,既然是某一段的和,这一段的起点可能是从0开始,也可能不从0开始。
· 也就是说,要想满足题目要求的话,那么就构成一个等式,当前 i 的前缀和减去 k 肯定等于i 前些前缀和的某个前缀和。
· 如图所示,也就是若出现让这个等式成立的情况,那么从 0 到 i 这一范围内,肯定存在满足题目要求的子数组,可能不止一个。
· 所以我们借助哈希表解题,并将当前 i 的前缀和以及出现的次数的存入哈希表中,若该哈希表中存在 前缀和 - k,那么就让计数器加上其出现的次数。
· 细节:
1. 前缀和为0时,其次数应该初始化为1,因为可能存在 sum - k = 0的情况,这也是满足题目条件的。
2. 我们不用真的创建一个前缀和数组,只需要维护一个 sum 就好,然后将当前的 sum 加入到哈希表中即可。
编写代码
class Solution {public int subarraySum(int[] nums, int k) {// 创建哈希表标记前缀和出现的次数Map<Integer, Integer> hash = new HashMap<>();hash.put(0, 1);int sum = 0, count = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];count += hash.getOrDefault(sum - k, 0);hash.put(sum, hash.getOrDefault(sum, 0) + 1);}return count;}
}
和可被 K 整除的子数组
题目解析
返回子数组中所有元素的和可以被k整除的个数。
算法讲解
· 本题借助一个数学定理解题会更方便 => 同余定理
· 假设两数字 i 和 j,这两数的差除以任一数,若可以整除得到 k。即 (i - j) / p == k ...... 0
· 则 i % p == j % p
· 利用这一定理,便可求解出题目,思路和上一题差不多。
· 细节:对于负数的取余,需要作特殊情况。
编写代码
class Solution {public int subarraysDivByK(int[] nums, int k) {// 存放前缀和的余数以及出现的次数Map<Integer, Integer> hash = new HashMap<>();hash.put(0, 1);// 根据同余定理int sum = 0, count = 0;for (int x: nums) {sum += x; // 计算当前位置的前缀和int mod = (sum % k + k) % k; // Java取模的特殊性,当被除数为负数时取模结果为负数,需要纠正count += hash.getOrDefault(mod, 0);hash.put(mod, hash.getOrDefault(mod, 0) + 1);}return count;}
}
连续数组
题目解析
这是一个只含 0 和 1 的数组,找到数组中 0 和 1 数量相同的子数组,返回最长子数组的长度
算法讲解
· 既然是相同数量的 0 和 1,如果把 0 都变成 -1,那么相同数量 0 和 1 的子数组的和就一定是 0
· 利用这一性质,i 下标的前缀和若与之前下标的前缀和相同,则存在这样的子数组,更新长度。
· 即 sum - x = 0
编写代码
class Solution {public int findMaxLength(int[] nums) {// 存放前缀和和对应的下标Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1); // 前缀和为0所对应的下标应该为-1// 转化为和为0的子数组int sum = 0, len = 0; for (int i = 0; i < nums.length; i++) {sum += nums[i] == 0 ? -1 : 1; // 将所有的0转化为-1// 不需要每次都更新key为sum的值,只需更新一次即可if (hash.containsKey(sum)) len = Math.max(len, i - hash.get(sum)); // 存在与当前sum相同的前缀和,则更新数据else hash.put(sum, i); // 不存在,则将其放入哈希表}return len;}
}
矩阵区域和
题目解析
求出 (i - k, j - k) 到 (i + k, j + k) 之间的和即可。
算法讲解
· 本题使用二维前缀和,首先根据公式创建出前缀和数组。
· 随后根据题目要求,求出 x1,x2,y1,y2坐标。
· 最后带入公式即可。
· 细节:注意下标映射关系以及边界处理。
编写代码
class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {// 创建dp二维前缀和数组int m = mat.length + 1, n = mat[0].length + 1;int[][] dp = new int[m][n];for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j-1] + mat[i - 1][j - 1] - dp[i-1][j-1];}}int[][] answer = new int[m - 1][n - 1];for (int i = 0; i < m - 1; i++) {for (int j = 0; j < n - 1; j++) {int x1 = Math.max(i - k, 0), x2 = Math.min(i + k, m - 2);int y1 = Math.max(j - k, 0), y2 = Math.min(j + k, n - 2);answer[i][j] = dp[x2 + 1][y2 + 1] - dp[x1][y2 + 1] - dp[x2 + 1][y1] + dp[x1][y1];}}return answer;}
}
好了,以上就是今天内容的全部讲解,如果有不懂的地方,随时私聊😘
我们下一章节见 => 位运算😁
相关文章:

基础算法之前缀和--Java实现(下)--LeetCode题解:-和为 K 的子数组 - 和可被 K 整除的子数组 -连续数组-矩阵区域和
这里是Themberfue 和为 K 的子数组 题目解析 返回子数组中所有元素的和等于给定k的个数。 算法讲解 这题好像是用滑动窗口解决,但其实不能,因为 nums 中的元素可能存在负数,就不能保证其单调性的性质。 用前缀和求也不易想到,…...

序列化与反序列化基础及反序列化漏洞(附案例)
参考文章: [web安全原理]PHP反序列化漏洞 - 笑花大王 - 博客园 (cnblogs.com) 一、概念 为了能有效的存储数据而不丢失数据的类型和内容,经常需要通过序列化对数据进行处理,将数据进行序列化后,会生成一个字符串,字符…...

Khronos:动态环境下时空度量语义SLAM的统一方法
Khronos: A Unified Approach for Spatio-Temporal Metric-Semantic SLAM in Dynamic Environments 原文 项目 引言: 人类居住环境通常是高度动态的,人、机器人和其他实体不断移动、互动和改变场景。对于机器人在这种情况下的操作,仅仅建立一…...
一个迷茫的25岁前端程序员的自述
作者:一尾流莺 一直听说程序员的危机在 35 岁,没想到我的危机从 25 岁就开始了。 我甚至不知道自己是不是 25 岁,也可能是 26 岁,或者 27 岁,1998 年的生日,按照 2023 - 1998 的算法就是 25,按…...

多文件并发多线程MD5工具(相对快速的MD5一批文件),适配自定义MD5 Hash I/O缓存。
自己写的多文件 MD5校验工具,一个文件开一个线程,有最大I/O 缓存设置,兼容读写MD5后缀文件。 共计91个文件,合计180G左右 12分钟左右,UI基本卡废,但程序没蹦,属于正常。 卡的原因是基本是用 I/O…...

Pikachu-url重定向-不安全的url跳转
不安全的url跳转 不安全的url跳转问题可能发生在一切执行了url地址跳转的地方。如果后端采用了前端传进来的(可能是用户传参,或者之前预埋在前端页面的url地址)参数作为了跳转的目的地,而又没有做判断的话就可能发生"跳错对象"的问题。 url跳转比较直接的危害是: …...

如何下载和安装CLion,图文详解
一、下载 登录JetBrains官网,下载最新版本的Clion,Clion目前没有社区版,都是专业版。 二、安装 1、启动Clion安装程序,下一步。 2、修改安装目录,下一步。 3、创建桌面快捷方式,更新PATH变量࿰…...
vue3导入本地图片2种实现方法
在<script setup>中使用import语法: <template><img :src"logo" alt"Logo"> </template><script setup> import logo from ./assets/logo.png; </script> 使用Vue的ref来动态地在<script setup>中…...
leetcode 刷题day36动态规划Part05 背包问题(完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯 (进阶))
完全背包 完全背包的每件商品都有无限个,和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次,01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的,所以要从小到大去遍历。 518. 零钱兑换 II 思路&#…...

检查jar冲突,查找存在相同class的jar
写在前面 本文看下如何查找jar冲突,即查找哪些jar包中存在相同的class。如果是存在相同jar的不同版本,基本一眼就能看出来,然后结合maven的依赖关系将其剔除掉即可,但是当你遇到了有人手动拷贝某些class到jar包中导致冲突的情况时…...

PhpStudy-PHP5.4.45后门漏洞应用程序(C++/base64/winhttp)
PhpStudy-PHP5.4.45后门漏洞应用程序(C/base64/winhttp) 前言引言(时间回到多年前) PhpShellCmd.exe使用介绍:(1)输入网址检测是否存在PHP/5.4.45(2)whoami(3…...

【优选算法】(第二十七篇)
目录 重排链表(medium) 题目解析 讲解算法原理 编写代码 合并K个升序链表(hard) 题目解析 讲解算法原理 编写代码 重排链表(medium) 题目解析 1.题目链接:. - 力扣(LeetCod…...

学习Flask框架
Flask简介 Flask是一个使用 Python 编写的轻量级 Web 应用框架。其 WSGI 工具箱采用 Werkzeug ,模板引擎则使用 Jinja2 。Flask使用 BSD 授权。 Flask也被称为 “microframework” ,因为它使用简单的核心,用 extension 增加其他功能。Flask没…...

Elasticsearch:使用 LLM 实现传统搜索自动化
作者:来自 Elastic Han Xiang Choong 这篇简短的文章是关于将结构化数据上传到 Elastic 索引,然后将纯英语查询转换为查询 DSL 语句,以使用特定过滤器和范围搜索特定条件。完整代码位于此 Github repo 中。 首先,运行以下命令安装…...

人脸表情行为识别系统源码分享
人脸表情行为识别系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…...

ThreadLocal原理解析及面试
基本使用 讲原理之前,我简单写个demo小程序说说怎么使用 public class TestThreadLocal {public static void main(String[] args) throws InterruptedException {ThreadLocal<String> tl new ThreadLocal();/**主线程设置了一个值*/tl.set("SSSSSs&…...

探索未来:mosquitto-python,AI领域的新宠
文章目录 探索未来:mosquitto-python,AI领域的新宠背景:为何选择mosquitto-python?库简介:mosquitto-python是什么?安装指南:如何安装mosquitto-python?函数用法:5个简单…...
C++版iwanna1
第一篇目录 开头程序Game.cpp源文件Player.h头文件Player.cpp源文件trigger.h头文件trigger.cpp源文件Cmp.h头文件Cmp.cpp源文件 开头 大家好,我叫这是我58。 程序 Game.cpp源文件 #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <c…...

LSTM变种模型
一、GRU 1.概念 GRU(门控循环单元,Gated Recurrent Unit)是一种循环神经网络(RNN)的变体,旨在解决标准 RNN 在处理长期依赖关系时遇到的梯度消失问题。GRU 通过引入门控机制简化了 LSTM(长短期…...

Python进阶--函数进阶
目录 1. 函数多返回值 2. 函数多种传参方式 (1). 位置参数 (2). 关键字参数 (3). 缺省参数 (4). 不定长参数 3. 匿名函数 (1). 函数作为参数传递 (2). lambda匿名函数 1. 函数多返回值 def return_num():return 1# 返回1之后就不会再向下继续执行函数体return 2 resu…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...

工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...