当前位置: 首页 > 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…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...