每日一题-力扣-2537. 统计好子数组的数目 0416
LeetCode 2537. 统计好子数组的数目
问题描述
给定一个整数数组nums
和一个整数k
,定义"好子数组"为包含至少k
对相等元素的子数组。任务是计算数组中所有"好子数组"的数量。
两个相等的元素构成一对,例如数组[1,1,1]中有3对(1,1),因为C(3,2)=3。
解题思路
小明立即识别出这是一个适合使用滑动窗口技术的问题。这种方法特别适合需要找到满足特定条件的连续子数组的情况。他的整体策略如下:
- 维护一个动态窗口,用左右指针(left和right)标记窗口边界
- 使用哈希表记录窗口内每个元素的出现频率
- 追踪窗口内相等元素对的数量
- 当窗口满足条件时(对数≥k),计算有效子数组数量并收缩左侧
代码实现与详细分析
小明实现了以下解决方案:
class Solution:def countGood(self, nums: List[int], k: int) -> int:n = len(nums)left = 0pairs = 0 # 当前窗口中的对数result = 0freq = {} # 当前窗口中每个元素的频率for right in range(n):# 添加新元素到窗口,并更新对数# 当添加一个元素时,它与之前所有相同元素形成新的对pairs += freq.get(nums[right], 0)freq[nums[right]] = freq.get(nums[right], 0) + 1# 从左侧收缩窗口,直到对数小于kwhile left <= right and pairs >= k:# 对于每个满足条件的窗口,加上以当前left开始、以right或之后位置结束的子数组数量result += n - right# 移除左侧元素,更新对数freq[nums[left]] -= 1pairs -= freq[nums[left]]left += 1return result
代码分析
小明的解决方案展示了滑动窗口算法的精髓:
- 初始化:设置左指针、对计数器、结果变量和频率哈希表
- 扩展窗口:右指针逐步向右移动,每次加入新元素并更新对数
- 计算对数:当添加一个新元素时,它与窗口中已有的相同元素形成新对,对数增加量等于该元素之前的出现次数
- 收缩窗口:当窗口包含的对数达到或超过k时,记录满足条件的子数组数量,然后从左侧收缩窗口
- 计算结果:对于每个满足条件的窗口,所有以当前left开始、以right或之后位置结束的子数组都是有效的,数量为(n-right)
关键洞察
小明注意到,当窗口满足条件时,不仅当前窗口是一个有效解,而且任何包含当前窗口的更大子数组也都是有效解。这就是为什么他在代码中使用result += n - right
,因为从right到数组末尾的所有位置都可以作为以left开始的有效子数组的结束位置。
复杂度分析
小明对算法的时间和空间复杂度进行了分析:
- 时间复杂度:O(n),其中n是数组长度。虽然有嵌套循环,但每个元素最多被添加和移除一次,所以总操作次数是线性的。
- 空间复杂度:O(n),用于存储频率哈希表,最坏情况下数组中的所有元素都不同。
总结与反思
通过这个问题,小明巩固了滑动窗口技术在子数组问题中的应用。他认识到,对于需要满足特定累积条件的连续区间问题,滑动窗口往往是一种高效的解决方案。
特别是,他学到了如何在窗口滑动过程中高效地维护和更新计数信息,这是解决此类问题的关键。这个技巧不仅适用于本题,也适用于许多其他涉及子数组统计的问题。
明天,小明计划继续探索更复杂的滑动窗口变体,以及其在其他类型算法问题中的应用。
相关文章:
每日一题-力扣-2537. 统计好子数组的数目 0416
LeetCode 2537. 统计好子数组的数目 问题描述 给定一个整数数组nums和一个整数k,定义"好子数组"为包含至少k对相等元素的子数组。任务是计算数组中所有"好子数组"的数量。 两个相等的元素构成一对,例如数组[1,1,1]中有3对(1,1)&am…...
遨游防爆手机:构筑煤矿安全通讯的数字护盾
在煤炭、石油、化工等危险作业场景中,安全生产始终是企业发展的生命线。面对复杂多变的生产环境,传统的通讯设备已难以满足现代工业对安全性、可靠性和智能化的严苛要求。遨游通讯作为国内领先的防爆通讯设备制造商,凭借其核心科技自主研发的…...
进程通信详解
进程间通信(IPC)详解:原理、方式与使用场景全解析 摘要 进程间通信(IPC)是操作系统中用于实现多个独立进程之间数据交换和资源协作的重要机制。本文系统地讲解了 IPC 的基本概念、设计目标和系统实现原理,…...
《What Are Step-Level Reward Models Rewarding?》全文翻译
《What Are Step-Level Reward Models Rewarding?Counterintuitive Findings from MCTS-Boosted Mathematical Reasoning》 Step-Level奖励模型到底奖励了什么?来自基于MCTS提升的数学推理的反直觉发现 摘要 Step-level奖励模型(SRMs)通过…...
windows使用docker-desktop安装milvus和可视化工具attu
这里写目录标题 docker-desktop安装docker安装milvusdocker安装milvus可视化工具attu注意点 docker-desktop安装 参考:Windows Docker 安装 docker安装milvus 参考:添加链接描述在 Docker 中运行 Milvus(Windows) docker安装m…...
如何通过原型链实现方法的“重写”(Override)?
在 JavaScript 中,通过原型链实现方法的 “重写”(Override) 的核心思路是:在子类(或子对象)的原型链上定义同名方法,覆盖父类(或父对象)的方法。以下是具体实现步骤和代…...
PyTorch - Tensor 学习笔记
上层链接:PyTorch 学习笔记-CSDN博客 Tensor 初始化Tensor import torch import numpy as np# 1、直接从数据创建张量。数据类型是自动推断的 data [[1, 2],[3, 4]] x_data torch.tensor(data)torch.tensor([[2, 1, 4, 3], [1, 2, 3, 4], [4, 3, 2, 1]])输出&am…...
《协议栈的骨架:从Web请求到比特流——详解四层架构的可靠传输与流量控制》
前言 本篇博客将详细介绍网络原理(细~~~) 💖 个人主页:熬夜写代码的小蔡 🖥 文章专栏 若有问题 评论区见 🎉欢迎大家点赞👍收藏⭐文章 一.应用层 这里的应用层只是个开头&a…...
软考 系统架构设计师系列知识点 —— 设计模式之创建者模式
本文内容参考: 软考 系统架构设计师系列知识点之设计模式(2)_系统架构设计师中考设计模式吗-CSDN博客 创建者模式_百度百科 建造者模式_百度百科 https://zhuanlan.zhihu.com/p/551870461 特此致谢! Builder Pattern…...
oracle判断同表同条件查出两条数据,根据长短判断差异
目标:同一个物料,账套不同,排查同料号有差异的规格名称 在Oracle数据库中,如果你想查询同一张表中两条数据某个字段的长度不同的情况,你可以使用JOIN语句或者窗口函数(如ROW_NUMBER()、RANK()、DENSE_RANK…...
咋用fliki的AI生成各类视频?AI生成视频教程
最近想制作视频,多方考查了决定用fliki,于是订阅了一年试试,这个AI生成的视频效果来看真是不错,感兴趣的自己官网注册个账号体验一下就知道了。 fliki官网 Fliki生成视频教程 创建账户并登录 首先,访问fliki官网并注…...
【STM32-代码】
STM32-代码 ■ printf() 输出到uart1■■■ ■ printf() 输出到uart1 static UART_HandleTypeDef * g_HDebugUART &huart1;int fputc(int c, FILE *f) {(void)f;HAL_UART_Transmit(g_HDebugUART, (const uint8_t *)&c, 1, DEBUG_UART_TIMEOUT);return c; }int fgetc…...
用cursor三个小时复刻高德地图的足迹地图
用cursor三个小时复刻了高德地图的足迹地图,当然,是“低配”版的。 1、首先要初始化,提出一个需求,让它自由发挥 运行之后发现它报错了,原因出在这行代码,“https://cdn.jsdelivr.net/npm/echarts5,4.3/…...
Git分支管理与工作流实践
Git分支管理与工作流实践 一、Git分支规范与核心原则 主分支(master/main) 核心作用:存储生产环境代码,永远保持稳定且可直接发布。禁止直接在此分支开发。操作规范:仅通过合并release或hotfix分支更新,合…...
python面试总结
目录 Python基础 1、python及其特点 2、动态类型和静态类型? 3、变量命名规则是什么? 4、基本数据类型有哪些? 5、Python 中字典? 6、集合set是什么?有什么特点? 7、python的字符串格式化 函数 1…...
基于骨骼识别的危险动作报警系统设计与实现
基于骨骼识别的危险动作报警系统设计与实现 基于骨骼识别的危险动作报警分析系统 【包含内容】 【一】项目提供完整源代码及详细注释 【二】系统设计思路与实现说明 【三】基于骨骼识别算法的实时危险行为预警方案 【技术栈】 ①:系统环境:Windows 10…...
HarmonyOS 5.0应用开发——五子棋游戏(鸿蒙版)开发
【高心星出品】 文章目录 五子棋游戏(鸿蒙版)开发运行效果开发步骤项目结构核心代码棋盘组件:游戏逻辑处理:主页面: 五子棋游戏(鸿蒙版)开发 五子棋是一款传统的两人策略型棋类游戏࿰…...
避坑,app 播放器media:MediaElement paly报错
System.Runtime.InteropServices.COMException HResult=0x8001010E Message= Source=WinRT.Runtime StackTrace: 在 WinRT.ExceptionHelpers.<ThrowExceptionForHR>g__Throw|38_0(Int32 hr) 在 ABI.Microsoft.UI.Xaml.Controls.IMediaPlayerElementMethods.get_MediaPlay…...
STM32单片机入门学习——第38节: [11-3] 软件SPI读写W25Q64
写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难,但我还是想去做! 本文写于:2025.04.16 STM32开发板学习——第一节: [1-1]课程简介 前言开发板说明引用解答和…...
使用阿里云创建公司官网(使用wordpress)
安装 LNMP 不通的lnmp版本 https://lnmp.org/download.html wget http://soft.vpser.net/lnmp/lnmp2.1.tar.gz -cO lnmp2.1.tar.gztar zxf lnmp2.1.tar.gz && cd lnmp2.1 && ./install.sh lnmp数据库选5.7 选好数据库,会让你设置数据库 root 用户…...
Python程序结构深度解析:顺序结构与对象布尔值的底层逻辑与应用
一、程序结构的三大基石 在计算机科学领域,任何复杂的算法都可以分解为顺序结构、选择结构和循环结构这三种基本结构的组合。这种结构化编程思想由计算机科学家Bhm和Jacopini在1966年首次提出,至今仍是现代编程语言设计的核心原则。 1.1 顺序结构的本质…...
【系统搭建】Ubuntu系统两节点间SSH免密配置
SSH免密配置是MPI分布式、DPDK通信等集群节点间通信的基础配置 1. 安装SSH服务端(所有节点执行) Ubuntu 默认只安装 SSH 客户端(openssh-client),未安装服务端(openssh-server),需要手动安装并…...
美信监控易:揭秘高效数据采集和数据分析双引擎
在当今复杂多变的运维环境中,一款强大的运维管理软件对于保障企业的IT系统稳定运行至关重要。北京美信时代的美信监控易运维管理软件,凭借其卓越的数据分析双引擎,成为了众多运维团队的首选。 首先,美信监控易的数据采集引擎展现出…...
基于STM32+FPGA的地震数据采集器软件设计,支持RK3568+FPGA平台
0 引言 地震观测是地球物理观测的重点,是地震学和 地球物理学发展的基础 [1] 。地震数据采集器主要功 能是将地震计采集的地震波模拟信号转换为数字信 号并进行记录或传输 [2] ,为地震学提供大量的基础 数据。本文将介绍基FPGAARM的地震数据采集器软…...
NO.95十六届蓝桥杯备战|图论基础-单源最短路|负环|BF判断负环|SPFA判断负环|邮递员送信|采购特价产品|拉近距离|最短路计数(C++)
P3385 【模板】负环 - 洛谷 如果图中存在负环,那么有可能不存在最短路。 BF算法判断负环 执⾏n轮松弛操作,如果第n轮还存在松弛操作,那么就有负环。 #include <bits/stdc.h> using namespace std;const int N 2e3 10, M 3e3 1…...
Linux 网络管理深度指南:从基础到高阶的网卡、端口与路由实战
一、网卡管理:构建网络连接的基石 1.1 现代网络工具链解析 在当代Linux系统中,iproute2套件已全面取代传统的net-tools,其优势体现在: 推荐组合命令: ip -c addr show | grep "inet " # 彩色显示有效IP…...
《重构全球贸易体系用户指南》解读
文章目录 背景核心矛盾与理论框架美元的“特里芬难题”核心矛盾目标理论框架 政策工具箱的协同运作机制关税体系的精准打击汇率政策的混合干预安全工具的复合运用 实施路径与全球秩序重构阶段性目标 风险传导与反制效应内部失衡加剧外部反制升级系统性风险 范式突破与理论再思考…...
stateflow中的函数
最近开始使用STATEFLOW,感觉功能比较强大,在嵌入式的应用中应该缺少不了,先将用到的仔细总结一下。还有一点,积极拥抱ai,学会使用AI的强大功能来学习。 在 Stateflow 中,不同类型的函数和状态适用于不同的建模需求。以下是 图形函数(Graphical Function)、Simulink 函…...
41.[前端开发-JavaScript高级]Day06-原型关系图-ES6类的使用-ES6转ES5
JavaScript ES6实现继承 1 原型继承关系图 原型继承关系 创建对象的内存表现 2 class方式定义类 认识class定义类 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible&qu…...
Flutter学习四:Flutter开发基础(一)Widget
Widget 简介 0 引言 本文是对 Flutter Widget 相关知识的学习和总结。 1 Widget 概念 1.1 Widget 基础 Widget 字面意思:控件、组件、部件、微件、插件、小工具widget 的功能是"描述一个UI元素的配置信息",所谓的配置信息就是 Widget 接收…...
Dify智能体平台源码二次开发笔记(6) - 优化知识库pdf文档的识别
目录 前言 新增PdfNewExtractor类 替换ExtractProcessor类 最终结果 前言 dify的1.1.3版本知识库pdf解析实现使用pypdfium2提取文本,主要存在以下问题: 1. 文本提取能力有限,对表格和图片支持不足 2. 缺乏专门的中文处理优化 3. 没有文档结…...
【LaTeX】公式图表进阶操作
公式 解决不认识的符号 查资料:1)知道符号样子;2)知道符号含义 放大版括号 用来括住存在分式的式子,或者用来括住内部由有很多括号的式子。用法是在左右括号[]分别加上\left和\right \[ J_r\dfrac{i \hbar}{2m} \l…...
第二阶段:数据结构与函数
模块4:常用数据结构 (Organizing Lots of Data) 在前面的模块中,我们学习了如何使用变量来存储单个数据,比如一个数字、一个名字或一个布尔值。但很多时候,我们需要处理一组相关的数据,比如班级里所有学生的名字、一本…...
matlab中simulink的快捷使用方法
连接系统模块还有如下更有效的方式:单击起始模块。 按下 Ctrl键,并单击目标块。 图示为已经连接好的系统模块 旋转模块:选中模块后按图示点击即可...
Redux部分
在src文件夹下 的store文件夹下创建modules/user.js和index.js module/ user.js // 存储用户相关const { createSlice } require("reduxjs/toolkit");const userStore createSlice({name:"user",// 数据状态initialState:{token:},// 同步修改方法red…...
基于STM32F103C8T6的温湿度检测装置
一、系统方案设计 1、系统功能分析 本项目设计的是一款基于STM32F103C8T6的温室大棚检测系统低配版。由 STM32F103C8T6最小系统板,OLED显示屏,DHT11温湿度检测传感器,光敏电阻传感器组成, 可以实现如下功能: 使用D…...
设计模式 - 单例模式
一个类不管创建多少次对象,永远只能得到该类型一个对象的实力 常用到的,比如日志模块,数据库模块 饿汉式单例模式:还没有获取实例对象,实例对象就已经产生了 懒汉式单例模式:唯一的实例对象,…...
Linux驱动开发1 - Platform设备
背景 所有驱动开发都是基于全志T507(Android 10)进行开发,用于记录驱动开发过程。 简介 什么是platform驱动自己上网搜索了解。 在driver/linux/platform_device.h中定义了platform_driver结构体。 struct platform_driver {int (*probe…...
力扣-hot100(盛最多水的容器)
11. 盛最多水的容器 中等 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明…...
使用 PyTorch 构建 UNet 图像去噪模型:从数据加载到模型训练的完整流程
图像去噪是计算机视觉中的一个基础问题,在医学图像、遥感、夜间视觉等领域有广泛应用。本文将手把手带你用 PyTorch 构建一个 UNet 架构的图像去噪模型,包括数据预处理、网络搭建、PSNR 评估与模型保存的完整流程。 本项目已支持将数据增强版本保存为独立…...
从信号处理角度理解图像处理的滤波函数
目录 1、预备知识 1.1 什么是LTI系统? 1.1.1 首先来看什么是线性系统,前提我们要了解什么是齐次性和叠加性。...
集合框架--List集合详解
List集合 List 接口直接继承 Collection 接口,它定义为可以存储重复元素的集合,并且元素按照插入顺序有序排列,且可以通过索引访问指定位置的元素。常见的实现有:ArrayList、LinkedList。 Arraylist:有序、可重复、有索引 Linke…...
需求分析---软件架构师武器库中的天眼系统
在软件架构中,需求分析决定了系统的核心设计方向。 然而,现实中的需求往往存在以下问题: 需求被二次加工:产品经理或业务方可能直接提供“解决方案”(如“我们需要一个聊天功能”),而非原始需…...
Spring Cloud Gateway 的执行链路详解
Spring Cloud Gateway 的执行链路详解 🎯 核心目标 明确 Spring Cloud Gateway 的请求处理全过程(从接收到请求 → 到转发 → 到返回响应),方便你在合适的生命周期节点插入你的逻辑。 🧱 核心执行链路图(执…...
Python----机器学习(基于PyTorch框架的逻辑回归)
逻辑回归是一种广泛使用的统计学习方法,主要用于处理二分类问题。它基于线性回归模型,通过Sigmoid函数将输出映射到[0, 1]范围内,表示实例属于正类别的概率。尽管逻辑回归适用于二分类任务,但在多分类问题中常使用Softmax函数&…...
工业数据治理范式革新:时序数据库 TDengine虚拟表技术解析
小T导读:在工业数字化过程中,数据如何从设备采集顺利“爬坡”到上层应用,一直是个难题。传统“单列模型”虽贴合设备协议,却让上层分析举步维艰。TDengine 用一种更聪明的方法打通了这条数据通路:不强求建模、不手动转…...
Linux的应用领域,Linux的介绍,VirtualBox和Ubuntu的安装,VMware的安装和打开虚拟机CentOS
目录 Linux的应用领域 Linux的介绍 Linux的介绍 Linux发行版 Unix和Linux的渊源 虚拟机和Linux的安装 VirtualBox和Ubuntu的安装 安装VirtualBox 安装Ubuntu 下载Ubuntu操作系统的镜像文件 创建虚拟机 虚拟机设置 启动虚拟机,安装Ubuntu系统 Ubuntu基…...
使用 Java 8 Stream实现List重复数据判断
import java.util.*; import java.util.stream.Collectors;public class DeduplicateStreamExample {static class ArchiveItem {// 字段定义与Getter/Setter省略(需根据实际补充)private String mATNR;private String lIFNR;private String suppSpecMod…...
GDAL:地理数据的万能瑞士军刀
目录 1. 什么是GDAL?2. 为什么需要GDAL?3. GDAL的主要功能3.1. 数据转换3.2. 数据裁剪和处理3.3. 读取和写入多种格式 4. 实际应用场景4.1 环境监测4.2 城市规划4.3 导航系统 5. 技术原理简单解释6. 如何使用GDAL?6.1 简单命令示例 7. 学习建…...
每日文献(十三)——Part two
今天从第三章节:“实现细节”开始介绍。 目录 三、实现细节 四、实验 五、总结贡献 六、致谢 三、实现细节 我们在多尺度图像上训练和测试区域建议和目标检测网络。这是在KITTI目标检测基准[13]上基于CNN的目标检测的趋势。例如,在[16]中ÿ…...