Tag: 数据结构

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

摘要: 带长度限制的最大子矩阵和 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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++ 的“标

字符串哈希的哈希函数

在文章 字符串哈希 中,我们探讨了字符串哈希,及其在字符串相关的经典问题中的应用。 字符串哈希是哈希中最常见的形式,在搜索引擎创建索引的时候大量的计算消耗在哈希生成和查找上面,因此选择一个又快又好的哈希函数对性能提升至关重要。 本文记录几种字符串哈希中常用的哈希函数,这些哈希函数都是网上零散文章中摘录的,有一些在 大数据应用中的概率算法与数据结构 中有提到,有一些在 Redis 等框架中有用到。

【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 在文章 面试好题连载 中,我们提到了适合作为面试题的几个标准大致如下: 对于

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

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

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

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

用数组模拟双向循环链表

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

大学数据结构笔记

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

leetcode题目汇总-栈

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

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

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

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

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

Python标准库-数据结构

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

力扣962-最大宽度坡

算法要点: 单调栈 相关题目 力扣1124-表现良好的最长时间段 $1 题目题目链接 962. 最大宽度坡 题目描述给定一个整数数组 A,坡是元组 (i, j),其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。 找出 A 中的坡的最大宽度,如果不存在,返回 0 。 123提示:2 <= A.length <=

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

算法要点 前缀和 单调栈 相关题目 力扣962-最大宽度坡 $1 题目题目链接1124. 表现良好的最长时间段 题目描述给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」,意味在这段时间内,「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时

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

问题背景并查集回炉 基础并查集功能和题目列表: 并查集 带权并查集功能和题目列表: 带权并查集 并查集维护平面点的横纵坐标 并查集时光倒流 对于用[带权]并查集解决加边连通性的问题,我们之前处理过以下几类问题: 加边过程中动态地处理【两个点 x, y 是否连通】的查询问题 加边过程中动态地处理【某个点 x 对应的连通分量的大小】的查询问题 加边过程中动态地处理【当前连通分量的个数】的查询问题

力扣1722-执行交换操作后的最小汉明距离

算法要点: 并查集: 加边之后返回所有连通分量 并查集 并查集-加边过程中维护具体连通分量 求两个数组的交集 【STL】有序容器的集合操作 $1 题目题目链接1722. 执行交换操作后的最小汉明距离 题目描述给你两个整数数组 source 和 target ,长度都是 n 。还有一个数组 allowedSwaps ,其中每个 allowedSwaps[i] = [ai, bi] 表示

【设计难题】力扣1797-设计一个验证系统

第 48 双周赛 B 题 算法要点 设计 设计-功能系统 数据结构 【模板】无重哈希映射 【模板】双向链表 $1 题目题目链接 1797. 设计一个验证系统 题目描述你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了,那么它会在 currentTime (可能与

力扣1793-好子数组的最大分数

第 232 周赛 D 题 算法要点 单调栈 参考: 单调栈, 单调栈题目汇总 $1 题目题目描述给你一个整数数组 nums (下标从 0 开始)和一个整数 k 。 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

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

相关算法参考 二叉查找树的中序遍历和前驱后继 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 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法,都非常主流,并且

分桶法

摘要: 本文总结了 leetcode 上的分桶法相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于分桶的 14 道题。将场景相同的放到了一起,场景上主

力扣548-将数组分割成和相等的子数组

相关的算法或数据结构 哈希表 前缀和: 【模板】前缀和与差分 $1 题目题目链接 548. 将数组分割成和相等的子数组 题目描述给定一个有 n 个整数的数组,你需要找到满足以下条件的三元组 (i, j, k) : 0 < i, i + 1 < j, j + 1 < k < n - 1子数组 (0, i - 1),(i + 1, j - 1),(j + 1, k -

二叉树的建树

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

【多维分桶】力扣939,963-最小面积矩形

用坐标值对点做哈希,用哈希值 用中点和长度对点对(线段,圆)做哈希,用哈希值分桶 多层 treemap 对点对做多属性分桶 STL无序关联容器自定义哈希函数 939. 最小面积矩形题目描述给定在 xy 平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形,就返回 0。 提示:12341 <= points.length

力扣1409-查询带键的排列

第 184 场周赛 B 题 树状数组 $1 题目题目链接1409. 查询带键的排列 题目描述给你一个待查数组 queries ,数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i](从 i=0 到 i=queries.length-1): 一开始,排列 P=[1,2,3,…,m]。对于当前的 i ,请你找出待查项 queries[i] 在排列 P

【频数分桶】力扣1224-最大相等频率

将 key 按频数分桶 维护频数桶的数据结构 链表, 动态数组 Ref1: 全(1)的数据结构 Ref2: LFUCache $1 题目题目链接1224. 最大相等频率 题目描述给出一个正整数数组 nums,请你帮忙从该数组中找出能满足下面要求的 最长 前缀,并返回其长度: 从前缀中 删除一个 元素后,使得所剩下的每个数字的出现次数相同。如果删除这个元素后没有剩余元素存在,仍可认为每个数

力扣768-最多能完成排序的块2

摘要: 双指针+哈希表、单调栈两种解法的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个一题多解的问题:力扣 768。第一种解法是单调栈,不过此前我们解决过的单调栈的问题,栈里保

【模板】双向链表+哈希映射,有序字典,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):

下标索引堆优化Prim

1135. 最低成本联通所有城市 邻接表 + 二叉堆 Prim 最小生成树 $O(ElogE)$ 邻接表 + 下标索引堆 Prim 下标索引堆 在下标索引堆模板的基础上的修改 $O(ElogV)$ 完整代码 $0 1135. 最低成本联通所有城市$1 邻接表 Prim 参考: 最小生成树 123456将 0 加入集合 Twhile 尚有点没有进入集合 T 从剩下的点中,选出最

【模板】哈希集合

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

哈希索引堆的索引优化

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

字符串哈希

摘要: 本文系统梳理了字符串哈希相关的要点。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们系统串讲一下字符串哈希算法。首先介绍两个常用的

【设计难题】力扣432-全O(1)的数据结构

摘要: 基于链表+哈希表解决与频数相关的设计问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个设计问题。在文章 设计-功能系统 中我们系统梳理过设计功能系统的问题。本文解决

邻接表

桶 开散列表 图和树存储 邻接表 链式前向星 $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 和进程优先级在一个堆中