labuladong

滑动窗口

type: concept tags: [算法技巧, 双指针, 子数组, 子串] created: 2026-05-05 updated: 2026-05-05滑动窗口（Sliding Window）通过左右指针维护一个窗口区间，在 O(N) 时间内解决子数组/子串问题的算法技巧。定义滑动窗口是一种基于快慢双指针的算法技巧，通过维护一个 [left, right) 左闭右开的窗口区间，不断滑动窗口来寻找满足特定条件的最优子数组或子串。它将暴力解法的 O(N²) 时间复杂度优化为 O(N)。核心特性| 特性 | 说明 | |------|------| | 本质 | 快慢双指针，一快一慢前后相随，中间部分即窗口 | | 时间复杂度 | O(N)，每个元素进出窗口各一次 | | 空间复杂度 | O(k)，k 为窗口内不同元素的数量 | | 适用问题 | 寻找满足某条件的最长/最短子数组（子串） | | 区间定义 |

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

BFS框架

type: summary tags:BFS算法框架LeetCode最短路径 created: 2026-05-06 updated: 2026-05-06BFS 算法框架[[raw/articles/2026/05/BFS框架]]一句话总结BFS 算法的本质是二叉树的层序遍历扩展到图结构，通过队列实现按层级扩散搜索，适合求解最短路径问题。核心要点1. BFS 与树/图遍历的关系DFS/回溯 的本质是二叉树的递归遍历（前中后序）BFS 的本质是二叉树的层序遍历扩展到图结构从基础数据结构到高级算法的推导路径：二叉树遍历 → 多叉树遍历 → 图遍历（加 visited 数组）→ BFS 算法BFS 适合最短路径问题，因为它按层扩散，第一次到达目标时步数最少2. BFS 通用框架（三种写法）第一种写法（简单但局限大）：// 从 start 开始 BFS，寻找 target void bfs(Node start, Node target) { Queue<Node> q = new LinkedList<>();

N叉树遍历基础

type: summary tags: [N叉树, 树遍历, DFS, BFS, 森林, 数据结构] created: 2026-05-03 updated: 2026-05-03N叉树遍历基础[[raw/articles/2026/05/N叉树遍历基础]]⚠️ 内容不完整 - 原文抓取被截断，缺少递归遍历（DFS）和层序遍历（BFS）的具体代码实现部分相关题目| LeetCode | 力扣 | 遍历类型 | | --- | --- | --- | | 589. N-ary Tree Preorder Traversal | 589. N 叉树的前序遍历 | 前序遍历（DFS） | | 590. N-ary Tree

二叉堆基础

