Category: 数据结构

2020
算法数据结构

对顶栈

摘要: 对顶栈的使用场景 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $1 场景有一个光标，给出对光标的操作序列，维护操作结果，当操作有以下特性时，对顶栈可以很好地解决。 一次只移动一位 添加、

算法数据结构

加索引的链表

摘要: 加索引的链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 背景有些数据结构可以根据 key 快速找到其所在节点，例如哈希表、平衡树、Trie，跳表。这些可以看成是一

算法数据结构

随机队列

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

算法数据结构

自定义堆或优先级队列的比较规则：基于比较函数或键函数

摘要: C++ / Python 的堆或优先级队列中，自定义比较函数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，我们知道排序可以自定义比较规则，参考文章 自定义排序题目清单：自定义定义

算法数据结构

线段树大模板：区间修改(加法、乘法)、区间和查询

摘要: 线段树区间修改(加法、乘法)、区间和查询 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 线段树和树状数组：单点修改、区间和查询 中我们学习了线段树的单点更新、区间查询，并解决了区间求

算法数据结构

单调队列

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

算法数据结构

跳表

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

算法数据结构

线段树：区间修改(更改为定值)、区间最值查询

摘要: 线段树，区间修改与区间查询，原理与实现，RMQ 问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 线段树和树状数组：单点修改、区间查询，区间求和问题 中，我们学习了带单点修改、区间

算法数据结构

线性探测解决哈希冲突

摘要: 线性探测法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 哈希表在发生冲突时，有开散列法和闭散列法两种主流的处理方法。线性探测法是闭散列法中比较简单的一种。本文我们通过力扣 945，来看一

算法数据结构

LFU：维护最频繁访问的元素

摘要: LFU 的原理、实现与应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们详细介绍 LFU 的思想，以 460. LFU缓存 为模板题实现 LFU 的插入和查询，形成代码模板。 最后

算法数据结构

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

摘要: BST 的中序遍历，前驱和后继 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 中序遍历题目清单 98. 验证二叉搜索树 99. 恢复二叉搜索树 230. 二叉搜索树中第K小的元素 2

算法数据结构

设计-基础数据结构

摘要: 力扣上的基础数据结构设计的题目分类汇总 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 实现哈希表 705. 设计哈希集合 706. 设计哈希映射 实现字典树 208. 实现 Tr

算法数据结构

设计-功能系统

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

算法数据结构

LRU：维护最近访问/插入的元素

摘要: LRU 的原理、实现与应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们详细介绍 LRU 的思想，以 146. LRU缓存机制 为模板题实现 LRU 的插入和查询，形成代码模板。

算法数据结构

设计-迭代器模式

摘要: 迭代器模式，题目清单，典型题解 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们简要介绍一下常用的设计模式：迭代器模式。列出了一些与迭代器相关的题目清单。最后解决两个比较典型的问题。

算法数据结构

稀疏相似度：倒排索引

摘要: 倒排索引简介及其在稀疏相似度中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 单词-文档矩阵单词—文档矩阵是表达两者之间所具有的一种包含关系的概念模型，每列代表一个文档，每行代表一个单

算法数据结构

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

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

算法数据结构

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

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

算法数据结构

树状数组：单点修改，区间最值查询

摘要: 线段树和树状数组，单点修改与区间查询，原理与实现 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 考虑以下需求：给定一个数组 a，支持区间和的查询, 其中 a 中的元素可变，每次变化 a 中的

算法数据结构

单调栈题目汇总

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

算法数据结构

单调栈：两侧距离最近的更大元素

摘要: 单调栈的算法原理，代码模板和应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以力扣 84. 柱状图中最大的矩形 为模板题，串讲一下单调栈的思路和代码。在文章 单调栈题目汇总 中列

算法数据结构

二维线段树：单点修改，矩阵和查询

摘要: 二维线段树，单点修改与矩阵查询，原理与实现 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文通以 308. 二维区域和检索 - 可变 作为模板题来看一下二维线段树的原理与实现。 本文的线段

算法数据结构

权值线段树、权值树状数组：元素排名区间的权值(个数)和

摘要: 元素的计数，权值线段树、权值树状数组 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 线段树和树状数组：单点修改、区间和查询 中，我们知道线段树和树状数组可以处理元素

算法数据结构

线段树和树状数组：单点修改、区间和查询

摘要: 线段树和树状数组，单点修改与区间查询，原理与实现 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文通以 307. 区域和检索 - 数组可修改 作为模板题来看一下线段树和树状数组的原理与实现

算法数据结构

链表问题汇总

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

算法数据结构

用数据结构维护前缀状态信息

摘要: 用前缀和的思想表示维护前缀上的状态信息 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 使用类似前缀和的处理方式，维护前缀或后缀的一些状态值，最常见的是维护前缀上各个元素值的计数信息，参考文章