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

力扣992做题笔记

news 来源：原创 2025/7/19 7:52:38

左神做法的理论依据

我们可以通过 集合的包含关系 和 具体示例枚举 来直观理解这一推导过程。以下结合题目示例 1 进行详细说明：

示例 1 分析

输入：nums = [1,2,1,2,3], k = 2
目标：计算恰好包含 2 种不同整数 的子数组个数。

步骤一集合 A 的计数

滑动窗口的核心逻辑是：

对于每个右边界 r，找到最小左边界 l，使得窗口 [l, r] 内不同整数个数 ≤k。
此时，左边界可以是 [l, r] 中的任意位置，因此贡献 r - l + 1 个子数组。

以示例 1 为例，滑动窗口计算 findNumsofMost(nums, 2)（即 |A|）的过程如下：

r	元素	窗口内元素	不同数	最小左边界 l	贡献子数组数
0	1	[1]	1	0	1
1	2	[1,2]	2	0	2
2	1	[1,2,1]	2	0	3
3	2	[1,2,1,2]	2	0	4
4	3	[2,1,2,3]	3（超过 2）	移动 l 到 1	窗口 [1,4] 含 2,1,3（3 种，仍超过）→ 继续移动 l 到 2 → 窗口 [2,4] 含 1,2,3（3 种，仍超过）→ 移动 l 到 3 → 窗口 [3,4] 含 2,3（2 种）→ 最小 l=3，贡献 (4-3+1=2)

累加结果：(1+2+3+4+2=12)，即 |A|=12。
而 findNumsofMost(nums, 1)（即 |B|）的计算结果为 5（仅含单个元素的子数组），因此：

步骤 2：定义集合 B（不超过 k-1 种）

集合 B 包含所有不同整数个数 ≤1 的子数组（即仅含 1 种整数）。
枚举所有满足条件的子数组：

单个元素：[1], [2], [1], [2], [3]，共 5 个。
连续相同元素的子数组：
- [1]（位置 0）、[2]（位置 1）、[1]（位置 2）、[2]（位置 3）、[3]（位置 4）。
- 无长度 ≥2 的连续相同元素（因为数组中相邻元素不同）。
集合 B 的总数：5 个。

步骤 3：计算集合差集 A - B

根据定义：
恰好含 k 种的子数组个数 = |A| - |B|

集合 A 包含 含 1 种或 2 种 的子数组。
集合 B 包含 仅含 1 种 的子数组。
因此，A - B 即为仅含 2 种的子数组，其数量为：
|A| - |B| = 12 - 5 = 7

这与题目示例 1 的输出一致。

数学推导：集合差集的严格性

设 (f(m)) 表示 不同整数个数 ≤m 的子数组个数。
恰好含 k 种的子数组必须满足：
- 不同整数个数 ≤k（属于集合 A），
- 且不同整数个数 >k-1（不属于集合 B）。
因此，恰好含 k 种的子数组是 A 中排除 B 的部分，即：

= f(k) - f(k-1)

例子 2：更简单的数组（nums = [1,1,2], k=2）

为了更直观，我们用一个更短的数组验证。

问题目标

找到所有「恰好有 2 种不同整数」的子数组。

数组分析

数组 [1,1,2] 的所有子数组及其不同整数个数：

子数组	内容	不同整数个数
[0,0]	[1]	1
[0,1]	[1,1]	1
[0,2]	[1,1,2]	2
[1,1]	[1]	1
[1,2]	[1,2]	2
[2,2]	[2]	1

集合 A（≤2）和 B（≤1）的大小

集合 A（≤2）：所有子数组都满足（因为最大不同个数是 2），共 6 个。
集合 B（≤1）：不同整数个数为 1 的子数组，即 [0,0], [0,1], [1,1], [2,2] → 共 4 个。

结论验证

恰好有 2 种不同整数的子数组是 [0,2], [1,2] → 共 2 个。
根据公式 |A| - |B| = 6 - 4 = 2，与实际结果一致。

