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

【专题四】前缀和（3）

news 来源：原创 2025/5/25 1:04:27

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

视频

974. 和可被 K 整除的子数组
- 个人解
- 优质解
525. 连续数组
- 个人解
- 优质解
1314. 矩阵区域和
- 个人解

974. 和可被 K 整除的子数组

题目链接：974. 和可被 K 整除的子数组

在这里插入图片描述

个人解

思路：
和上篇文章的第三题一样，但是，因为哈希表里面可能有多个前缀和都满足要求，而我没想到如何快速搜索到这些前缀和。
暴力解法：O( $n^2$ )是过不了的。

优质解

思路：

哈希表里面有多个前缀和满足要求是因为：可能出现dp[x2] = dp[x1] + k的情况（即两数之间差nk），导致对于dp[i]，可能有多个前缀和与之匹配。那如何保证唯一且能把这些数全部统计到呢？
我们可以在记录前缀和的时候，不记录前缀和，而是记录前缀和 % k的余数。
因为：如果(dp[i] - dp[x]) % k == 0，则dp[i] % k == dp[x] % k
细节问题：我们的数组中有负数，但是C++ 中的取模性质：负数 % 正数 == 负数。所以我们要对模出来的结果进行修正
修正：对于负数结果修正：余数 = dp[i] % k + k，但是为了正负数同一：余数 = (dp[i] % k + k) % k

代码：

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;int ans = 0, sum = 0;hash[0] = 1;for(auto x: nums){sum += x; // sum代表当前位置的前缀和int modulus = (sum % k + k) % k;if(hash.count(modulus)) ans += hash[modulus];hash[modulus]++;}return ans;}
};

时间复杂度：O( $n$ )
空间复杂度：O( $n$ )

525. 连续数组

题目链接：525. 连续数组

在这里插入图片描述

个人解

思路：
脑子锈了，只能想到O( $n^2$ )的解法。

优质解

思路：

把 0 变-1
问题变成：找子数组所有元素和为0的最长子数组。
细节1：哈希表存储什么？答：<前缀和，下标>，并且如果遇到相同的前缀和，下标大的不存（因为子数组短）
细节2：当前位置的信息使用完以后才存入哈希表，不然dp[i] - dp[i]这个子数组实际为空
细节3：默认前缀和0的位置要存在-1

代码：

class Solution {
public:int findMaxLength(vector<int>& nums) {int ans = 0, sum = 0;unordered_map<int, int> hash;hash[0] = -1;for(int i = 0; i < nums.size(); i++){sum += (nums[i] == 0? -1 : 1);if(hash.count(sum)) ans = max(ans, i - hash[sum]);elsehash[sum] = i;}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

1314. 矩阵区域和

题目链接：1314. 矩阵区域和

在这里插入图片描述

个人解

这道题和文章中第二题很像，这道题麻烦在下标对应。
思路：

题意：answer中每一格表示的是：以mat[r][c]为中心的，边长为2k+1的正方形中所有元素（且在mat中）的和
建立一个二维前缀和数组：dp[i][j]代表mat 的 [0, 0]到[i, j]这个矩阵内的元素和
然后利用这个前缀和数组来填写answer
下标对应：初始化时：因为mat的元素是从下标[0, 0]开始的，所以dp[i][j]加的应该是mat[i - 1][j - 1]
使用时：dp[1][1]才对应mat的第一个元素，所以，在使用dp的时候下标都要-1

用时：20:00
屎山代码：

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));vector<vector<int>> answer(m, vector<int>(n, 0));// 初始化前缀和数组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] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int x1 = max(0, i - k);int y1 = max(0, j - k);int x2 = min(m - 1, i + k);int y2 = min(n - 1, j + k);answer[i][j] = dp[x2 + 1][y2 + 1] - dp[x1][y2 + 1] - dp[x2 + 1][y1] + dp[x1][y1];}}return answer;}
};

时间复杂度：O( $m * n$ )
空间复杂度：O( $m * n$ )

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！

【专题四】前缀和（3）

📝前言说明： 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分每题主要记录：（1）本人解法本人屎山代码；（2）优质解法优质代码；&#xff…...

编程日记 2025/5/25 1:04:27

STM32 USB配置详解

STM32 USB配置详解一、USB基础概念 1.1 USB简介 USB (Universal Serial Bus) 是一种用于计算机与外部设备连接的串行总线标准，具有热插拔、即插即用等特点。STM32微控制器内置了多种USB接口，可实现各类USB应用。 1.2 USB速度等级 Low Speed (LS): …...

