Archive: 2020/11

全O(1)的数据结构:哈希表计数,支持查询计数最大与最小的键

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

邻接表

摘要: 邻接表的应用:桶、开散列表、树和图的存储 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们总结一下邻接表的各种应用。包括桶、开散列表、树和图的存储。 $0 邻接表邻接表可以看成带有索引

高度数组:后缀数组中相邻两个后缀的最长公共前缀

摘要: 高度数组 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景高度数组是后缀数组中相邻两个后缀的最长公共前缀(LCP)。 1lcp[i] := s[sa[i]..n-1] 与

【DP难题】力扣1639-通过给定词典构造目标字符串的方案数

摘要: 一道推公式优化 DP 的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们看一个推公式优化 DP 的问题。本题是第 37 双周赛 D 题。关于推公式优化 DP 的更多例子,

链表维护多项式的加法

摘要: 链表维护多项式加法,力扣 1634 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 链表的一种应用是维护多项式,本文我们通过一个题目看一下如何用链表进行多项式的存储,以及两个多项式链表如何求和

用并查集中各集合的代表元建图,处理集合级信息

摘要: 只用并查集中各集合的代表元建图 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个并查集的高级应用,先用并查集将节点分类并维护集合级信息。然后只用集合的代表元建图,对集合级信

通过分类讨论拆目标函数中的绝对值

摘要: 力扣1330:分类讨论拆目标函数中的绝对值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在优化问题中,如果目标函数带有绝对值,处理起来是比较棘手的。有一些比较简单的情况,可以通过分类讨论的

曼哈顿距离

摘要: 曼哈顿距离相关的几道题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在上一篇文章 通过分类讨论拆目标函数中的绝对值 中,我们看了一个比较简单的目标函数带绝对值的优化问题,目标函数的形式是下

动态规划概念和基础线性DP

摘要: 动态规划的基本概念 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们系统学习一下动态规划中一些基本概念。这里我们参考《算法竞赛进阶指南》中关于动态规划的讲解,把动态规划的几个核心概念梳

深拷贝

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

尺取法(单串单向双指针)

摘要: 本文系统梳理了单串单向双指针的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 双指针 中,我们系统梳理了常见的双指针问题类型,包括单串单向、单串双向、双串单向、单串三指针等。

滑动窗口

摘要: 本文系统梳理定长滑动窗口相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 不定长滑动窗口不定长滑动窗口经常也称为尺取法,可以参考文章: 尺取法。 $1 定长滑动窗口 题

下标索引堆

摘要: 下标索引堆,思想,代码模板,例子 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景(1) 支持按 key 删除的堆一般的堆不支持按key操作,例如按 key 删除,

力扣828-统计子串中的唯一字符

摘要: 用前缀和维护前缀的某种状态 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【模板】前缀和与差分 中,我们串讲了前缀和的算法原理和代码模板、在 差分的应用 中,我们学习了用差分

力扣424-替换后的最长重复字符

摘要: 力扣 424,双指针+哈希表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们看一个双指针的问题,指针推进的过程中用哈希表维护窗口内的值。 $1 题目 424. 替换后的

【STL】bitset

摘要: 本文介绍在 C++ STL 中的 bitset 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 《C++标准库》 第2版,作者 Nicolai M. josuttis,侯捷 译 $12.5

双指针

摘要: 本文系统梳理了双指针的算法要点。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 单串单向维护 [l, r]维护 [l, r] 的题目可以参

实数值域二分

摘要: 实数值域二分经典题目 lc644 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二分 中,我们总结了二分的常见类型,其中主要是区间二分以及值域二分。 在文章 实数区间二分 中,我们学

堆的标记删除

摘要: 带标记删除的堆 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们借鉴 GC 中的标记删除算法,在堆的元素中加上标记删除,实现对堆中元素的动态删除。 我们给出代码模板,最后用 239.

【随机算法】黑名单映射

摘要: 黑名单映射在随机算法中的应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,最近我们密集地学习了常见的随机算法,并且解决了不少力扣中的问题。本文我们看两个力扣上的综

【随机算法】加权蓄水池抽样

摘要: 加权蓄水池抽样 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【随机算法】蒙特卡洛 中,我们了解了蒙特卡洛方法的基本思想,实现蒙特卡洛方法最重要的是根据需求

【随机算法】加权随机事件的二分查找

摘要: 加权随机事件二分的场景与解法 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【随机算法】蒙特卡洛 中,我们了解了蒙特卡洛方法的基本思想,实现蒙特卡洛方法最重

加索引的数组

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

线性索引表

摘要: 线性索引表的原理,例子 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 线性索引表将数组中数据的 key 和数据在数组中的节点位置以元组的形式放进数组维护,这个保存 key 和节点位置的

力扣480-滑动窗口中位数

摘要: 滑动窗口中位数:一题多解。对堆的各种改进。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个对于堆这种数据结构的非常经典的问题,480. 滑动窗口中位数,涉及到对堆的各种改进。

【设计难题】力扣642-设计搜索自动补全系统

摘要: 自动补全系统设计,基于 Trie 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 题目 642. 设计搜索自动补全系统 为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句(最少

对顶堆

摘要: 对顶堆的思想,在中位数问题中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二叉堆 中,我们详细学习了二叉堆的原理、代码模板,以及在排序中的应用。 对于一些中位数问题,我们可以

二叉堆

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