Category: 算法

二叉查找树的中序遍历和前驱后继

摘要: BST 的中序遍历,前驱和后继 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 中序遍历题目清单 98. 验证二叉搜索树 99. 恢复二叉搜索树 230. 二叉搜索树中第K小的元素 2

货仓选址与安排邮筒

摘要: 安排邮筒问题,使用动态规划解决 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天看一个非常经典的动态规划的问题,本题是第 28 双周赛 D 题,安排邮筒。 安排邮筒说的是

差分维护区间加法

摘要: 本文通过详细拆解 leetcode 370 来理解差分的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 【模板】前缀和与差分 中,我们串讲了前缀和的算法原理和代码模板,并

力扣1476-子矩形查询

摘要: 惰性更新与延迟计算的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在很多数据结构中,对节点更新的时间复杂度是比 $O(1)$ 要大的。当修改非常频繁,但是查询相对稀少的时候,可以将

带边权的并查集

摘要: 带边权并查集的原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 并查集 中我们学习了并查集的原理和代码模板,本文介绍带边权并查集。 我们知道并查集的结构是一个森林,其中的

并查集

摘要: 并查集的原理与代码模板 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍并查集的原理和代码模板,最后针对并查集可以解决的几类问题,列出了一些题目列表。 $1 并查集并查集是一种可以动

异构图建图

摘要: 两种类型的点和边的异构图建图 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们知道图论的算法相对比较固定,变化的地方不多,难点在于怎样从实际问题转换为图,图中的节点、边在原问题中是什么含义

拓扑排序

摘要: 拓扑排序原理、代码模板、题目列表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumFloyd算法的原理与代码模板plings 本文我们学习拓扑排序的原理、给出代码模板和题目列表,然后解决力扣 210. 拓

多进程DP:一个阶段控制两个独立的附加信息

摘要: 多进程 DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 当明确了动态规划的阶段要素后,经常会发现发现阶段不足以表示状态,需要增加额外信息作为状态的维度,例如 阶段不足表示状态:附加信息作

带权图最短路径的变种问题

摘要: 带权图最短路径的变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 带权图最短路径算法与实现 中我们以力扣 743 作为模板题,全面梳理了带权图最短路径的各种算法与实现。 本文

带压缩的额外状态的 BFS

摘要: 带压缩的额外状态的 BFS 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较难的 BFS 的问题。说的是我们在二维矩阵上走迷宫,其中除了常规的道路和墙,还有

惰性更新

摘要: 惰性更新的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 惰性更新是一种常见的思想,简单理解就是将更新操作存下来,但是不实际执行更新,而当查询的内容需要更新后的结果的时候,才执行更新

力扣164-最大间距

摘要: 桶排序的经典问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 非比较排序 中,我们学习了计数排序、桶排序、基数排序的原理、代码模板、题目,本文我们看一个稍微难点的问题,但很经典,

三色排序

摘要: 计数排序的特例:三色排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过一个模板题看一下三色排序问题。有计数排序和双指针两种方法。之后我们解决力扣 324 摆动排序2,其

非比较排序

摘要: 计数排序、桶排序、基数排序 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 计数排序当数据范围较小,例如十万级,可以通过一个计数数组统计各个数字出现的次数,然后在按照出现的数字和次数从小

DP问题分类汇总-加强版

摘要: 文章《dp问题分类汇总》的加强版 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings dp问题分类汇总 的加强版,《动态规划精讲》 系列的目录结构的主要参考。题目主要是 2000 以内的。 1、

比较简单的两种字符串的编码与解码

摘要: 字符串的编码解码,分隔符、分块编码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 哈夫曼树与哈夫曼编码 和 k叉哈夫曼树 中,我们学习了 2 叉和 k 叉哈夫曼树和哈夫曼编码,并用于

股票系列问题-高维动态规划视角

摘要: 本文介绍股票系列问题,主线算法是动态规划 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍股票问题这个系列问题,一共六道题。有动态规划和自动机两种思考方式。本文我们串讲一下这六道题,并

设计-基础数据结构

摘要: 力扣上的基础数据结构设计的题目分类汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 实现哈希表 705. 设计哈希集合 706. 设计哈希映射 实现字典树 208. 实现 Tr

设计-功能系统

摘要: 力扣上的设计功能系统的题目分类汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于设计功能系统的 38 道题。将核心数据结构相同的放到了一起。刷完这份

LRU:维护最近访问/插入的元素

摘要: LRU 的原理、实现与应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们详细介绍 LRU 的思想,以 146. LRU缓存机制 为模板题实现 LRU 的插入和查询,形成代码模板。

模拟-元胞自动机

摘要: 本文介绍元胞自动机,并解决三个力扣上的问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 元胞自动机是一类模拟中常见的算法,应用非常多,在力扣上也有一些相关的问题。本文我们就简单了解一下元

设计-迭代器模式

摘要: 迭代器模式,题目清单,典型题解 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们简要介绍一下常用的设计模式:迭代器模式。列出了一些与迭代器相关的题目清单。最后解决两个比较典型的问题。

稀疏相似度:倒排索引

