Archive: 2020/11

2020
算法数据结构

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

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

算法数据结构

邻接表

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

算法字符串

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

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

算法leetcode

【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 本文我们系统学习一下动态规划中一些基本概念。这里我们参考《算法竞赛进阶指南》中关于动态规划的讲解，把动态规划的几个核心概念梳

算法数据结构

几个实现深拷贝的题目，包括使用或自定义 deepcopy 的方法

摘要: 几个深拷贝的问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们看4个题，leetcode第1490题【1490. 克隆 N 叉树】，第133题【133. 克隆图】，第138题【13

算法基础算法

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

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

算法基础算法

滑动窗口

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

算法数据结构

下标索引堆：key 是大对象时，如何实现可对给定 key 删改的堆

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

算法leetcode

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

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

算法leetcode

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

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

编程C++

【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 在文章 二分 中，我们总结了二分的常见类型，其中主要是区间二分以及值域二分。 在文章 实数区间二分 中，我们学

算法数据结构

堆的标记删除：简单实现对给定 key 的删除操作

摘要: 带标记删除的堆 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 和节点位置的

算法leetcode

力扣480-滑动窗口中位数

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

算法leetcode

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

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

算法数据结构

对顶堆

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

算法数据结构

二叉堆

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