数学推导：为什么差集是正确的？

用数学符号形式化定义：

设 f(k) 为「不同整数个数 ≤k 的子数组数目」。
设 g(k) 为「不同整数个数恰好等于k 的子数组数目」。

根据定义，f(k) 是所有 g(1), g(2), ..., g(k) 的和，即：
[ f(k) = g(1) + g(2) + … + g(k) ]

同理，f(k-1) 是：
[ f(k-1) = g(1) + g(2) + … + g(k-1) ]

两式相减得：
[ f(k) - f(k-1) = g(k) ]

这正是题目要求的「恰好有k种不同整数的子数组数目」。

总结

通过具体例子和数学推导可以看出：
「不超过k的子数组数」减去「不超过k-1的子数组数」，本质是通过「前缀和相减」的方式，精准提取出「恰好等于k」的子数组数目。这种方法将复杂的「恰好k」问题转化为更易计算的「不超过k」问题，是滑动窗口算法中常用的技巧。

代码

class Solution {public int subarraysWithKDistinct(int[] nums, int k) {return findNumsofMost(nums, k) - findNumsofMost(nums, k - 1); }private static final int maxn = 20001;private static int[] cnts = new int[maxn];private int findNumsofMost(int[] nums, int k) { Arrays.fill(cnts, 1, nums.length + 1, 0);int ans = 0;for (int r = 0, l = 0, collect = 0; r < nums.length; r ++) { if (++cnts[nums[r]] == 1) { collect ++;}while (collect > k) { if (--cnts[nums[l++]] == 0) { collect--;}}ans += r - l + 1;}return ans;}
}

力扣992做题笔记

左神做法的理论依据我们可以通过集合的包含关系和具体示例枚举来直观理解这一推导过程。以下结合题目示例 1 进行详细说明： 示例 1 分析输入：nums [1,2,1,2,3], k 2 目标：计算恰好包含 2 种不同整数的子数组个数。步骤一集合 A…...

编程日记 2025/7/19 7:52:38

特征值与特征向量的计算——PCA的数学基础

特征值与特征向量定义令 A {\bm A} A为 n n n \times n nn矩阵，如果存在非零向量 x {\bm x} x使得 A x λ x (1) {\bm A}{\bm x} \lambda {\bm x}\tag{1} Axλx(1) 成立，则称数 λ \lambda λ是矩阵 A {\bm A} A的特征值，称非零向量 x…...

编程日记 2025/7/19 7:46:32

vue2.0 的计算属性

个人简介 👨‍💻‍个人主页： 魔术师 📖学习方向： 主攻前端方向，正逐渐往全栈发展 🚴个人状态： 研发工程师，现效力于政务服务网事业 🇨🇳人生格言&…...

编程日记 2025/7/18 13:58:42