编程日记 2025/5/25 0:32:20

2025年Mapbox零基础入门教程（1）地图初始化

什么是mapbox？ mapbox是一个地图框架，不仅提供前端渲染能力，还具备后端服务接口能力。相较于openlayers，它可构建二维和三维地图，并支持优化导航路线和位置查询等功能。开发中使用mapbox需引入库文件并设置token&…...

编程日记 2025/5/25 0:00:31

课外知识：你需要了解的Python类对象里面的getattr方法

你需要了解的Python类对象中的__getattr__方法一、__getattr__基础概念 1. 方法定义 def __getattr__(self, name: str) -> Any:"""当访问不存在的属性时触发"""2. 核心特性动态属性处理：拦截未定义的属性访问按需触发&…...

编程日记 2025/5/25 0:10:29

openGauss新特性 | DataKit支持PostgreSQL到openGauss的迁移能力

Postgresql-\>openGauss迁移工具debezium-connector-postgres 可获得性本特性自openGauss 7.0.0-RC1版本开始引入。特性简介 debezium-connector-postgres工具是一个基于Java语言的Postgresql到openGauss的复制工具。该工具提供了初始全量数据及对象（视图、…...

编程日记 2025/5/25 0:49:15

【前端】跟进新趋势- PWA WebAssembly

不定期更新及补充实战。建议关注收藏点赞。目录 PWA（渐进式 Web 应用，Progressive Web App）WebAssembly（WASM） PWA（渐进式 Web 应用，Progressive Web App） PWA 是一种提升 Web 应用…...

编程日记 2025/5/25 0:22:53

C++学习：六个月从基础到就业——模板编程：SFINAE原则

C学习：六个月从基础到就业——模板编程：SFINAE原则本文是我C学习之旅系列的第三十六篇技术文章，也是第二阶段"C进阶特性"的第十四篇，主要介绍C模板编程中的SFINAE原则。查看完整系列目录了解更多内容。目录 C学习之…...

编程日记 2025/5/24 6:24:49

完美解决.NET Framework 4.0 中 System.Drawing 库不支持 WebP 格式的图像处理

如果你想在 .NET Framework 4.0 中使用 ImageMagick 处理图片，可以通过 Magick.NET 库来实现。Magick.NET 是 ImageMagick 的 .NET 封装，可以用来读取、写入、编辑图像。以下是如何使用 Magick.NET 来处理图像并提取图像的宽度和高度。步骤&#xff…...

编程日记 2025/5/24 14:12:21

网络基础概念：从菜鸟到入门

前言：快递小哥的故事想象一下你要给朋友寄个礼物，这个过程其实和网络通信非常相似： 1. 你需要知道朋友的”地址“（IP地址） 2. 要注明是送到他家大门还是物业代收（端口号） 3. 要选择快递公司并…...

编程日记 2025/5/18 11:24:21

优先队列和单调队列（双端队列实现的）

这里写自定义目录标题一、优先队列与单调队列二、优先队列2.1 概念2.2 增删查判空2.3 示例代码三、双端队列四、单调队列4.1 单调递增队列4.2 单调递减队列一、优先队列与单调队列二、优先队列 2.1 概念一种特殊的队列，它与普通队列的主要区别在于元素的出…...

编程日记 2025/5/24 23:18:59

设计模式（状态模式）

概述在实际的软件开发中，状态模式并不是很常用，但是在能够用到的场景里，它可以发挥很大的作用。从这一点上来看，它有点像我们之前讲到的组合模式。状态模式一般用来实现状态机，而状态机常用在游戏、工作流引擎等系统…...

编程日记 2025/5/25 0:50:37

安卓基础（get和set）

在 Java 中，get 和 set 方法是面向对象编程中封装（Encapsulation） 的核心实现，用于安全地访问和修改类的私有字段（private 成员变量）。它们的核心作用是控制对数据的访问&#xff0c…...

编程日记 2025/5/24 6:41:35

机器人灵巧操作新突破，力感知技术让机械手更精准

在机器人的发展历程中，让机器人实现灵活操作一直是科研人员努力攻克的难题。我们这篇文章给大家带来一份新的工作：DexForce 链接：[2501.10356] DexForce: Extracting Force-informed Actions from Kinesthetic Demonstrations for Dextero…...

编程日记 2025/5/25 0:03:37

八大排序——直接插入排序/希尔排序