摘要: 倒排索引简介及其在稀疏相似度中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单词-文档矩阵单词—文档矩阵是表达两者之间所具有的一种包含关系的概念模型,每列代表一个文档,每行代表一个单

位运算操作

摘要: 常见的位运算操作 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在编程中,经常会使用一些位运算操作,比如用位运算来实现集合的操作。本文我们总结一下常见的位运算操作,首先介绍基础的位运算的运算

力扣239-滑动窗口最大值

摘要: 非常经典的题目:滑动窗口最大值,有单调队列、平衡树、堆等解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个经典题,滑动窗口最大值。主流方法有两类,一类是基于单调队列的方法,

异或的性质,数字出现次数问题

摘要: 利用异或的性质,解决数组中数字出现次数的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 异或的性质 交换律: $p \oplus q = q \oplus p$ 结合律: $p \opl

力扣456-132模式

摘要: 用单调栈解决 132 模式问题,132 模式可以作为组件解决其他问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 面试好题 中,我提到了我认为的适合作为面试题的标准,这里复习一下

词法分析:有限自动机

摘要: 有限自动机的原理与实现,若干例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们简要串讲一下词法分析中的有限自动机理论,然后解决力扣上的 4 道相关题目: 65. 有效数字

手撕平衡树-二叉查找树BST

摘要: 二叉查找树(BST)的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 二叉查找树定义二叉查找树(Binary Search Tree)是指一棵空树

手撕平衡树-大小平衡树SBT

摘要: 大小平衡树的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们知道二叉查找树在多次插入删除之后会变得不平衡,使得树的深度逐渐大于 $O(\log N)$,使得查询的效率变低。如果

计算的本质:深入剖析程序和计算机

摘要: 《计算的理论》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最近在 Leetcode 见到两类题目,一个是跟语法分析相关的,例如解析括号,解析表达式,等等各种解析,主要涉

树状数组:单点修改,区间最值查询

摘要: 线段树和树状数组,单点修改与区间查询,原理与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 考虑以下需求:给定一个数组 a,支持区间和的查询, 其中 a 中的元素可变,每次变化 a 中的

数位DP

摘要: 数位 DP 的算法原理,题目列表以及题解 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 数位 DP 在基础的动态规划问题当中算是比较难的一类,因为数位 DP 的状态的物理意义不太好理解。其它

单调栈题目汇总

摘要: 单调栈的题目汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单调栈基本思想和模板单调栈的算法原理和代码模板看这篇文章:单调栈。 单调栈的题目以下是单调栈的题目列表,思路类似,可以集

单调栈:两侧距离最近的更大元素

摘要: 单调栈的算法原理,代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以力扣 84. 柱状图中最大的矩形 为模板题,串讲一下单调栈的思路和代码。在文章 单调栈题目汇总 中列

topK问题:第K个最大元素

摘要: TopK 问题的几种主流解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个大家都研究的很透的问题,数组中的第 K 个最大元素。这种 TopK 问题有 3 种主流解法: 用堆

众数,摩尔投票

摘要: 求众数的算法,摩尔投票 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文以 169. 多数元素 和 229. 求众数 II 来看一下求众数的算法。其中我们重点看一下摩尔投票算法。 求众数问

二维线段树:单点修改,矩阵和查询

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

区间问题汇总

摘要: 本文总结了 leetcode 上的区间问题相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 力扣上 2000 以内的区间类的题一共 41 道题,按解决方案和问题模型分类。区间类的题有

树上倍增

摘要: 树上倍增算法及其在最近公共祖先问题上的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 树的直径 中我们学习了树的直径的算法,这是树上的一个基础问题,很多问题都可以拆解成树的直径问

权值线段树、权值树状数组:元素排名区间的权值(个数)和

摘要: 元素的计数,权值线段树、权值树状数组 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 线段树和树状数组:单点修改、区间和查询 中,我们知道线段树和树状数组可以处理元素

带权图最短路径算法与实现

摘要: 带权图单源最短路 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以力扣 743 为模板题来看一下带权图的单源最短路问题的各种算法的原理以及实现。涉及到以下算法: dkijstra

线段树和树状数组:单点修改、区间和查询

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

区间合并问题

摘要: 本文我们以力扣 56 来看一下区间合并问题的各种解法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们系统串讲一下区间合并问题。这个问题有很多解法,每个解法都是主流经典算法。同时区间也

字符串精确匹配

摘要: 字符串精确匹配方法汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以 leetcode 第 28 题为模板题,总结一下字符串精确匹配的各种算法。 28. 实现 strStr()给

Trie

摘要: 经典的 Trie 的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以力扣 208 作为模板题来学习一下 Trie 的建树,插入和查找。并形成代码模板。 模板题

括号问题汇总

摘要: 总结括号相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 有效括号有效括号的条件: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 有效括号的递归定义: 空

语法分析问题分类汇总

摘要: 语法分析题目汇总 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于语法解析问题的 32 道题。将场景相同的放到了一起,场景上主要涉及嵌

链表问题汇总

摘要: 总结链表题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 链表节点操作 61. 旋转链表 86. 分隔链表 21. 合并两个有序链表 23. 合并K个升序链表 109. 有序链表转