type: summary tags: [数据结构, 二叉堆, 优先级队列, 堆排序, 完全二叉树] created: 2026-05-04 updated: 2026-05-04二叉堆核心原理及可视化[[raw/articles/2026/05/二叉堆基础]]一句话总结二叉堆是一种能够动态排序的数据结构，核心操作是 sink（下沉）和 swim（上浮），用于维护堆性质。主要应用有两个：优先级队列（Priority Queue）和堆排序（Heap Sort）。核心内容一、二叉堆概览定义：二叉堆是一种特殊的完全二叉树，存储在数组中（而非链表）。数组索引与树节点关系（索引 0 空着不用）：int parent(int root) { return root / 2; } int left(int root) { return root * 2; } int right(int root) { return root * 2 + 1;

二叉堆详解实现优先级队列

type: summary tags:数据结构二叉堆优先级队列算法 created: 2026-05-08 updated: 2026-05-08二叉堆详解实现优先级队列[[raw/articles/2026/05/二叉堆详解实现优先级队列.md]]一句话总结通过 swim（上浮）和 sink（下沉）两个核心操作维护堆性质，实现高效的优先级队列数据结构。核心要点1. 二叉堆的本质二叉堆是一种特殊的完全二叉树，存储在数组中而非链式结构。通过数组索引计算父子关系：父节点：parent = root / 2左子节点：left = root * 2右子节点：right = root * 2 + 12. 堆性质最大堆：每个节点都大于等于它的两个子节点，堆顶是最大元素最小堆：每个节点都小于等于它的两个子节点，堆顶是最小元素3. 两大核心操作swim（上浮）：当节点比父节点大时，交换位置向上浮动sink（下沉）：当节点比子节点小时，与较大的子节点交换向下沉4. 优先级队列实现基于二叉堆实现，核心 API：insert(Key e)：插入到堆底，然后 swim 上浮到正确位置delMax()：堆顶与堆底交换，删除原堆顶，然后 sink 下沉恢复堆性质基本原理二叉堆通过数组存储完全二叉树，利用索引关系而非指针维护树结构。插入和删除时通过局部调整（上浮/下沉）维护堆性质，避免全局重建。上浮代码（swim）：private void swim(int k) { while (k >

位图-总结

type: summary tags: [位图, 数据结构, 空间优化, bitmap] created: 2026-05-02 updated: 2026-05-02位图（BitMap）基础[[raw/articles/2026/05/位图]]一句话总结位图（BitMap）是一种极致节省空间的数据结构，用 1 个比特位（bit）的 0/1 来标记元素是否存在，相比布尔数组节省 7/8 的内存空间，适用于超大规模数据场景。核心原理问题背景在算法题中，常用 boolean[] visited 布尔数组记录元素访问状态：boolean[] visited = new boolean[nums.length]; visited[10] = true;空间浪费问题：布尔类型只需 1 bit（0/1）即可表示但大部分编程语言中，一个 boolean 占用 1 字节（8 bits） 内存布尔数组实际浪费了 7/8 的存储空间位图设计位图直接用 1 个 bit 表示一种状态：0 表示元素不存在 / 未访问1

冒泡排序-总结

type: summary tags:排序算法算法基础稳定排序 created: 2026-05-05 updated: 2026-05-05冒泡排序 (Bubble Sort)[[raw/articles/2026/05/冒泡排序]]一句话总结冒泡排序是对选择排序的优化，通过交换相邻逆序对完成排序，是一种稳定排序算法，支持在数组有序时提前终止。核心要点1. 从选择排序的缺陷出发选择排序存在三个主要问题：不稳定排序：交换操作会改变相同元素的相对位置无视数组有序度：即使输入已有序，时间复杂度仍是 O(n²)时间复杂度无法优化：固定执行约 n²/2 次操作冒泡排序通过逐步优化选择排序来解决这些问题。2. 三个优化阶段阶段一：获得稳定性将选择排序的"交换"改为"数据搬移"把 nums[sortedIndex..minIndex] 整体后移一位，让最小值插入正确位置代价：增加了一个 for 循环，实际执行次数增加阶段二：合并操作（真正的冒泡排序）倒序遍历，发现逆序对就交换相邻元素最小值会像气泡一样逐步"冒"到正确位置消除了额外的数据搬移循环，执行次数回到约 n²/2 次关键：只交换相邻元素，不改变相同元素的相对位置 → 稳定排序阶段三：提前终止添加 swapped 布尔变量记录是否发生交换如果一轮遍历没有交换，说明数组已有序，提前退出对近乎有序的数组效率显著提升基本原理冒泡排序的核心思想是通过交换相邻逆序对，让最小值逐步移动到正确位置。初始: [5, 3, 1, 4, 2] 第1轮 (sortedIndex=0): i=4: [5,3,1,4,2] → [5,3,1,2,4] (交换4,2) i=3: [5,3,1,2,4] → [5,3,1,2,4]

分治算法解题套路框架

type: summary tags: [分治算法, 算法设计, 递归] created: 2026-05-06 updated: 2026-05-06分治算法解题套路框架[[raw/articles/2026/05/分治算法解题套路框架]]一句话总结区分广义分治思想与狭义分治算法的核心差异，讲解分治算法通过问题分解降低时间复杂度的原理及递归解题框架。核心要点1. 分治思想 vs 分治算法分治思想：宽泛的分解问题思路，将问题拆解为子问题求解后合并，广泛应用于递归算法（如斐波那契递归、二叉树节点计数、动态规划等）分治算法：特指分解后求解比直接求解复杂度更低的递归算法，需满足分解带来的效率提升（如桶排序、归并排序）2. 复杂度降低原理数学类比：$(a+b)^2 = a^2 + 2ab + b^2 \geq a^2 + b^2$原问题规模 $N=a+b$，直接求解 $O(N^2)$ 复杂度为 $O((a+b)^2)$分解为子问题后分别求解，复杂度为 $O(a^2 + b^2) < O((a+b)^2)$适用条件：仅多项式级别复杂度的算法可能通过分治提升效率3. 解题框架分治算法本质是分解问题的递归思路，类似二叉树后序遍历：分解原问题为结构相同的子问题递归求解子问题合并子问题的解得到原问题解基本原理| 概念 | 说明 | |------|------| | 分治思想 | 所有递归算法的两种思路之一（另一种是遍历思路），用于分解问题 | | 分治算法

前缀树(Trie)基础

type: summary tags: [前缀树, Trie, 字典树, 字符串, 数据结构, labuladong] created: 2026-05-04 updated: 2026-05-04[[raw/articles/2026/05/前缀树(Trie)基础]]前缀树（Trie）基础⚠️ 内容不完整：原始文件仅包含核心原理与前缀操作部分，后续内容（如通配符匹配等）缺失。核心原理（多叉树本质、空间优势、前缀操作复杂度）Trie 树（又称字典树、前缀树）是 多叉树结构的延伸，专门针对字符串做优化：每个节点代表一个字符串字符，从根节点到某一节点的路径表示一个完整字符串空间优势：不重复存储公共前缀，例如存储 "apple"、"app"、"appl" 仅需 5 个字符（HashMap 需存储 12 个字符，重复存储3次 "app"、2次 "l"）前缀操作复杂度：所有前缀相关操作（如 shortestPrefixOf、longestPrefixOf、hasKeyWithPrefix）的时间复杂度为 O(L)，L 为前缀长度，远优于 HashMap/TreeMap 的 O(N*L)（需遍历所有键逐一比对）与多叉树的关系：Trie 是特殊的多叉树，子节点对应下一个可能的字符，子节点数量取决于字符集大小（如小写字母为26个）与现有数据结构对比（核心原理+定位对比）本站已实现的数据结构定位对比：| 数据结构 | 底层实现 | 键类型 | 核心操作复杂度 | 特点 | |---------|---------|--------|--------------|------| | HashMap/HashSet

哈夫曼树

type: summary tags: [数据压缩, 哈夫曼树, 哈夫曼编码, 前缀编码, 变长编码] created: 2026-05-04 updated: 2026-05-04哈夫曼树[[raw/articles/2026/05/哈夫曼树]]一句话总结霍夫曼树是二叉树结构的经典应用，它是一种最优前缀编码树，常用于数据压缩。核心内容数据压缩基础无损压缩 vs 有损压缩| 类型 | 特点 | 示例 | |------|------|------| | 无损压缩 | 压缩后数据可完全还原，不丢失任何信息 | zip 压缩包 | | 有损压缩 | 压缩后数据会丢失一些信息，但压缩率更高 | 图片压缩（降低色度精度） |无损压缩的本质：编码和解码过程。压缩效果取决于算法能否充分挖掘原始数据中的冗余信息。权衡三角：通用性 ↔ 压缩率 ↔ 性能定长编码 vs 变长编码| 编码方式 | 特点 |

哈希表与链表组合原理

type: summary tags: [哈希表, 链表, LinkedHashMap, 哈希链表, Golang, Java] created: 2026-05-03 updated: 2026-05-03哈希表与链表组合原理[[raw/articles/2026/05/哈希表与链表组合原理]]核心要点1. Golang map 的随机遍历顺序Golang 的 map 每次遍历顺序都不同，这是故意设计的，目的是防止开发者依赖哈希表的遍历顺序。实现原理：不触发扩缩容时，底层 table 数组的存储顺序是固定的遍历时不是从数组头部开始，而是从一个随机位置开始利用环形数组技巧遍历整个 table 数组这样既保证随机性，又不牺牲太多性能示例遍历顺序变化：| 1 2 3 4 5 5 | 1 2 3 4 2 3 4 5 | 1 | 1 2 3 4 52.

哈希表基础

type: summary tags: [哈希表, HashMap, 数据结构, Java, 哈希函数, 负载因子, 哈希冲突, 拉链法, 线性探查法] created: 2026-05-03 updated: 2026-05-03哈希表基础[[raw/articles/2026/05/哈希表基础]]核心要点1. 哈希表 vs MapMap 是接口，仅声明操作方法（get/put/remove），未指定实现方式HashMap 是 Map 的一种实现，底层使用哈希表，增删查改复杂度 O(1)其他实现如 TreeMap（红黑树，O(logN)）、LinkedHashMap（保持插入顺序）不能假设所有键值对操作都是 O(1)，需看具体实现的数据结构2. 哈希表基本原理哈希表 = 加强版数组核心机制：通过哈希函数将 key 映射到数组索引，实现 O(1) 访问伪码逻辑：put(key, value): table[hash(key)] = value get(key): return table[hash(key)] remove(key): table[hash(key)] = null3. 哈希函数设计作用：将任意类型

哈希表链地址法

type: summary tags: [哈希表, 拉链法, 链地址法, 数据结构, Java, 哈希冲突, 开放寻址法] created: 2026-05-03 updated: 2026-05-03哈希表链地址法（拉链法）实现[[raw/articles/2026/05/哈希表链地址法]]⚠️ 注意：原文使用 JavaScript 动态加载内容，未能获取完整正文（仅获取到29行简介）。以下为基于现有内容的摘要，待补充完整内容。核心要点前置知识本文建立于以下基础知识之上：[[哈希表基础]][[链表]]哈希冲突解决方法回顾文章回顾了两种主流哈希冲突解决方法：| 方法 | 别名 | 原理 | |------|------|------| | 拉链法 | 链地址法 | 数组每个位置存储链表，冲突元素追加到链表 | | 开放寻址法 | 线性探查法 | 冲突时往后找空位（index+1, +2, ...） |![[images/hash-collision.jpeg]]拉链法简化版实现假设为了便于理解，文章采用以下简化：类型限制：仅支持 key 类型为 int，value 类型为 int，key 不存在时返回

图最短路径算法

type: summary tags: [图算法, 最短路径, Dijkstra, Bellman-Ford, Floyd, 启发式搜索] created: 2026-05-04 updated: 2026-05-04图最短路径算法[[raw/articles/2026/05/图最短路径算法]]一句话总结Dijkstra 算法 和 A* 算法 是 [[BFS]] 的拓展，处理不包含负权重的单源最短路径问题SPFA 算法（基于队列的 Bellman-Ford 算法）是 [[BFS]] 的拓展，可处理包含负权重的单源最短路径问题Floyd 算法 是 [[动态规划]] 的应用，处理多源最短路径问题最短路径问题分类单源最短路径从某个起点出发，到其他所有顶点的最短路径。输出：一维数组 distTo，distTo[i] 表示从起点到节点 i 的最短路径长度代表算法：Dijkstra 算法：BFS + 贪心思想，效率高，不能处理负权重Bellman-Ford 算法（SPFA）：BFS 拓展，可处理负权重，效率较低点对点最短路径从起点 src 到目标节点 dst 的最短路径。可视为单源最短路径的特例A* 算法：启发式搜索，利用终点信息有方向性地搜索关键：启发函数（Heuristic

图论术语

type: summary tags: [图论, 数据结构, 算法基础, 术语] created: 2026-05-04 updated: 2026-05-04图论术语[[raw/articles/2026/05/图论术语]]一句话简介图论基础术语详解：图的结构组成、度的概念、边节点数量关系、子图类型及连通性等核心概念。关键要点1. 图的基本结构节点 (Vertex)：图的基本组成单元，每个节点有唯一 ID边 (Edge)：连接节点的线，可以是有向或无向有向图 (Directed Graph)：边有方向，只能沿箭头方向到达无向图 (Undirected Graph)：边无方向，可双向到达（可理解为双向图）加权图 (Weighted Graph)：边带权重，可用于表示距离、成本等无权图 (Unweighted Graph)：边无权重2. 度的概念度 (Degree)：无向图中与节点相连的边的条数入度 (Indegree)：有向图中指向该节点的边数出度 (Outdegree)：有向图中从该节点指向其他节点的边数3. 边和节点的数量关系简单图 (Simple Graph)：无自环边和多重边的图边数的取值范围：$0 \leq E \leq V(V-1)/2 \approx V^2$稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边稀疏图 (Sparse Graph)：$E$ 远小于

基数排序-总结

type: summary tags: [算法, 排序, 基数排序, 稳定排序] created: 2026-05-05 updated: 2026-05-05基数排序[[raw/articles/2026/05/基数排序.md]]一句话总结基数排序是 [[计数排序]] 的扩展，对整数的每一位依次进行稳定排序，最终完成整体排序。核心要点1. 基数排序的本质基数（Radix）即进制，适用于整数或可转换整数的数据是计数排序的扩展，用于解决计数排序空间复杂度过高的问题与桶排序关系不大2. 稳定排序的必要性对每一位排序时必须使用稳定排序原因：相同高位或低位的值需要保持原有相对顺序示例：56 和 57，十位数相同（都是5），稳定排序保证个位数顺序不变3. 排序顺序从低位（个位）到高位依次排序由于使用稳定排序，低位排序的结果不会被高位排序破坏基本原理示例：对 nums = [329, 457, 839, 439, 720, 355, 350] 进行基数排序初始状态：329 457 839 439 720 355 350按个位数稳定排序后：720 350 355 457 329 839 439按十位数稳定排序后：720 329 839 439 350 355 457按百位数稳定排序后（最终结果）：329 350 355 439 457 720 839时间复杂度| 操作 | 时间复杂度 | 说明 | |------|-----------|------| | 基数排序 | O(d * (n + k)) | d

堆排序-总结

type: summary tags: [排序算法, 堆排序, 二叉堆, 原地排序, 时间复杂度] created: 2026-05-05 updated: 2026-05-05堆排序[[raw/articles/2026/05/堆排序]]一句话总结堆排序是基于二叉堆结构的原地排序算法，复杂度为 O(N log N)，通过原地建堆（Heapify）和排序两个步骤完成。核心要点1. 堆排序的两个关键步骤原地建堆（Heapify）：直接把待排序数组原地变成一个二叉堆。排序（Sort）：将元素不断地从堆中取出，最终得到有序的结果。2. 堆排序与优先级队列的关系最简单的堆排序思路是直接利用优先级队列：把所有元素塞到优先级队列里面，然后再取出来。但这种方法空间复杂度是 O(N)，因为需要额外的数据结构。堆排序解决的问题是：不要使用额外的辅助空间，直接在原数组上进行 sink, swim 操作，在 O(N log N) 的时间内完成排序。3. 二叉堆的关键原理二叉堆（优先级队列）底层是用数组实现的，但是逻辑上是一棵完全二叉树，主要依靠 swim, sink 方法来维护堆的性质。优先级队列可以分为小顶堆和大顶堆，小顶堆会将整个堆中最小的元素维护在堆顶，大顶堆会将整个堆中最大的元素维护在堆顶。优先级队列插入元素时，首先把元素追加到二叉堆底部，然后调用 swim 方法把该元素上浮到合适的位置，时间复杂度是 O(log N)。优先级队列删除堆顶元素时，首先把堆底的最后一个元素交换到堆顶作为新的堆顶元素，然后调用 sink 方法把这个新的堆顶元素下沉到合适的位置，时间复杂度是 O(log N)。基本原理堆排序基于二叉堆结构，通过 swim（上浮）和 sink（下沉）操作维护堆性质。利用优先级队列的简单实现思路：// 直接利用优先级队列对数组从小到大排序 void sort(int[] nums) {

布隆过滤器-总结

type: summary tags: [布隆过滤器, 数据结构, 概率型数据结构, 空间优化] created: 2026-05-03 updated: 2026-05-03布隆过滤器（Bloom Filter）[[raw/articles/2026/05/布隆过滤器]]⚠️ 内容不完整提示：原文使用 JavaScript 动态加载，仅获取到 35 行简介，核心原理、实现代码、详细分析等内容缺失。一句话总结布隆过滤器的核心能力是：在超大规模的数据集中，仅使用少量内存空间，即可快速判断一个元素是否存在。具备数据隐私性。即，可以在不暴露具体数据的情况下，判断一个元素是否存在。它的核心原理是，不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。核心原理布隆过滤器不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。与哈希集合的对比：| 特性 | 哈希集合 | 布隆过滤器 | |------|---------|------------| | 空间复杂度 | $O(N)$ | 远低于 $O(N)$ | | 数据存储 | 存储实际数据 | 仅存储哈希值（指纹） | | 数据隐私性 | 无（暴露实际数据） | 有（不存储实际数据） | | 查询时间

并查集基础

type: summary tags: [并查集, 数据结构, 图算法, 算法基础] created: 2026-05-04 updated: 2026-05-04并查集基础[[raw/articles/2026/05/并查集基础]]一句话总结并查集（Union Find）是二叉树结构的衍生，用于高效解决无向图的动态连通性问题，所有操作时间复杂度 O(1)。核心要点1. 并查集的核心价值并查集提供以下 API：union(p, q)：连接节点 p 和 q，O(1)connected(p, q)：查询 p 和 q 是否连通，O(1)count()：查询当前连通分量数量，O(1)为什么需要并查集：使用邻接表/邻接矩阵 + DFS/BFS 判断连通性需要 O(V+E)并查集只需一个数组，所有操作 O(1)特别适合处理动态连通性问题（边逐步增加）2. 动态连通性问题图结构中的连通操作与查询：连接操作：将节点 p 和 q 连通连通查询：判断两个节点是否连通（考虑传递性）统计连通分量：查询当前图中有多少连通分量连通关系的性质：自反性：节点 p 和 p 自身是连通的对称性：如果 p 和 q 连通，则 q

归并排序-总结

type: summary tags: [归并排序, 排序算法, 分治算法, 二叉树后序遍历] created: 2026-05-05 updated: 2026-05-05归并排序核心思路[[raw/articles/2026/05/归并排序]]一句话总结归并排序的核心思路需要结合 二叉树的后序遍历 来理解：先利用递归把左右两半子数组排好序，然后在后序位置合并两个有序数组。核心要点1. 归并排序的核心思想归并排序采用分治算法思想，结合二叉树的后序遍历：先递归地将左右两半子数组排好序，然后在后序位置合并两个有序数组。算法框架（概念性描述）：1. 分解：将数组分成左右两半 2. 解决：递归地对左右两半进行排序 3. 合并：在后序位置合并两个已排序的子数组2. 与快速排序的对比| 维度 | 快速排序 | 归并排序 | |------|---------|---------| | 遍历模式 | 二叉树前序遍历 | 二叉树后序遍历 | | 核心思路 | 先将一个元素放到正确位置，再递归处理左右 | 先递归处理左右，再合并结果 | | 分区方式 | partition：选择一个 pivot，将数组分为两部分 | merge：合并两个已排序的子数组 | |

快速排序算法

type: summary tags:排序算法快速排序时间复杂度递归分治算法 created: 2026-05-05 updated: 2026-05-05快速排序算法[[raw/articles/2026/05/快速排序算法]]⚠️ 内容不完整：原始网页为动态加载，仅成功提取开头部分，完整内容待补充一句话总结快速排序的核心思路需要结合 二叉树的前序遍历 来理解：在二叉树遍历的前序位置将一个元素排好位置，然后递归地将剩下的元素排好位置。核心要点1. 算法思路（基于二叉树遍历）快速排序的思维模式与二叉树前序遍历类似：前序位置：将一个元素排好位置（对应 partition 操作）递归过程：然后递归地将剩下的元素排好位置核心思想：把一个元素排好序，然后把剩下元素排好序，就能把整个数组排好序。2. 关键函数：partition快速排序的核心是 partition 函数：let p = partition(nums, lo, hi)这个函数负责：选择一个基准元素（pivot）将数组分为两部分：小于 pivot 的和大于等于 pivot 的返回 pivot 的最终位置3. 递归结构快速排序是一个典型的分治算法：调用 partition 确定 pivot 位置递归排序 pivot 左边的子数组递归排序 pivot 右边的子数组4. 算法可视化文章提供了交互式可视化面板，可直观观察快排的递归过程和排序效果。时间复杂度| 情况 | 时间复杂度 | 说明 | |------|-----------|------| |

排序算法的关键指标

type: summary tags:排序算法算法基础稳定性 created: 2026-05-05 updated: 2026-05-05排序算法的关键指标[[raw/articles/2026/05/排序基础]]一句话总结介绍排序算法的三个核心评估指标：时空复杂度、排序稳定性和是否原地排序，为后续学习具体排序算法打下基础。核心要点1. 时空复杂度排序算法的效率由时间复杂度和空间复杂度共同衡量。时间复杂度描述算法执行时间随输入规模增长的趋势，空间复杂度描述算法占用额外存储空间的情况。复杂度越低，算法性能越好。2. 排序稳定性稳定排序的定义：对于序列中的相同元素，如果排序之后它们的相对位置没有发生改变，则称该排序算法为「稳定排序」，反之则为「不稳定排序」。实际意义：对于简单 int 数组排序，稳定性意义不大对于复杂数据结构（如订单数据），稳定排序能保持多字段排序的层次性实例说明： 假设已有按日期排序的订单数据，现需按用户 ID 排序：使用稳定排序：相同用户 ID 的订单仍按日期有序排列使用不稳定排序：相同用户 ID 的订单相对位置可能变化，日期有序性丧失3. 是否原地排序原地排序定义：排序过程中不需要额外的辅助空间，只需要常数级别的额外空间，直接操作原数组进行排序。区别示例：// 非原地排序：需要 O(N) 额外空间 void sort(int[] nums) { int[] tmp = new int[nums.length]; // 辅助数组 // 对 nums 进行排序

插入排序-总结

type: summary tags: [排序算法, 插入排序, 稳定排序, 原地排序] created: 2026-05-05 updated: 2026-05-05插入排序[[raw/articles/2026/05/插入排序.md]]一句话总结插入排序是基于选择排序的优化，将 nums[sortedIndex] 插入到左侧有序数组中，对有序度较高的数组效率较高，是稳定排序。核心要点1. 核心思想：反向思维传统选择排序在右侧未排序部分找最小值插入左侧，插入排序反过来：在左侧已排序数组 [0, sortedIndex) 中找到 nums[sortedIndex] 应该插入的位置。类比：打扑克牌时，将新抓到的牌插入到手中已经排好序的牌中。2. 算法特性| 特性 | 值 | |------|-----| | 时间复杂度 | O(n²)，但有序度高时可接近 O(n) | | 空间复杂度 | O(1)，原地排序 | | 稳定性 | ✅ 稳定（只有 nums[i] < nums[i-1] 才交换） | | 综合性能

数组双指针技巧总结

type: summary tags: [双指针, 数组, 算法技巧, LeetCode] created: 2026-05-05 updated: 2026-05-05数组双指针技巧总结[[raw/articles/2026/05/数组双指针技巧总结]]一句话总结系统讲解数组中的双指针技巧，分为快慢指针（原地修改、滑动窗口）和左右指针（二分查找、n数之和、反转、回文）两大类，配合 LeetCode 经典题目实践。核心要点1. 双指针两大分类数组中的双指针技巧主要分为两类：| 类型 | 指针移动方式 | 典型应用 | |------|-------------|----------| | 快慢指针 | 同向而行，一快一慢 | 原地修改、滑动窗口 | | 左右指针 | 相向而行或相背而行 | 二分查找、n数之和、反转、回文 |2. 快慢指针：原地修改核心思想：慢指针 slow 走在后面，快指针 fast 走在前面探路，找到符合条件的元素就赋值给 slow 并前进。经典问题：| LeetCode | 问题 |

数组基础

type: summary tags: [数据结构, 数组, 算法, labuladong, 静态数组, 内存模型] created: 2026-05-02 updated: 2026-05-02数组基础：底层原理篇[[raw/articles/2026/05/数组基础]]侧重：静态数组的内存模型、地址计算原理、O(1) 随机访问的本质核心原理：静态数组的本质1. 内存模型静态数组在内存中的本质是一段连续的内存空间，以 int arr[10] 为例：开辟连续空间：操作系统分配 10 * sizeof(int) = 40 字节的连续内存数组指针：arr 是指向这段内存首地址的指针元素定位：每个元素占用固定大小（int = 4字节），通过首地址 + 偏移量精确定位内存布局示意： 首地址 → [int][int][int][int][int][int][int][int][int][int] ↑ 0

数组实现（动态数组）

type: summary tags: [数据结构, 动态数组, 数组实现, Java, labuladong, 扩缩容, 内存管理] created: 2026-05-02 updated: 2026-05-02动态数组实现：从理论到代码[[raw/articles/2026/05/数组实现（动态数组）]]侧重：动态数组的完整 Java 代码实现，包括扩缩容策略、索引检查、内存泄漏防护前置知识本文是 [[数组基础]] 的续篇，建议先阅读数组基础篇了解静态数组的内存模型。核心内容1. 动态数组的本质动态数组 ≠ 新的数据结构动态数组（如 Java ArrayList、C++ std::vector）底层仍然是静态数组，只是封装了：自动扩缩容逻辑增删查改的 API本文提供了完整的 Java 实现 MyArrayList<E>，包含以下核心功能：| 操作 | 方法 | 时间复杂度 | |------|------|-----------| | 尾部添加 | addLast(E e) | O(1) 均摊 | | 任意位置插入

时间空间复杂度入门

type: summary tags: [算法, 复杂度分析, 时间复杂度, 空间复杂度] created: 2026-05-02 updated: 2026-05-02时间空间复杂度入门 - 实用分析方法[[raw/articles/2026/05/复杂度分析基础]]来源：labuladong 算法网站 侧重：复杂度分析的实用方法（简化估算技巧）核心要点：实用估算方法1. 大O表示法简化原则关键规则：忽略常数项和低增长项，只保留最高增长项| 原始表达式 | 简化后 | |-----------|--------| | $O(2n^2 + 3n + 1)$ | $O(n^2)$ | | $O(1000n + 1000)$ | $O(n)$ | | $O(5\log n + 10)$ | $O(\log n)$ |2. 时间复杂度快速估算实用技巧：大部分情况下，看 for

树和映射数据结构基础

type: summary tags: [二叉搜索树, TreeMap, TreeSet, 数据结构, 有序映射] created: 2026-05-03 updated: 2026-05-03树和映射数据结构基础[[raw/articles/2026/05/树和映射数据结构基础]]一句话总结二叉搜索树（BST）通过左小右大特性实现 O(logN) 查找，TreeMap/TreeSet 底层基于 BST，相比 HashMap 能维护键的有序性。前置知识[[summaries/2026/05/二叉树基础及常见类型]][[summaries/2026/05/N叉树遍历基础]]核心内容1. 二叉搜索树（BST）的优势特性：左小右大对于树中的每个节点，其 左子树的每个节点 的值都要小于这个节点的值右子树的每个节点 的值都要大于这个节点的值时间复杂度： | 操作 | BST | 普通二叉树 | |------|-----|-----------| | 查找 | O(logN) | O(N) | | 插入 | O(logN) | - | | 删除 | O(logN)

桶排序-总结

type: summary tags:排序算法桶排序计数排序算法思想 created: 2026-05-05 updated: 2026-05-05桶排序[[raw/articles/2026/05/桶排序]]一句话总结桶排序通过「分配元素到桶 → 对每个桶排序 → 合并有序桶」三步骤实现排序，是归并排序与计数排序的通用形式。核心要点1. 桶排序三步骤分配：将待排序数组中的元素使用映射函数分配到若干个「桶」中排序：对每个桶中的元素进行排序（可使用任意排序算法）合并：将这些排好序的桶按顺序合并，得到最终排序结果2. 桶排序与归并排序的联系桶排序的思路类似归并排序：都是把大的数组分成小的数组进行排序，最后再合并。但桶排序更加灵活：归并排序是固定二分（k=2）桶排序可灵活决定桶的数量 k 和映射函数3. 桶排序与计数排序的联系当桶的数量 k 无限大，每个桶至多只有一个元素时，桶排序就转化成了计数排序，复杂度降低到 O(n)。关系总结：桶排序 (通用形式) ├─ k=2 时 → 类似归并排序 └─ k 足够大时 → 计数排序4. 分开排序更高效（数学证明）以选择排序为例：直接对大小为 n 的数组排序，时间复杂度 O(n²)。若将数组分成 k 个桶，每个桶大小为 n₁, n₂, ..., nₖ（n =

滑动窗口框架

type: summary tags: [滑动窗口, 算法框架, 双指针, LeetCode] created: 2026-05-05 updated: 2026-05-05滑动窗口算法框架[[raw/articles/2026/05/滑动窗口框架.md]]一句话总结提供滑动窗口算法的通用代码框架，通过左右指针维护窗口，将子数组/子串问题的时间复杂度从 O(N²) 优化到 O(N)。核心要点1. 滑动窗口基本原理滑动窗口是快慢双指针的应用，维护一个 [left, right) 左闭右开区间作为窗口，通过扩大和缩小窗口寻找满足条件的最优解。核心思路：第1步：移动 right 扩大窗口，直到满足条件（寻找可行解）第2步：移动 left 缩小窗口，优化结果（优化可行解）重复上述过程，直到 right 到达尽头时间复杂度 O(N) 的原因：left 和 right 指针只增不减，不回退每个元素只进入窗口一次，离开窗口一次嵌套 while 循环的总执行次数与 N 成正比（均摊分析）2. 通用代码框架// 滑动窗口算法伪码框架 void slidingWindow(String s) { // 用合适的数据结构记录窗口中的数据

环形数组技巧及实现

type: summary tags: [数据结构, 环形数组, 数组, 算法技巧, Java] created: 2026-05-02 updated: 2026-05-02环形数组技巧及实现[[raw/articles/2026/05/环形数组技巧及实现]]一句话总结环形数组通过求模（余数）运算在逻辑上实现数组环形化，可将头尾增删元素的时间复杂度优化至 $O(1)$，核心是通过 start 和 end 两个指针维护有效元素区间。核心原理逻辑环形：数组本身是线性连续内存，通过 % 求模运算实现索引循环（如 i = (i + 1) % arr.length 可无限遍历数组）双指针维护：start 指向第一个有效元素（闭区间），end 指向最后一个有效元素的下一个位置（开区间），形成左闭右开区间 [start, end)边界处理：指针移动超出数组边界时，通过求模运算自动回绕到数组另一端，无需数据搬移时间复杂度优势| 操作 | 普通数组 | 环形数组 | |------|----------|----------| | 头部增删 | $O(N)$（需搬移元素） | $O(1)$（仅移动 start

理解递归框架

type: summary tags: [递归, 算法框架, 二叉树, 思维模式] created: 2026-05-06 updated: 2026-05-06理解递归框架[[raw/articles/2026/05/理解递归框架.md]]一句话总结从「树」的角度理解递归，掌握「遍历」和「分解问题」两种递归思维模式，是编写递归算法的核心要领。核心要点1. 从树的角度理解递归核心观点：理解和编写递归算法最有效的方法是从「树」的视角去理解，其他的视角（如镜像、栈）都属于花拳绣腿。论证例子：斐波那契数列：递归结构是一棵二叉树，fib(n) = fib(n-1) + fib(n-2)全排列问题：递归结构是一棵多叉树，每个节点代表一次选择2. 编写递归的两种思维模式所有递归算法都可以用以下两种思维模式之一来编写：模式一：分解问题（Divide & Conquer）特点：递归函数有清晰的定义和返回值利用定义计算子问题，通过子问题的解推导原问题的解类似数学归纳法适用场景：斐波那契数列、二叉树最大深度（LeetCode 104）、动态规划代码示例（二叉树最大深度）：// 定义：输入一个节点，返回以该节点为根的二叉树的最大深度 public int maxDepth(TreeNode root) { if (root == null) { return 0;

用链表实现队列栈

type: summary tags: [数据结构, 链表, 队列, 栈, Java] created: 2026-05-03 updated: 2026-05-03用链表实现队列/栈[[raw/articles/2026/05/链表实现队列和栈]]核心要点本文是 labuladong 数据结构基础系列教程，讲解如何以链表作为底层结构实现栈和队列，所有操作均达到 O(1) 时间复杂度。用链表实现栈使用双链表（java.util.LinkedList）作为底层存储可将双链表的头部或尾部作为栈顶：两端增删操作均为 O(1)示例代码 MyLinkedStack：push(E e)：向栈顶添加元素 → list.addLast(e)（尾部作为栈顶）pop()：弹出栈顶元素 → list.removeLast()peek()：查看栈顶 → list.getLast()若改为头部作为栈顶，只需将 addLast → addFirst、removeLast → removeFirst、getLast → getFirst用链表实现队列同样使用双链表作为底层存储将双链表头部作为队头、尾部作为队尾：头部删除 O(1)，尾部添加 O(1)示例代码 MyLinkedQueue：push(E e)：入队 → list.addLast(e)（队尾添加）pop()：出队 → list.removeFirst()（队头删除）peek()：查看队头 → list.getFirst()也可反转方向，将头部作为队尾、尾部作为队头，只需调整对应 API

线性探查法的两个难点

type: summary tags: [哈希表, 线性探查法, 开放寻址法, 数据结构, 算法原理, 哈希冲突] created: 2026-05-03 updated: 2026-05-03线性探查法的两个难点[[raw/articles/2026/05/线性探查法的两个难点]]⚠️ 注意：原文使用 JavaScript 动态加载内容，未能获取完整正文（仅获取到"简化场景"部分，缺少"两个难点"的核心内容）。以下为基于现有内容的摘要，待补充完整内容。核心要点（侧重算法原理理解）前置知识本文建立于以下基础知识之上：[[哈希表基础]]哈希冲突解决方法对比| 方法 | 别名 | 基本原理 | 特点 | |------|------|---------|------| | 拉链法 | 链地址法 | 数组每个位置存储链表，冲突元素追加到链表 | 实现简单，每个桶独立 | | 线性探查法 | 开放寻址法 | 冲突时往后找空位（index+1, +2, ...） | 所有元素存在数组中，缓存友好 |![[images/hash-collision.jpeg]]线性探查法基本原理核心思想：当发生哈希冲突时，从冲突位置开始，线性向后探查，直到找到：相同的 key（更新值）空位（插入新键值对）到达数组末尾（探查失败，需特殊处理）算法特性：所有数据存储在同一个数组中（不像拉链法需要额外链表）探查序列：hash(key),

计数排序-总结

type: summary tags: [排序算法, 计数排序, 非比较排序] created: 2026-05-05 updated: 2026-05-05计数排序[[raw/articles/2026/05/计数排序]]一句话总结计数排序通过统计每种元素出现的次数来推算排序后位置，时间空间复杂度均为 O(n + max - min)，是一种非比较排序算法。核心要点1. 基本原理计数排序的核心思想是：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。需要将元素的值作为 count 数组的索引才能计数仅关心元素出现次数，不关心相同元素的相对位置 → 不稳定排序适合元素值范围不大的场景2. 时间空间复杂度| 指标 | 复杂度 | 说明 | |------|--------|------| | 时间复杂度 | O(n + max - min) | n 是数组长度，max - min 是元素值范围 | | 空间复杂度 |

贪心算法解题套路框架

type: summary tags:贪心算法算法思想动态规划回溯算法 created: 2026-05-06 updated: 2026-05-06贪心算法解题套路框架[[raw/articles/2026/05/贪心算法解题套路框架]]一句话总结贪心算法通过局部最优选择推导全局最优解，无需穷举所有可行解，是对回溯和动态规划的进一步剪枝优化。核心要点1. 贪心算法与回溯、动态规划的本质区别算法的本质都是穷举，区别在于穷举的范围和优化手段不同：| 算法思想 | 优化手段 | 穷举范围 | 算法复杂度 | |---------|---------|---------|-----------| | 回溯算法 | 剪枝优化：提前排除不可能的答案，使树结构尽可能小 | 穷举所有可行解 | 一般指数级别（如 $O(2^n)$） | | 动态规划 | 备忘录优化：避免重复计算，把树形结构优化成线性结构 | 穷举所有可行解（去重后） | 一般多项式级别（如 $O(n^2)$） | | 贪心算法 | 推导最优：不需要完整穷举，直接推导最优解 | 不穷举所有可行解 | 可优化到常数级别（如 $O(1)$） |核心洞察：回溯和动态规划都穷举了所有可行解，试图从中寻找最优解；贪心算法则跳过完整穷举，通过局部最优选择直接推导全局最优。2.

跳表基础

type: summary tags: [数据结构, 跳表, 链表, 算法, 空间换时间] created: 2026-05-02 updated: 2026-05-02跳表基础[[raw/articles/2026/05/跳表基础]]一句话总结跳表（Skip List）通过空间换时间思想，在原始链表上构建多层索引，将查询、插入、删除操作的时间复杂度从 $O(N)$ 优化到 $O(\log N)$，实现难度远低于自平衡二叉搜索树。核心原理问题背景普通单链表中，通过索引查询对应节点需要从头结点开始逐个遍历，时间复杂度为 $O(N)$。即使拿到目标节点后的增删改操作只需 $O(1)$，查找的瓶颈导致整体效率低下。跳表设计跳表在原始链表基础上增加多层索引：每向上一层，索引节点数量减少一半，索引间隔变为 2 倍索引高度为 $\log N$（$N$ 为链表元素个数）示例结构：indexLevel 0-----------------------8-----10 indexLevel 0-----------4-----------8-----10 indexLevel 0-----2-----4-----6-----8-----10 indexLevel 0--1--2--3--4--5--6--7--8--9--10 nodeLevel a->b->c->d->e->f->g->h->i->j->k查询过程（以查索引 7 为例）最高层：区间 [0,

选择排序-总结

type: summary tags:排序算法选择排序时间复杂度稳定排序 created: 2026-05-05 updated: 2026-05-05选择排序[[raw/articles/2026/05/选择排序]]一句话总结选择排序是最简单朴素的排序算法，时间复杂度 O(n²)，不是稳定排序，其他基础排序算法都是基于选择排序的优化。核心要点1. 算法思路先遍历数组找到最小值，与第一个元素交换；再遍历剩余部分找到次小值，与第二个元素交换；以此类推直到整个数组有序。2. 时间复杂度与优化尝试时间复杂度：O(n²)，嵌套循环执行 n²/2 次特点：即使数组已有序，仍执行相同次数，原始数据有序度不影响时间复杂度优化尝试：尝试用 suffixMin 数组预计算后缀最小值，但因交换操作导致 nums 变化，预计算失效，无法优化3. 排序稳定性不是稳定排序：交换操作会打乱相同元素的相对位置原因：第一次寻找最小值时就可能交换，破坏相同元素的原始顺序优化思考：作者提出思考方向，后续排序算法会尝试解决基本原理选择排序的核心：每次选择未排序部分的最小值，放到已排序部分的末尾。void sort(int[] nums) { int n = nums.length; int sortedIndex = 0; // 已排序/未排序分割线 while (sortedIndex <

链表基础

type: summary tags: [数据结构, 链表, 算法, labuladong, 单链表, 双链表, 指针操作] created: 2026-05-02 updated: 2026-05-02链表基础：单链表与双链表的操作[[raw/articles/2026/05/链表基础]]侧重：链表的内存模型、单/双链表增删查改操作、时间复杂度分析、指针操作技巧核心原理：链表的内存模型1. 链表 vs 数组| 特性 | 数组 | 链表 | |------|------|------| | 内存分布 | 连续内存空间 | 分散的内存块 | | 访问方式 | O(1) 随机访问（索引计算） | O(N) 顺序访问（遍历指针） | | 扩容 | 需重新分配 + 复制（O(N)） |

链表实现

type: summary tags: [数据结构, 链表, 算法, labuladong, 双链表, 单链表, 虚拟头尾节点, Java实现] created: 2026-05-02 updated: 2026-05-02链表实现：双链表与单链表的完整 Java 实现[[raw/articles/2026/05/链表实现]]侧重：链表的工程级实现（虚拟头尾节点、头尾引用、内存管理）、完整的增删查改操作核心实现技巧1. 同时持有头尾节点引用在实际开发中，双链表通常会同时持有头尾节点的引用，以优化尾部操作性能：| 操作 | 无尾引用 | 有尾引用 | |------|---------|---------| | 尾部添加 | O(N) 需遍历 | O(1) | | 尾部删除 | O(N) 需找前驱 | O(1)（单链表仍需遍历前驱）|单链表的权衡：持有尾引用可以 O(1) 添加，但删除时仍需遍历找前驱删除尾节点时，正好需要遍历到倒数第二个节点，可以顺便更新尾引用2. 虚拟头尾节点（Dummy Head/Tail）这是本文的核心技巧，在 [[链表基础]] 中已提及虚拟头结点，本文扩展到虚拟头尾节点：原理：创建链表时就创建虚拟头节点（dummyHead）和虚拟尾节点（dummyTail）无论链表是否为空，这两个节点都存在避免空指针问题，简化边界条件处理示例：空链表：dummyHead

链表技巧总结

type: summary tags: [数据结构, 链表, 算法, 双指针, labuladong, LeetCode] created: 2026-05-05 updated: 2026-05-05链表技巧总结：双指针的七大应用场景[[raw/articles/2026/05/链表技巧总结]]侧重：双指针技巧在单链表算法中的7大应用场景，每种技巧对应1-2道经典LeetCode题目一句话总结本文系统总结了单链表算法中双指针技巧的7种核心应用，覆盖合并、分解、查找、环检测、交点判断等常见场景，每种技巧都配有Java实现和LeetCode对应题目。核心要点1. 合并两个有序链表对应题目：LeetCode 21 / 力扣 21核心思路：类似"拉拉链"，用两个指针分别遍历两个链表，每次取较小节点接入结果链表。关键技巧：使用**虚拟头结点（dummy）**简化边界处理——当需要创造一条新链表时，虚拟头结点可以避免处理空指针的情况。ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1), p = dummy; ListNode p1 = l1, p2 =