八大排序——直接插入排序/希尔排序目录一、直接插入排序二、希尔排序一、直接插入排序每一趟从待排序序列中取第一个值，将其插入到已排序好的序列中，对已排序好的序列，从右到左依次和待插入值比较，如果大于则向后挪&…...

编程日记 2025/5/25 0:42:55

一、ab压力测试 # ab ‐c 100 ‐n 1000 http://vedio.linux.com/index.html 2 This is ApacheBench, Version 2.3 <$Revision: 1430300 $> 3 Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/ 4 Licensed to The Apache Software Foundation,…...

编程日记 2025/5/24 22:45:11

node.js 实战——mongoDB

MongoDB MongoDB 简介 MongoDB 是一种基于文档型 (document-oriented) 的 NoSQL 数据库，使用类 JSON 的 BSON 格式存储数据，自然支持复杂数据结构。它特别适合需要快速变化、大量数据处理和高应用扩展性的场景。 MongoDB 特性： 无法表、无…...

编程日记 2025/4/29 9:12:53

C语言学习路线

以下是一份综合多个优质资源的C语言学习路线规划，结合2025年最新技术趋势和工程实践需求，分为三个阶段系统推进： 一、入门阶段（1-2个月） 目标：掌握基础语法，能编写简单程序&#xff…...

编程日记 2025/4/29 9:12:52

飞凌嵌入式T527核心板获得【OpenHarmony生态产品兼容性证书】

近日，飞凌嵌入式FET527-C核心板通过OpenHarmony 4.1 Release版本兼容测评，获得【OpenHarmony生态产品兼容性证书】。飞凌嵌入式FET527-C核心板搭载全志T527系列全国产高性能处理器，集成8个ARM Cortex-A55核心，并内置RISC-V核和DS…...

编程日记 2025/5/17 23:40:56

Mioty｜采用报文分割（Telegram Splitting）以提高抗干扰能力的无线通信技术

1、什么是Mioty 在物联网（IoT）快速发展的背景下，低功耗广域网（LPWAN）技术成为连接海量设备的关键。LPWAN具有低功耗、低成本、广覆盖和强抗干扰能力等特点，使其特别适用于大规模、远距离、低数据速率的IoT…...

编程日记 2025/5/25 0:55:17

WPF 程序监控硬件设备状态变化的实现方案

以下是一个完整的 C# WPF 程序实现方案，用于监控硬件设备状态变化（基于设备 SDK API）。我们将分步骤实现，包含状态轮询、事件通知、UI 绑定和错误处理。 1. 项目结构设计 HardwareMonitor/ ├── Models/ # 数据模…...

编程日记 2025/5/3 8:10:14

利用Python打印有符号十进制数的二进制原码、反码、补码

有时候手动计算有符号十进制数的二进制原码、反码、补码是一件挺麻烦的事情。下面是一个段Python 代码，它可以接收一个 16 位有符号十进制数的输入，然后输出其对应的二进制原码、反码和补码： def decimal_to_binary(decimal_num):# 检查输入…...

编程日记 2025/5/2 3:11:55

STM32裸机编程架构与思路

STM32作为广泛应用的微控制器系列，其强大的功能和灵活的编程方式使其成为嵌入式系统开发的优选。裸机编程（bare-metal programming）指的是在没有操作系统支持的情况下，直接对硬件进行编程。这种方式虽然较为底层，但能够…...

编程日记 2025/5/18 8:44:26

Eureka 深度解析：从原理到部署的全场景实践

一、Eureka 核心原理与架构设计 1. 核心定位与组件模型 Eureka 是 Netflix 开源的服务发现（Service Discovery）组件，作为 Spring Cloud 微服务体系的核心基础设施，其核心目标是解决分布式系统中服务实例动态管理与跨服务通信解耦…...

编程日记 2025/5/22 10:11:36

有哪些和PPT自动生成有关的MCP项目？

随着AI技术的快速发展， Model Context Protocol（MCP）作为一种连接大型语言模型（LLMs）与外部工具的开放协议，正在重塑自动化办公领域。在PPT自动生成场景中，MCP通过标准化接口实现了AI模型与设计工具、数据源的无缝整合。以下从技术框架、项目案例、应用场景三个维度展开…...

编程日记 2025/4/29 9:10:42

经典数仓架构深度解析与演进：从离线处理到新型架构对比

经典数仓架构深度解析与演进：从离线处理到新型架构对比在数据驱动决策的时代，经典数仓作为企业数据管理与分析的核心基础设施，承载着从数据存储到价值挖掘的重要使命。本文将深入剖析经典数仓的架构、数据处理流程、主流架构模式及其对比&a…...

