Tag: 数据结构

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

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

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

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

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

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

力扣206-反转链表

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

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

摘要: 带长度限制的最大子矩阵和 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 在文章 邻接表 中,我们学习了邻接表及其应用,在文章 用数组模拟双向循环链表 中,

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

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

用数组模拟双向循环链表

摘要: 用数组模拟双向循环链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的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,本文我

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

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

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

摘要: 加边过程中动态查询具体连通分量 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章并查集-加边过程中维护具体连通分量中我们了解了用并查集在加边过程中动态查询具体连通分量的原理。 本文我们看

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

摘要: 设计难题,验证系统 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个设计问题,第 48 场双周赛 B 题。本题的设计以哈希表为核心,类似的设计题汇总见文章 设计-功能系统。此外还

力扣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(E\log E)$ 邻接表 + 下标索引堆 Prim 下标索引堆 在下标索引堆模板的基础上的修改 $O(E\log V)$ 完整代码 $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. 滑动窗口最大值

字符串哈希

摘要: 本文系统梳理了字符串哈希相关的要点,并通过字符串精确匹配问题给出代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们系统串讲一下字符串哈希算法。字符串哈希是一种哈希函数

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

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