缘由程序设计 -- 数根（2）-编程语言-CSDN问答 void 数根() {//缘由https://ask.csdn.net/questions/7635593?spm1005.2025.3001.5141std::string n;int m 0, a 0;std::cin >> n;while (n[a] ! \0)m n[a] - 0;a 0;while (m)a m - m / 10 * 10…...

编程日记 2025/7/19 7:38:08

【Android】一键创建Keystore + Keystore 参数说明 + 查询SHA256（JDK Keytool Keystore）

一键创建 Android Keystore 的实用方法与参数详解在 Android 应用开发与发布中，**Keystore（签名文件）**扮演着至关重要的角色。本文将介绍如何通过 .bat 脚本一键创建 Keystore 文件，并详细讲解每一个参数的含义，帮助…...

编程日记 2025/7/1 10:37:38

laravel 通过Validator::make验证后，如何拿到验证后的值

在 Laravel 中，通过 Validator::make 创建的验证器实例验证数据后，可以通过以下方式获取验证后的值： 使用 validate() 方法调用验证器实例的 validate() 方法，会返回经过验证的数据数组。如果验证失败，该方法会抛出 V…...

编程日记 2025/7/1 10:37:35

centos把jar包配置成服务并设置开机自启

1.准备好jar包，启动路径，日志路径 2.编写启动脚步 vim /etc/systemd/system/test.service [Unit] Descriptionlapis Requiresnetwork.target remote-fs.target ##启动优先级，在下面的服务之后启动 Afterkafka.service zookeeper.service n…...

编程日记 2025/7/15 10:02:24

CentOS相关操作hub（更新中）

CentOS介绍： CentOS（Community Enterprise Operating System）是基于 Red Hat Enterprise Linux（RHEL）源代码编译的开源企业级操作系统，提供与 RHEL 二进制兼容的功能完全兼容 RHEL，可直接使用…...

编程日记 2025/7/18 13:19:04

数据库（一）：分布式数据库

定义分布式数据库（Distributed Database） 是指： 数据分布在多个物理位置，但对用户透明，表现为一个统一逻辑数据库的系统。结构模式（三层模式扩展） 层次作用对应实体用户层提供统一视图&…...

编程日记 2025/7/17 4:31:32

人工智能（AI）与BIM：建筑业创新实践的深度融合

一、BIM在建筑领域的发展现状与挑战作为建筑数字化的核心技术，BIM通过三维模型集成建筑全生命周期信息，已成为工程设计、施工及运维的标准工作流程。当前，BIM在碰撞检测、施工模拟、成本管控等场景的应用已较为成熟，但行业仍面临…...

编程日记 2025/7/17 6:26:20

FIR数字滤波器设计与实现

低通滤波器的设计与实现打开Matlab ,运行命令filterDesigner，选择FIR 最小二乘或者其它，设置采样频率，和低通滤波器截止频率。点击设计滤波器，如图1： 点击目标生成.C头文件，滤波器系数如下： …...

编程日记 2025/7/18 11:41:55

软件架构之-论高并发下的可用性技术

论高并发下的可用性技术摘要正文摘要 ;2023年2月，本人所在集团公司承接了长三角地区某省渔船图纸电子化审查系统项目开发，该项目旨在为长三角地区渔船建造设计院、以及渔船审图机构提供一个便捷化的服务平台。在此项目中，我作为项目组成员参与了项目建设工作，并担任系统架…...

编程日记 2025/7/1 10:37:17

阻塞队列：线程安全与生产者消费者模型解析

一、阻塞队列阻塞队列就是基于普通队列做出扩展 1.线程安全的如果针对一个已经满了的队列进行入队列，此时入队列操作就会阻塞，一直阻塞到队列不满（其他线程出队列元素）之后如果针对一个已经空了的队列进行出队列&#xff0c…...

编程日记 2025/7/16 11:45:02

【时时三省】(C语言基础)用函数实现模块化程序设计

山不在高，有仙则名。水不在深，有龙则灵。 ----CSDN 时时三省为什么要用函数？ 已经能够编写一些简单的C程序，但是如果程序的功能比较多，规模比较大，把所有的程序代码都写在一个主函数(main函数)中&#x…...

编程日记 2025/7/17 4:31:35

基于CATIA参数化圆锥建模的自动化插件开发实践——NX建模之圆锥体命令的参考与移植（一）

引言在CATIA二次开发领域，Python因其灵活性和丰富的库支持逐渐成为高效工具开发的首选语言。本文将以笔者开发的CATIA锥体自动化建模工具为例，参考NX软件中高效锥体创建命令，深度解析基于PySide6 GUI框架与pycatia接口库的集成…...

编程日记 2025/7/17 1:26:56

天才简史——Paolo Fiorini与他的速度障碍法

一、背景第一次“认识”Paolo Fiorini教授是看了DMP的体积避障论文《Dynamic Movement Primitives: Volumetric Obstacle Avoidance》，而且他的学生Michele Ginesi将相关代码开源了，后来查阅了Paolo Fiorini相关资料才发现他竟然是速度障碍法的作者&am…...

编程日记 2025/7/18 4:46:43

第五天的尝试

目录一、每日一言二、练习题三、效果展示四、下次题目五、总结一、每日一言毅力是永久的享受。没有人是一座孤岛，每个人都是这块大陆的一部分。二、练习题 import numpy as np import matplotlib.pyplot as plt array np.array([1,2,3,4,5]) plt.plot…...

编程日记 2025/7/5 19:41:38

大小端模式和消息的加密解密

大小端模式知识点一什么是大小端模式 // 大端模式 // 是指数据的高字节保存在内存的低地址中 // 而数据的低字节保存在内存的高地址中 // 这样的存储模式有点儿类似于把数据当作字符串顺序处理 // 地址由小向大增加，数据从高位往低位放 …...

编程日记 2025/7/18 8:03:09

(1) 查看端口状态

1. lsof 和 netstat 命令的区别 1.1 lsof 概念：只有在 root 的命令下才能执行，否则无内容显示；root 命令下显示完全 lsof -i: 8080 1.2 netstat 普通用户下显示不完全，root 命令下显示完全 netstat -tunlp | grep 8080 1.3…...

编程日记 2025/7/18 8:01:13

【C++]string模拟实现

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<assert.h> using namespace std; namespace liu {class string{public:using iterator char*;using const_iterator const char*;//string();//无参构造 string(const string&…...

编程日记 2025/7/18 20:15:43

Linux动静态库制作与原理

什么是库库是写好的现有的，成熟的，可以复用的代码。现实中每个程序都要依赖很多基础的底层库，不可能每个人的代码都从零开始，因此库的存在意义非同寻常。本质上来说库是一种可执行代码的二进制形式，可以被操作系统…...

编程日记 2025/7/1 11:59:46

ArkUI Tab组件开发深度解析与应用指南

ArkUI Tab组件开发深度解析与应用指南一、组件架构与核心能力 ArkUI的Tabs组件采用分层设计结构，由TabBar（导航栏）和TabContent（内容区）构成，支持底部、顶部、侧边三种导航布局模式。组件具备以下核心特…...

编程日记 2025/7/18 23:45:57

winrar 工具测试下载与安装

https://zhuanlan.zhihu.com/p/680852417 https://www.angusj.com/resourcehacker/#download 点击String Table，在展开列表中找到80:2052展开，删除1277行。点击右上方编译按钮，并保存。...

编程日记 2025/7/17 5:51:40

代码随想录算法训练营第四十四天

卡码网题目: 99. 岛屿数量100. 岛屿的最大面积其他: 今日总结往期打卡 99. 岛屿数量跳转: 99. 岛屿数量学习: 代码随想录公开讲解问题: 给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水…...

编程日记 2025/7/17 5:19:24

每日Prompt：自拍生成摇头娃娃

提示词将这张照片变成一个摇头娃娃：头部稍微放大，保持面部准确，身体卡通化。[把它放在书架上]。...

编程日记 2025/7/18 10:47:08

制作我的计算器

1. 界面布局新建项目 MyCalculator，开始布局。 2. 静态布局代码如下： // etc/pages/Index.ets Entry Component struct Index {build() {Column() {/*** 运算区*/Column() {TextInput({ text: 12x13 }).height(100%).fontSize(32).enabled(false).f…...

编程日记 2025/7/17 1:27:03

如何查看 Ubuntu开机是否需要密码

要查看 Ubuntu 开机是否需要密码，可以通过以下方法进行判断： 1. 检查自动登录设置图形界面操作： 进入系统设置（Settings）→ 用户账户（User Accounts）→ 解锁设置（输入当前用户密码…...

编程日记 2025/7/17 8:38:18

今日行情明日机会——20250519

上证指数缩量收十字星，个股涨多跌少，这周反弹的概率比较大。深证指数缩量调整，临近反弹，个股表现更好。 2025年5月19日涨停股主要行业方向分析并购重组（政策驱动资产整合） • 涨停家数：16…...

编程日记 2025/7/18 21:02:36

【CodeBuddy 】从0到1，让网页导航栏变为摸鱼神器

【CodeBuddy 】从0到1，让网页导航栏变为摸鱼神器我正在参加CodeBuddy「首席试玩官」内容创作大赛，本文所使用的 CodeBuddy 免费下载链接：腾讯云代码助手 CodeBuddy - AI 时代的智能编程伙伴 🌟嗨，我是LucianaiB&#…...

编程日记 2025/7/17 17:18:32

PCL点云库点云数据处理入门系列教材目录（2025年5月更新....）

PCL点云库点云数据处理入门系列教材目录基础阶段第 1 讲：PCL库简介和安装（Win10/11VS2019PCL 1.12.0）第 2 讲：PCL库中点云基本知识和数据类型结构第 3 讲：PCL库中点云数据格式PCD和PLY及其输入输出（IO&…...

编程日记 2025/7/17 8:01:11

同一颗太阳：Australia、Austria、Arab、Africa、Augustus、August、Aurora、Athena

我们来看一下下面这一堆单词： Australia n.澳大利亚；澳洲 Australian n.澳大利亚人 a.澳大利亚的 Austria n.奥地利 Austrian n.奥地利人 a.奥地利(人)的 Africa n.非洲 African n.非洲人* Arab a.阿拉伯的；阿拉伯人的 n.阿拉伯人(pl.Arabs)…...

编程日记 2025/7/17 7:13:45

用户账号及权限管理：企业安全的基石与艺术

在当今数字化时代，用户账号及权限管理已成为企业IT安全体系中不可或缺的核心组件。它不仅是保护敏感数据的第一道防线，更是确保业务运营效率和合规性的关键。本文将深入探讨用户账号及权限管理的重要性、最佳实践以及实施策略，助您构建一个安全、高效且灵活的访问控制体系。…...

编程日记 2025/7/18 17:51:18

存储系统03——数据缓冲evBuffer

存储系统03——数据缓冲evBuffer 数据缓冲evBuffer分段存储零拷贝线程安全 evbuffer 实例——存储系统事件触发数据缓冲evBuffer evbuffer 是 Libevent 提供的一个高效内存缓冲区管理工具，用于存储和操作数据。它类似于一个动态增长的字节缓冲区，支持多…...

编程日记 2025/7/1 11:59:21

留给王小川的时间不多了

王小川，这位头顶“天才少年”光环的清华学霸、搜狗输入法创始人、中国互联网初代技术偶像，正迎来人生中最难啃的硬骨头。他在2023年创立的百川智能，被称为“大模型六小虎”之一。今年4月，王小川在全员信中罕见地反思过去两年工作…...

编程日记 2025/7/1 11:59:19

Python海龟绘图-斗地主

#导入库 import random as r import turtle as t #数据 pk[红心A,红心2,红心3,红心4,红心5,红心6,红心7,红心8, 红心9,红心10,红心J,红心Q,红心K,黑桃A,黑桃2,黑桃3,黑桃4,黑桃5,黑桃6,黑桃7,黑桃8, 黑桃9,黑桃10,黑桃J, 黑桃Q,黑桃K,方块A,方块2,方块3,方块4,方块5,方块6,方块…...

编程日记 2025/7/17 10:09:50

一、内存调优

一、内存调优什么是内存泄漏监控Java内存的常用工具内存泄露的常见场景内存泄露的解决方案内存泄露与内存溢出的区别内存泄露：在Java中如果不再使用一个对象，但是该对象依然在GC ROOT的引用链上，这个对象就不会被垃圾回收器回收&…...

编程日记 2025/7/17 1:27:24

机器学习--特征工程具体案例

一、数据集介绍 sklearn库中的玩具数据集，葡萄酒数据集。在前两次发布的内容《机器学习基础中》有介绍。 1.1葡萄酒列标签名： wine.feature_names 结果： [alcohol, malic_acid, ash, alcalinity_of_ash, magnesium, total_phenols, flavanoi…...

编程日记 2025/7/17 12:33:40

Java-List集合类全面解析

Java-List集合类全面解析前言一、List接口概述与核心特性1.1 List在集合框架中的位置1.2 List的核心特性1.3 常见实现类对比二、ArrayList源码剖析与应用场景2.1 内部结构与初始化2.2 动态扩容机制2.3 性能特点与最佳实践三、LinkedList 源码剖析与应用场景3.1 内部结构与节…...

编程日记 2025/7/1 11:59:11

在Cursor中启用WebStorm/IntelliJ风格快捷键

在Cursor中启用WebStorm/IntelliJ风格快捷键方法一：使用预置快捷键方案打开快捷键设置 Windows/Linux: Ctrl K → Ctrl SmacOS: ⌘ K → ⌘ S 搜索预设方案在搜索框中输入keyboard shortcuts，选择Preferences: Open Keyboard Shortcuts (JSON) …...

编程日记 2025/7/17 5:36:20

32、跨平台咒语—— React Native初探

一、时空晶体架构（核心原理） 1. 量子组件桥接协议 // 原生组件映射 <View> → iOS UIView / Android ViewGroup <Text> → UILabel / TextView 魔法特性： • JavaScriptCore引擎：通过V8/Hermes引擎执行JS逻辑…...

编程日记 2025/7/1 11:59:07

无源探头衰减比与带宽特性的关联性研究

引言在电子测量领域，无源探头作为示波器的重要附件，其性能参数直接影响测量结果的准确性。本文将从电路设计原理出发，深入分析衰减比与带宽这两个关键参数的相互关系，帮助工程师正确理解并选择适合的测量探头。技术原理分析 …...

编程日记 2025/7/1 11:59:06

虚拟机的三个核心类加载器

虚拟机的三个核心类加载器在Java虚拟机（JVM）中，类加载器（ClassLoader）负责将类的字节码加载到内存中，并生成对应的Class对象。以下是三个核心类加载器的详细说明： 1. 启动类加载器（Bootstrap ClassLoader）职责：加载Java核心类库（如java.lang、java.util等），位…...

编程日记 2025/7/1 11:59:04

国家互联网信息办公室关于发布第十一批深度合成服务算法备案信息的公告

wenz 根据《互联网信息服务深度合成管理规定》，现公开发布第十一批境内深度合成服务算法备案信息，具体信息可通过互联网信息服务算法备案系统（https://beian.cac.gov.cn）进行查询。任何单位或个人如有疑议，请发送邮件…...

编程日记 2025/7/1 11:59:02

深入理解动态规划：从斐波那契数列到最优子结构

引言动态规划(Dynamic Programming, DP)是算法设计中一种非常重要的思想，广泛应用于解决各类优化问题。许多看似复杂的问题，通过动态规划的视角分析，往往能找到高效的解决方案。本文将系统介绍动态规划的核心概念，通过经典案例展…...

编程日记 2025/7/17 21:17:46

AT 指令详解：基于 MCU 的通信控制实战指南AT 指令详解

在 MCU（单片机）项目中，我们经常需要与各种通信模组（GSM、Wi-Fi、蓝牙等）交互。而这类模组通常都通过串口（UART）与 MCU 通信，控制它们的“语言”就是——AT 指令。一、什么是 AT 指…...

编程日记 2025/7/16 17:13:41

初学c语言16（内存函数）

1.memcpy 形式： 功能：完成内存块拷贝（所以可拷贝任何类型的数据） 过程：从source开始拷贝num个字节的数据到destination指向的空间里返回值：返回目标空间的起始地址应用： 模拟实现&#xf…...

编程日记 2025/7/1 11:58:57

【git进阶】git rebase（变基）

文章目录合并分支提交信息修改合并提交记录时间问题1时间问题2时间问题3git rebase有很多用武之地，我一一道来合并分支当多人协作同一个分支时，在提交我们自己版本之前，我们会先用git pull获取远端最新的版本。但是 git pull = git fetch + git mergegit merge是一个非…...

编程日记 2025/7/17 11:31:01