编程日记 2025/4/29 9:10:40

[Python开发] 如何用 VSCode 编写和管理 Python 项目（从 PyCharm 转向）

在 Python 开发领域，PyCharm 一直是广受欢迎的 IDE，但其远程开发功能（如远程 SSH 调试）仅在付费版中提供。为了适应服务器部署需求，很多开发者开始将目光转向更加轻量、灵活且免费扩展能力强的 VSCode。本篇文章将详细介绍，从 PyCharm 转向 VSCode 后，如何高效搭建和管理…...

编程日记 2025/5/13 2:52:01

系统架构-架构评估

质量属性性能指系统的响应能力指标：响应时间、吞吐量等。设计策略：优先级队列、增加计算资源、减少计算开销、引入并发机制、采用资源调度可靠性在意外或错误使用的情况下维持软件系统的功能特性指标：MTTF、MTBF、MTTR 设计策…...

编程日记 2025/4/29 9:10:39

使用 MQTT - C 访问 IoTDA 平台：一个完整的嵌入式示例

引言在物联网（IoT）开发领域，设备与平台之间的通信至关重要。MQTT 作为一种轻量级的消息传输协议，因其高效、可靠的特性，在物联网场景中得到了广泛应用。华为的 IoTDA（IoT Device Access）平台为…...

编程日记 2025/5/15 4:44:04

Leetcode594.最长和谐子序列

目录题目算法标签: 滑动窗口, 哈希表思路滑动窗口代码哈希表代码题目 594. 最长和谐子序列算法标签: 滑动窗口, 哈希表思路先将数组进行排序, 检查两个相邻的但是不相等的数字的差值是否是 1 1 1, 如果是 1 1 1更新答案滑动窗口代码 #include <algorithm> #i…...

编程日记 2025/4/29 9:09:31

如何在idea中编写spark程序

在 IntelliJ IDEA 中编写 Spark 程序的详细指南在大数据处理领域，Apache Spark 凭借其强大的分布式计算能力，成为了众多开发者的首选工具。而 IntelliJ IDEA 作为一款功能强大的集成开发环境（IDE），为编写 Spark 程序…...

编程日记 2025/4/29 9:09:30

人工智能数学基础（一）：人工智能与数学

在人工智能领域，数学是不可或缺的基石。无论是算法的设计、模型的训练还是结果的评估，都离不开数学的支持。接下来，我将带大家深入了解人工智能数学基础，包括微积分、线性代数、概率论、数理统计和最优化理论，并通过 P…...

编程日记 2025/5/15 19:10:33

Android Studio 安装 Continue插件

1、Android 插件Studio中安装Continue 2、从本地盘符安装 3、安装后发现Continue为空 Android studio中 Help -> Find Action->Choose Boot Java 设置 4、配置DeepSeek 参考https://juejin.cn/post/7464122534546407461...

编程日记 2025/4/29 9:07:17

【C++】类和对象（4）

目录 1. 类型转换非explicit的单参数构造函数示例 explicit的单参数构造函数示例不同版本的行为示例 （单参数） 示例（多参数且其余参数有默认值 ） 示例（多参数且无默认值） 2. static成员变量…...

编程日记 2025/5/22 20:25:06

微信jdk 前端vue获取流程1、

参考链接： 企业微信的JSSDK,调用及使用方法_企业微信jssdk-CSDN博客 1、引用 <script src"//res.wx.qq.com/open/js/jweixin-1.2.0.js"></script> <script src"https://res.wx.qq.com/open/js/jweixin-1.2.0.js" referrerpolic…...

编程日记 2025/5/18 0:08:13

Linux进程7-signal信号处理方式验证、可重入函数举例、信号集函数验证、信号集阻塞验证

目录 1. signal函数 1.1进程接收到信号后的处理方式 1.2 signal 函数 1.2.1 signal 函数默认处理 1.2.2 signal 函数忽略处理 1.2.3 signal 函数自定义处理 1.2.4 signal 函数返回值 2.可重入函数 2.1如何判断函数是否可重入 2.2自定义信号处理函数举例 2.2.1 sle…...

编程日记 2025/5/13 2:00:27

使用Python在excel里创建柱状图

一、前言通过使用Python的openpyxl库，在excel里创建柱状图。openpyxl库提供了创建Excel图表的功能，包括柱状图(Bar Chart)。二、程序展示 1、导入相关模块，新建excel 新建excel后，在excel的第一列创建一些数据。 import op…...

编程日记 2025/5/8 13:49:39

