Category: 数据结构

【leetbook】树的技巧

摘要: 普通树的 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings LeetBook 链接:树的技巧。 树的基本概念 树 根 树叶 兄弟 祖父 孙子 路径 路

【leetbook】哈希的技巧

摘要: 哈希技巧的 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings LeetBook 链接:哈希思想。 哈希表基础知识 线性探测 945 闭散列表 邻接

手撕平衡树-Treap

摘要: Treap 的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前,我们已经写过不少关于树的文章,包括二叉树、二叉查找树、平衡树。 二叉树 树的DFS

手撕平衡树-数组模拟链表实现二叉查找树

摘要: 用数组模拟链表的方式实现二叉查找树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们用数组模拟链表的方式实现二叉查找树,并形成代码模板。 关于二叉查找树,在文章 手撕

用数组模拟链表的方式实现【带权有向图的邻接表】

在文章 邻接表 中,我们学习了邻接表及其应用,在文章 用数组模拟双向循环链表 中,我们学习了用数组模拟的方式实现链表,并用该链表解决了实际问题,同时 结合链表容易删除的特点使用逆向思维 中也介绍了一个思路完全一样的题目,也是用数组模拟链表解决的。 邻接表中的链表实际上也可以用数组模拟的方式来实现,本文我们就来看一下带权有向图的邻接表用数组模拟的实现方式。 带权有向图的邻接表在一个有 n 个点,m

结合链表容易删除的特点使用逆向思维

逆向思维是一种常见的算法思维方式,在文章 逆向思维 中,我们例举了不少 leetcode 上用逆向思维解决的问题。 链表由于有易于删除的特点,因此经常与逆向思维结合使用。 在例如在文章 加索引的数组,用数组模拟双向循环链表 中我们解决的 136. 邻值查找。 本文我们再看一个类似的题 106. 动态中位数,本题的主流解法是 对顶堆,它是在线算法。这里我们用基于链表和逆向思维的离线算法。 问题依次读

用数组模拟双向循环链表

在文章 【模板】双向链表 中,我们实现了双向循环链表,并将其用在实现了 LFU,以及实现循环双端队列中。 在文章 邻接表,中我们学习了一种基于链表的数据结构: 邻接表。这种邻接表可以应用在桶、开散列表以及图和树存储中。 在文章 加索引的数组 和 加索引的链表 中,我们学习了对链表和数组中加各种索引的方式。 本文我们来看一种用数组模拟双向循环链表的实现方法,相关的基础知识可以看前面的几篇文章,重点是

大学数据结构笔记

摘要: 大学数据结构的笔记 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 大学数据结构笔记,2017年,共 51 页。主要内容如下: 数据结构基础 栈 队列 表 静态查找表 高级

leetcode题目汇总-栈

摘要: 力扣上的栈的问题汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结一下力扣上 2000 题以内的关于栈的 73 道题。 栈是一种最基础的数据结构,本身是比较简单的,而且没什么变化

两本高级数据结构的英文书

本文给大家分想两本高级数据结构的书。LeetCode 主要是针对面试的算法刷题平台,在 LeetCode 之外也有很多高级一些的算法和数据结构,其中有一些比较实用的会在面试中遇到,比如在文章 大数据应用中的概率算法与数据结构 中提到过的海量数据处理场景中的概率算法。 与前面提到的海量数据处理中的随机算法不同,高级数据结构与算法这块其实还是有很多中文书可以参考的,本文分享其中两本英文书。 第一本是《

中序遍历过程中通过引用维护前驱

相关算法参考 二叉查找树的中序遍历和前驱后继 783. 二叉搜索树节点最小距离给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值。 示例 1:输入:root = [4,2,6,1,3]输出:1示例 2:输入:root = [1,0,48,null,null,12,49]输出:1 提示:123树中节点数目在范围 [2, 100] 内0 <= N

二叉树的建树

摘要: 本文介绍了一类由给定的递归定义的建树规则进行建树的问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 相关的内容: 递归 中缀表达式建表达式树 后缀表达式建表达式树 抽象问题给出一组

【模板】双向链表+哈希映射,有序字典,LRU,LFU

背景 链表维护数据插入顺序 对链表节点的高效查询, 加索引的链表 【模板】无重哈希映射 【模板】双向链表 模板应用: 实现带更新顺序的字典 Python OrderedDict 模板 : 双向链表+哈希映射实现带更新顺序的字典 应用: 340. 至多包含 K 个不同字符的最长子串 模板应用: 实现带访问顺序的字典 146. LRU缓存机制 模板 : 双向链表+哈希映射实现带访问顺序的字典

【模板】双向链表的懒释放

