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

基础算法之前缀和--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的个数。 算法讲解 这题好像是用滑动窗口解决&#xff0c;但其实不能&#xff0c;因为 nums 中的元素可能存在负数&#xff0c;就不能保证其单调性的性质。 用前缀和求也不易想到&#xff0c;…...

序列化与反序列化基础及反序列化漏洞(附案例)

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

Khronos:动态环境下时空度量语义SLAM的统一方法

Khronos: A Unified Approach for Spatio-Temporal Metric-Semantic SLAM in Dynamic Environments 原文 项目 引言&#xff1a; 人类居住环境通常是高度动态的&#xff0c;人、机器人和其他实体不断移动、互动和改变场景。对于机器人在这种情况下的操作&#xff0c;仅仅建立一…...

一个迷茫的25岁前端程序员的自述

作者&#xff1a;一尾流莺 一直听说程序员的危机在 35 岁&#xff0c;没想到我的危机从 25 岁就开始了。 我甚至不知道自己是不是 25 岁&#xff0c;也可能是 26 岁&#xff0c;或者 27 岁&#xff0c;1998 年的生日&#xff0c;按照 2023 - 1998 的算法就是 25&#xff0c;按…...

多文件并发多线程MD5工具(相对快速的MD5一批文件),适配自定义MD5 Hash I/O缓存。

自己写的多文件 MD5校验工具&#xff0c;一个文件开一个线程&#xff0c;有最大I/O 缓存设置&#xff0c;兼容读写MD5后缀文件。 共计91个文件&#xff0c;合计180G左右 12分钟左右&#xff0c;UI基本卡废&#xff0c;但程序没蹦&#xff0c;属于正常。 卡的原因是基本是用 I/O…...

Pikachu-url重定向-不安全的url跳转

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

如何下载和安装CLion,图文详解

一、下载 登录JetBrains官网&#xff0c;下载最新版本的Clion&#xff0c;Clion目前没有社区版&#xff0c;都是专业版。 二、安装 1、启动Clion安装程序&#xff0c;下一步。 2、修改安装目录&#xff0c;下一步。 3、创建桌面快捷方式&#xff0c;更新PATH变量&#xff0…...

vue3导入本地图片2种实现方法

在<script setup>中使用import语法&#xff1a; <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. 爬楼梯 (进阶))

完全背包 完全背包的每件商品都有无限个&#xff0c;和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次&#xff0c;01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的&#xff0c;所以要从小到大去遍历。 518. 零钱兑换 II 思路&#…...

检查jar冲突,查找存在相同class的jar

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

PhpStudy-PHP5.4.45后门漏洞应用程序(C++/base64/winhttp)

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

【优选算法】(第二十七篇)

目录 重排链表&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 合并K个升序链表&#xff08;hard&#xff09; 题目解析 讲解算法原理 编写代码 重排链表&#xff08;medium&#xff09; 题目解析 1.题目链接&#xff1a;. - 力扣&#xff08;LeetCod…...

学习Flask框架

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

Elasticsearch:使用 LLM 实现传统搜索自动化

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

人脸表情行为识别系统源码分享

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

ThreadLocal原理解析及面试

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

探索未来:mosquitto-python,AI领域的新宠

文章目录 探索未来&#xff1a;mosquitto-python&#xff0c;AI领域的新宠背景&#xff1a;为何选择mosquitto-python&#xff1f;库简介&#xff1a;mosquitto-python是什么&#xff1f;安装指南&#xff1a;如何安装mosquitto-python&#xff1f;函数用法&#xff1a;5个简单…...

C++版iwanna1

第一篇目录 开头程序Game.cpp源文件Player.h头文件Player.cpp源文件trigger.h头文件trigger.cpp源文件Cmp.h头文件Cmp.cpp源文件 开头 大家好&#xff0c;我叫这是我58。 程序 Game.cpp源文件 #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <c…...

LSTM变种模型

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

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 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

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

YSYX学习记录(八)

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

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; 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协议网关详解

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

IT供电系统绝缘监测及故障定位解决方案

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

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

工厂方法模式和抽象工厂方法模式的battle

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