计算机视觉进化论：YOLOv12、YOLOv11与Darknet系YOLOv7的微调实战对比

摘要 YOLO系列作为实时目标检测领域的重要里程碑，持续引领速度与精度的平衡发展。本文围绕YOLOv7（基于Darknet框架）、YOLOv11及YOLOv12，系统、深入地对比了三款模型的架构创新、微调策略、核心技术及应用场景。我们详细解析了三者…...

编程日记 2025/5/15 8:38:10

湖北理元理律师事务所：债务管理领域的平台化创新探索

随着中国居民负债率攀升至62%（央行2023年数据），债务管理从个体需求演变为社会性课题。湖北理元理律师事务所通过“法律科技金融”的融合模式，构建了国内首个全链条债务管理平台，其服务逻辑与行业价值值得深度剖析。平…...

编程日记 2025/5/10 21:23:07

沐曦玩转 LMDeploy、XTuner 和 InternLM3

学习链接： https://aicarrier.feishu.cn/wiki/O84LwkiBriUU0NkDwurcSufhnVb 一 LMDeploy推理及验证 1.1 下载LMDeploy # 安装addict软件包 pip install addict mmengine mmengine-lite fire accelerate0.32.1 nvidia-ml-py# 解决LMDeploy对tranformers版本要求的…...

编程日记 2025/5/13 2:57:52

【Java面试笔记：进阶】26.如何监控和诊断JVM堆内和堆外内存使用？

监控和诊断JVM内存使用是优化性能和解决内存问题的关键。 1.JVM内存监控与诊断方法 1.图形化工具 JConsole：提供图形化界面，可直接连接到Java进程，查看内存使用情况。VisualVM：功能强大的图形化工具，但注意从Oracle JDK 9开始不再包含在JDK安装包中。Java Mission Contr…...

编程日记 2025/4/29 9:05:02

阿里云服务器云盘扩容

在阿里云服务器上在线扩容了云盘后，如果服务器内部查看容量没有变化，可能是由于分区和文件系统未正确扩展。以下是详细的解决步骤： 1. 确认扩容是否成功在阿里云控制台检查磁盘容量是否已显示扩容后的新大小。如果控制台显示已扩容&#x…...

编程日记 2025/5/17 3:04:23

【ESP32】st7735s + LVGL移植

LVGL的移植使用版本1、创建工程2、开始移植2.1、文件准备2.2、修改代码2.3、SDK配置编辑器 3、测试使用版本 LVGL版本：8.3 链接点这里ESPIDF版本：4.4.8lvgl_esp32_drivers： 链接点这里ESP32型号：ESP32S3 1、创建工程默认都会…...

编程日记 2025/4/29 9:05:01

Jackson 使用方法详解

Jackson 是 Java 生态中最流行的 JSON 处理库，也是 Spring Boot 的默认 JSON 解析器。它提供了高性能的 JSON 序列化（对象 → JSON）和反序列化（JSON → 对象）功能。以下是 Jackson 的全面使用指南。 1. 基础依赖 Mave…...

编程日记 2025/4/29 9:03:56

TensorFlow深度学习框架：从入门到精通的完整指南

🌟 TensorFlow核心优势 TensorFlow作为Google开发的顶级深度学习框架，具有三大独特优势： 工业级部署能力：支持从移动端到服务器的全平台部署完善的工具链：包含TensorBoard、TF Lite、TF.js等完整生态强大的社区支持&…...

编程日记 2025/4/29 9:03:53

Java 入门宝典--注释、关键字、数据类型、变量常量、类型转换

作者：IvanCodes 发布时间：2025年4月28日🐣 专栏：Java教程哈喽，各位 CSDN 的小伙伴们！👋 这部分内容虽然基础，但极其重要，是后续学习所有高级特性的基石。准备好了吗&…...

编程日记 2025/4/29 9:02:50

【含文档+PPT+源码】基于微信小程序的旅游论坛系统的设计与实现

项目介绍本课程演示的是一款基于微信小程序的旅游论坛系统的设计与实现，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系统 …...

编程日记 2025/5/15 8:08:27

Android开发，实现一个简约又好看的登录页

文章目录 1. 编写布局文件2.设计要点说明3. 效果图4. 关于作者其它项目视频教程介绍 1. 编写布局文件编写activity.login.xml 布局文件 <?xml version"1.0" encoding"utf-8"?> <androidx.appcompat.widget.LinearLayoutCompat xmlns:android…...

编程日记 2025/4/29 9:02:47