惰性更新与懒释放 带懒释放的双向循环链表 懒释放 模板 测试: 1388. 3n 块披萨 $1 惰性更新与懒释放惰性更新是一种面对频繁操作时,先把操作记下来,等查询时再把记下的操作一次性都做掉,这在很多时候可以提高性能,因为有时候操作可以合并。参考 惰性更新 在基于数组的数据结构中对指定节点删除经常是一种比较重的操作,需要根据实际情况判断是否要用惰性更新的方式,即懒删除,具体的操作是

【模板】双向链表

双向循环链表 节点定义 接口 迭代器相关 定点增删改查 头尾增删改查 模板: 双向循环链表 测试: 剑指 Offer 62. 圆圈中最后剩下的数字 应用 460. LFU缓存 【模板】双向链表+哈希映射,有序字典,LRU,LFU 模板: 641. 设计循环双端队列 $1. 双向循环链表(1) 节点定义1234567891011typedef int DLType;const

【模板】无重哈希映射

哈希集合 无重映射 哈希映射在哈希集合基础上的变化 模板:闭散列表无重哈希映射 模板:开散列表无重哈希映射 测试: 706. 设计哈希映射 应用: 460. LFU缓存 有重映射 $1 哈希集合哈希映射是将哈希集合中的每个节点加一个数据的字段,其余部分与哈希集合基本一样。支持集合增删改查的哈希表理论也与哈希集合一样。 【模板】哈希集合 $2 无重映射 insert(k, v):

【模板】哈希集合

