Tag: 数据结构

极值栈与极值队列

摘要: 极值栈,极值队列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 极值栈是指除了维护栈的基本功能之外,还需要随时查询栈中的最值。它的设计思想是用两个栈来维护,其中一个栈维护数据的插入删除,另一

双单调栈:两侧距离第二近的更大元素

摘要: 双单调栈 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单调栈是一种在数组上摊销 $O(1)$ 地解决以下问题的数据结构:对于 $nums[i]$,求两侧距离最近的大于 $nums[i]$

Python queue 和 deque 的用法

摘要: Python 双端队列操作 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过用 Python 实现 极值栈与极值队列 中的 MaxQueue,来看一下 collections 模块中

heapq的用法

摘要: Python 堆操作 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍 Python 中与堆相关的组件:heapq 模块。首先介绍建堆、插入、查询极值、删除极值、合并有序序列等操作。之

力扣1670-设计前中后队列

摘要: 基于链表的设计 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个基础数据结构的设计问题。难点在于增删的时候如何维护指向链表中间节点的指针。细节处理非常繁琐,不容易过。 题目请你设计一

在数据结构中维护前缀和:区间(矩形/路径)和等于(大于)目标值

摘要: 区间和等于目标值的各种变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】前缀和与差分 中我们了解了一维和二维前缀和的算法原理和代码模板。在实际问题中我们经常要将前缀和维

设计内存文件系统:在Trie中用TreeMap维护子节点

摘要: TreeMap 维护子节点的 Trie 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 Trie 中,一般用数组或哈希表维护子节点,本文我们看一个用TreeMap维护子节点的例子。 题

二维偏序问题:扫描线+树状数组

摘要: 一个维度用扫描线(排序)保证有序;一个维度用树状数组保证有序;维护权值的最值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 二维偏序问题形式化定义如果形式化地定义,二维偏序问题的描述如下。

二维的滑动窗口最大值

摘要: 滑动矩形窗口最大值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 滑动窗口最大值问题是单调队列的最典型使用场景,单调队列也是定长滑动窗口问题的最优解法,时间复杂度为 $O(N)$,参考文章

离线分治:基于时间 (CDQ分治)

摘要: 基于时间的离线分治,逆序对个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 很多数据结构的问题可以抽象为“维护一系列数据,并对一系列操作一次做出响应”,这些操作可以分为两种: 查询型操作

树状数组优化DP

摘要: 权值树状数组优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 最长上升子序列LIS 我们通过动态规划解决了最长上升子序列问题,其状态转移方程如下: dp[i] = 1 + \m

归并树:区间大于x的元素个数

摘要: 归并树,区间大于 x 的元素个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 315. 计算右侧小于当前元素的个数 出发,引出一个维护区间大于 x 的元素个数的数据结构:归并树

划分树:区间第k大