哈希函数 取余 相乘取整 哈希冲突 闭散列 线性探测 平方探测 再散列探测 开散列 邻接表 重哈希(rehash) 原理 触发时机 可重集合实现方式 模板 闭散列表 (无重集合/可重集合) 开散列表 (无重集合/可重集合) 测试:705. 设计哈希集合 应用:1074. 元素和为目标值的子矩阵数量 $1 哈希函数(1) 取余1234int hash1(const

哈希索引堆的索引优化

背景 - 哈希索引堆 哈希索引堆的优化 — 分配唯一 ID 分配唯一 ID 代码 (模板: 分配唯一ID的哈希索引堆) 测试: 239. 滑动窗口最大值 哈希索引堆的优化 — vector 代替 unordered_map vector 代替 unordered_map 代码 (模板: ID从1自增时用vector代替unordered_map的哈希索引堆) 测试: 239. 滑动窗口最大值

邻接表

桶 开散列表 图和树存储 邻接表 链式前向星 $0 邻接表邻接表可以看成带有索引数组的多个数据链表。索引数组称为表头数组,其中每一项指向一个数据链表的表头。 邻接表中的数据天然地被分为若干类,每一类的数据在一个链表中。 这里的表头数组和数据链表均可以根据插入删除以及查询的需要选择用动态数组或链表实现。 邻接表的应用许多数据结构用到了邻接表的这种将数据分类的特性。 桶 开散列表 图 $

链表维护多项式

加法 1634. Add Two Polynomials Represented as Linked Lists 一个节点代表多项式的一项,节点中持有的属性如下: 1234567struct PolyNode { int coefficient, power; PolyNode *next; PolyNode(): coefficient(0), power(0),

深拷贝

摘要: 经典的二叉堆的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们看4个题,leetcode第1490题【1490. 克隆 N 叉树】,第133题【133. 克隆图

下标索引堆

背景 - 哈希索引堆及其优化 二叉堆 堆的标记删除 哈希索引堆 哈希索引堆的索引优化 下标索引堆 内部树形索引 外层哈希索引 代码 测试: 239. 滑动窗口最大值 索引堆优化邻接矩阵 Prim $0 背景(1) 支持按 key 删除的堆一般的堆不支持按key操作,例如按 key 删除,按 key 修改。 现实中这种需求是常见的,例如进程调度的时候,进程 ID 和进程优先级在一个堆中

堆的标记删除

堆的按 key 删除 直接哈希索引: 哈希索引堆 标记删除: 惰性更新 不修改数据数组,先标记删除(_size 不变),从堆头弹出时再真正删除 题目 239. 滑动窗口最大值 480. 滑动窗口中位数 $0 场景一般的堆不支持按 key 删除。 现实中这种需求是常见的,例如进程调度的时候,进程 ID 和进程优先级在一个堆中维护。直接删除某个进程 ID 是很合理的需求。 为了实现

哈希索引堆

哈希索引堆 直接哈希索引 后续优化: 哈希索引堆的索引优化 题目 912. 排序数组 239. 滑动窗口最大值 480. 滑动窗口中位数 $0 场景一般的堆不支持按key操作,例如按 key 删除,按 key 修改。 现实中这种需求是常见的,例如进程调度的时候,进程 ID 和进程优先级在一个堆中维护。直接删除某个进程 ID,以及根据进程 ID 修改进程优先级,都是很合理的需求。 如果

加索引的数组

$0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一种自带索引的数据结构(索引结构)。即将数据项(key)插入进去之后,可以随时根据给定的 key,可以快速查到它所在节点的位置。 作为对比,数组,链表就没有这种根据 key 快速找到其所在节点的特性,数据项(key)插入进去之后,如果想给定 key 找到对应的节点,只能线性扫描去找。(栈,

线性索引表

$1 线性索引表将数组中数据的 key 和数据在数组中的节点位置以元组的形式放进数组维护,这个保存 key 和节点位置的数组称为线性索引表,如图。 如果只是建这么一个线性索引表,其实用处不大: 调度节点层面:当数据通过与尾部交换的方式插入删除时,数据在数组中的节点位置发生变化,需要更新索引,由于在数组中查找 key 是 $O(N)$ 的,更新索引比较困难。 查询层面:通过线性索引查询 key,

对顶堆

$0 场景维护一个数据结构支持以下操作: 插入 key 查询当前数据结构中的中位 key $1 对顶堆以中位数为例,维护一个大顶堆,一个小顶堆,大顶堆,将大顶堆放左边,小顶堆放右边,两个队头对着。 从左向右看两个堆中的数据,恰好从大顶堆底到大顶堆顶到小顶堆顶到小顶堆底是递增的。 维护的时候始终保持两堆的数据量平衡,即左堆数据量始终等于右堆或者比右堆多一个。 平衡12345左堆大小 > 右

二叉堆

摘要: 经典的二叉堆的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 二叉堆原理堆是一种支持插入key,删除堆顶key,查询key的最值的数据结构,二叉堆对是一种满足堆

对顶栈

$1 场景有一个光标,给出对光标的操作序列,维护操作结果,当操作有以下特性时,对顶栈可以很好地解决。 一次只移动一位 添加、删除均在光标操作 操作位置一定在光标左右 对顶栈实现12vector<int> st_l; // 左栈数据,光标在左栈栈顶vector<int> st_r; // 右栈数据 $2 题目1472. 设计浏览器历史记录问题你有一个只支持单个标签页的

加索引的链表

$0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一种自带索引的数据结构(索引结构)。即将数据项(key)插入进去之后,可以随时根据给定的 key,可以快速查到它所在节点的位置。 作为对比,数组,链表就没有这种根据 key 快速找到其所在节点的特性,数据项(key)插入进去之后,如果想给定 key 找到对应的节点,只能线性扫描去找。(栈,

随机队列

摘要: 本文介绍随机队列的原理和代码模板,以及 2 道 leetcode 相关题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 随机队列 增加删 key 的支持 380. 常数时间插入、删除和

线段树区间修改

线段树相关基础 力扣1476-子矩形查询,延迟计算 线段树,树状数组 线段树维护区间最值RMQ 离散化,权值线段树,权值树状数组 线段树和树状数组题目汇总 线段树更新非叶节点 带懒标记的线段树模板 同时支持区间加法和区间乘法,区间求和模板 1622. 奇妙序列 P3373 【模板】线段树 2 线段树区间修改 懒标记当线段树有区间修改的需求 range_update_add(i, j,

单调队列

摘要: 单调队列的算法原理,代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文详细介绍单调队列的算法原理、代码模板和应用。涉及到的题目汇总如下: 基本模型 239. 滑动窗口最大值

跳表

摘要: 跳表的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 跳表背景与哈希表、平衡树、Trie类似,跳表也可以看成是一种自带索引的数据结构(索引结构)。即根据给定的 key,可以快

线段树维护区间最值RMQ

线段树的区间修改模板 数组写法 链式写法 线段树的单点更新和区间查询参考 : 线段树,树状数组 问题问题:给你一个数组 ,其中有 N 个数字,现在给你一次查询,给你区间[l ,r],问你在这个区间内的最值为多少 数组长度为 N,查询次数为 Q 主流解法 1、搜索,$O(n)$ 预处理 $O(qn)$ 在线查询。 2、稀疏表(ST),$O(nlogn)$ 预处理 $O(q)$ 在线查询。

线性探测解决哈希冲突

闭散列法:线性探测解决哈希冲突 945. 使数组唯一的最小增量 闭散列表设计 705. 设计哈希集合 706. 设计哈希映射 更好的闭散列表模板 【模板】哈希集合 $1 闭散列法:线性探测解决哈希冲突945. 使数组唯一的最小增量给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 12345678910111

二叉查找树的中序遍历和前驱后继

背景: 树的DFS遍历 手撕平衡树-二叉查找树BST 中序遍历 98. 验证二叉搜索树 99. 恢复二叉搜索树 230. 二叉搜索树中第K小的元素 255. 验证前序遍历序列二叉搜索树 272. 最接近的二叉搜索树值 II 426. 将二叉搜索树转化为排序的双向链表 501. 二叉搜索树中的众数 530. 二叉搜索树的最小绝对差 776. 拆分二叉搜索树 1305. 两棵二

设计-基础数据结构

实现哈希表 705. 设计哈希集合 706. 设计哈希映射 实现字典树 208. 实现 Trie (前缀树) 实现线段树 307. 区域和检索 - 数组可修改 308. 二维区域和检索 - 可变 实现前缀和 303. 区域和检索 - 数组不可变 304. 二维区域和检索 - 矩阵不可变 实现四叉树 427. 建立四叉树 实现队列 622. 设计循环队列 641. 设计循环双

设计-功能系统

摘要: 力扣上的设计功能系统的题目分类汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于设计功能系统的 38 道题。将核心数据结构相同的放到了一起。刷完这份

设计-迭代器模式

迭代器模式基本接口 T next() bool hasNext() 迭代器模式题目 281. 锯齿迭代器 173. 二叉搜索树迭代器 284. 顶端迭代器 1286. 字母组合迭代器 251. 展开二维向量 604. 迭代压缩字符串 341. 扁平化嵌套列表迭代器 1586. 二叉搜索树迭代器 II $1 迭代器模式对于以下循环12for(int i = 0; i < n;

手撕平衡树-二叉查找树BST

摘要: 二叉查找树(BST)的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 二叉查找树定义二叉查找树(Binary Search Tree)是指一棵空树

手撕平衡树-大小平衡树SBT

摘要: 大小平衡树的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们知道二叉查找树在多次插入删除之后会变得不平衡,使得树的深度逐渐大于 $O(logN)$,使得查询的效率变低。如果能引

树状数组维护区间最值RMQ

考虑以下需求:给定一个数组 a,支持区间和的查询, 其中 a 中的元素可变,每次变化 a 中的 1 个元素。这个需求用带单点修改和区间查询的线段树或树状数组都可以解决,其中用树状数组的代码量少很多。 如果 a 不变,则是前缀和解决的问题。而对与 a 可变的情况,区间和查询是树状数组解决的最基本的问题,它在力扣上有对应的题目: 线段树,树状数组 二维线段树,二维树状数组 现在需求变一下,把支

单调栈题目汇总

摘要: 单调栈的题目汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单调栈基本思想和模板单调栈的算法原理和代码模板看这篇文章:单调栈。 单调栈的题目以下是单调栈的题目列表,思路类似,可以集

单调栈

单调栈的核心使用场景:摊销O(1)地获得所有位置上两侧第一个比它大/小的数的位置 基本模型:直方图最大矩形 单调栈题目列表: 单调栈题目汇总 $0 单调栈基本模型模型问题数组 A[i], 求 L[i], R[i] 12L[i] := [0..i-1] 上离 i 最近的大于 A[i] 的下标R[i] := [i+1..n-1] 上离 i 最近的大于 A[i] 的下标 84.

二维线段树,二维树状数组

以下二维树状数组和二维线段树的内容不含区间修改。 二维树状数组 二维线段树的两种实现方式: 四叉树和树套树 四叉树有链式写法和数组写法 树套树一般不写链式 四分分治:1274. 矩形内船只的数目 $1 题目题目链接308. 二维区域和检索 - 可变 题目描述给你一个 2D 矩阵 matrix,请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形

线段树和树状数组题目汇总

分治参考线段树隐含分治思想 前缀和参考树状数组隐含前缀和思想 前缀和问题分类汇总 线段树和树状数组一维 307. 区域和检索 - 数组可修改 单点修改+区间查询;链式线段树;数组线段树;树状数组 1476. 子矩形查询 区间修改+单点查询;保存操作,查询时再执行求结果 715. Range 模块 平衡树也可以 699. 掉落的方块 区间修改;平衡树区间管理 lc715 二维 308. 二维区域

离散化,权值线段树,权值树状数组

离散化模板 权值线段树模板 权值树状数组模板 CDQ 分治 $1 题目题目链接493. 翻转对 题目描述给定一个数组 nums ,如果 $i < j$ 且 $nums[i] > 2 * nums[j]$ 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 数据范围 给定数组的长度不会超过50000。输入数组中的所有数字都在32位整数的表示范围内。

线段树,树状数组

以下树状数组和线段树的内容不含区间修改。区间修改的内容参考 力扣699-平衡树区间模块,RMQ 线段树单点修改区间查询模板 链式写法 数组写法 树状数组单点修改区间查询模板 线段树和树状数组的区别和联系 $1 题目题目链接307. 区域和检索 - 数组可修改 题目描述给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点

链表问题汇总

摘要: 总结链表题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 链表节点操作 61. 旋转链表 86. 分隔链表 21. 合并两个有序链表 23. 合并K个升序链表 109. 有序链表转