摘要: 划分树,区间第 k 大数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 力扣315-索引数组,归并树 出发,引出一个维护区间第 k 大数的数据结构:划分树。 对于区间 $[i,

分块查找表:区间修改,区间最值查询

摘要: 分块查找表,原理与实现,解决带修改的区间最值查询问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分块查找表的主要思路是对于数据数组 nums[0..n-1], 共 n 个元素,每 $\s

Range模块:维护区间的增删改查

摘要: 基于平衡树的Range模块,维护区间的增删改查 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过力扣 715 来看一下可以动态维护区间的增删改查的组件的功能与实现,本题的代码可以作

前驱后继与线索二叉树

摘要: 线索树 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对树进行遍历的过程中,会产生一个遍历序,参考文章 遍历序的基本概念与性质。基于这个遍历序,每个节点都有一个前驱节点与后继节点。 在实际问

字符串哈希-字符串同构问题

摘要: 字符串同构问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 数据结构的同构问题是哈希表解决的一个基本问题,在给定数据结构的同构规则后,如何快速判断两个数据结构是否同构。 对于这种判定同构的

用字符串哈希解决经典问题:最长重复子串、最长公共子串

摘要: 可以用字符串哈希解决的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决,比

参考字符串哈希定义数组哈希(数组的同构)

摘要: 类似于字符串哈希的数组哈希,以及在数组同构中的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中我们学习了字符串哈希的原理与代码模板。 对于长度为 m 的字符串 s

力扣206-反转链表

摘要: 面试最爱问的反转链表,迭代和递归 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一下面试当中非常爱问的反转链表,当你去面试别人不知道问什么题的时候,就问

Morris遍历与Morris序

摘要: 树的 Morris 遍历 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 树的前序、中序、后序遍历与DFS搜索 中,我们知道树的前序、中序和后序遍历都有递归和非递归算法。两者的额外空间

用哈希表和和双向链表的代码模板实现LFU

摘要: 实现 LFU 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 LRU:维护最近访问/插入的元素 中,我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU

用哈希表和和双向链表的代码模板实现LRU

摘要: 实现LRU 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 LRU:维护最近访问/插入的元素 中,我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU

二维树状数组:单点修改,矩阵和查询

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

带长度限制的最大子数组和

摘要: 带长度限制的最大子矩阵和 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法,都非常主流,并且

【树形DP】力扣968-监控二叉树

摘要: 力扣 968, 状态比较复杂的树形 DP 题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【树形DP】树的直径 中,我们学习了树形 DP 的经典题目:树的直径,理

Java核心技术1-算法

摘要: 本文是《Java核心技术 10th》中关于泛型算法的要点总结。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 泛型算法基础泛型集合接口有一个很大的优点:算法只需要实现一次。 例如:求集合中最

Java自定义哈希函数

摘要: 本文介绍在 Java 中,使用自定义对象作为哈希映射容器的元素时,如何提供哈希函数和比较函数。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【STL】无序关联容器自定义哈希函数 和

Java核心技术1-映射

摘要: 本文是《Java核心技术 10th》中关于映射的要点总结。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 映射基本映射操作Java 类库为映射提供了两个通用的实现:HashMap 和 Tre

Java核心技术1-集合

摘要: 本文是《Java核心技术 10th》中关于集合的要点总结。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Java 集合框架设计人员希望让集合类库规模小且易于学习,而不希望像 C++ 的“标

字符串哈希的哈希函数

摘要: 字符串哈希的哈希函数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们探讨了字符串哈希,及其在字符串相关的经典问题中的应用。 字符串哈希是哈希中最常见的形式,在搜索

【leetbook】树的技巧

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

【leetbook】哈希的技巧

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

算法导论第四版

摘要: 算法导论第四版介绍 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍一下算法导论第四版。本书的第四版是去年出来的,新增了机器学习算法等内容,还是有不少更新的。本书完整下载链接如下

二分/手撕平衡树/分治/stable_sort

摘要: 综合题:二分、平衡树、分治、stable_sort 四种解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个排序的变种问题。跟排序一样,本题的解法也非常多,并且每个算法都是主流

手撕平衡树-Treap

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

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

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

力扣2104-子数组的范围和

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 面试好题连载 中,我们提到了适合作为面试题的几个标准大致如下: 对于

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

摘要: 数组模拟链表的方式实现图的邻接表,代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 邻接表 中,我们学习了邻接表及其应用,在文章 用数组模拟双向循环链表 中,

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

摘要: 链表易于删除节点,方便维护逆向思维 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 逆向思维是一种常见的算法思维方式,在文章 逆向思维 中,我们例举了不少 leetcode 上用逆向思维解决的

用数组模拟双向循环链表

摘要: 用数组模拟双向循环链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】双向链表 中,我们实现了双向循环链表,并将其用在实现了 LFU,以及实现循环双端队列中

大学数据结构笔记

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

leetcode题目汇总-栈

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

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

摘要: 两本高级数据结构书 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文给大家分想两本高级数据结构的书。LeetCode 主要是针对面试的算法刷题平台,在 LeetCode

大数据应用中的概率算法与数据结构

摘要: 介绍一本概率算法与数据结构的书 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最近系统复习了一下概率的东西,主要是因为【概率面试题连载】里面遇到某些题吃瘪了,在查资料的时候

Python标准库-数据结构

摘要: Python 标准库中关于数据结构的组件。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Python 中有几个作为内置类型的标准的数据结构:list, tuple, dict, set,除

力扣962-最大宽度坡

摘要: 本文是力扣 962 的题解,单调栈的基础应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们看一个单调栈的问题,力扣 962。本题解决之后,可以作为组件,直接解决力扣 11

力扣1124-表现良好的最长时间段

摘要: 本文是力扣 1124 的题解,力扣 962 的进阶问题,单调栈的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 力扣962-最大宽度坡 中我们解决了力扣 962,本文我

力扣1707-与数组中元素的最大异或值

摘要: 用 01Trie 处理 01 串的统计问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个 01Trie 的应用的问题,统计 01 串上的某些信息。比经典 01Trie 在节点

并查集-加边过程中维护具体连通分量

摘要: 并查集在加边过程中维护具体连通分量 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 问题背景对于用含集合级信息并查集解决加边连通性的问题,我们之前处理过以下几类问题: 加边过程中动态地处理【