Archive: 2020/10

后缀数组:排名为i的后缀的起始下标

摘要: 后缀数组原理与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 背景一个长度为 n 的字符串 s,共有 n 种后缀。现在想对这 n 个后缀排序,将排序结果保存在一个数组 sa 中。sa[i

跳表

摘要: 跳表的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 跳表背景与哈希表、平衡树、Trie类似,跳表也可以看成是一种自带索引的数据结构(索引结构)。即根据给定的 key,可以快

在模拟过程中找出循环节

摘要: 循环节优化模拟;倍增优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在模拟的过程中,如果出现了循环节,就可以直接跳过很多中间的模拟步骤。有时这种循环节是现成已知的,例如文章 通过已知

多重背包及其二进制划分优化

摘要: 多重背包 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 多重背包问题描述有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解

DAG上的DP (拓扑序DP),无权 DAG 的最长路径

摘要: 拓扑序DP解无权DAG上的最长路径问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于一个 DAG,我们可以进行拓扑排序,一些动态规划的问题,其阶段的推导过程呈现为一个 DAG,形成了图

【搜索难题】力扣956-最高的广告牌

摘要: 非常综合的搜索题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个综合性很强的搜索问题,会遇到搜索中的多种优化方法,首先比较关键的是找到剪枝方法,本题最终通过适当维护变量进行可行

倍增优化DP

摘要: 倍增优化DP,减少状态个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 倍增法 中我们了解了倍增法的原理与实现。本文我们以力扣 466 来看一下倍增优化 DP,最后我们解决一个非常

最小生成树2

摘要: 最小生成树的一些衍生问题,比较难。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最小生成树方案数 题目: P4208 最小生成树计数算法: Kruskal题解参考: 力扣1489-找

DAG典型应用-活动网络

摘要: AOV、AOE 两种活动网络。关键路径算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 活动网络活动网络(activity network)是一种 DAG,可以用来描述生产计划、施工

有向图的必经点,支配树

摘要: 有向图的必经点,支配树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个从业务场景中抽象出来的图论的问题:有向图的必经点。给定有向图上的两个点 S 和 T,从

最近公共祖先问题

摘要: 最近公共祖先问题的三种解法,以及一些应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 树上倍增 中,我们学习了树上倍增的思想。树上倍增主要解决从某个节点向上找第

线段树:区间修改(更改为定值)、区间最值查询

摘要: 线段树,区间修改与区间查询,原理与实现,RMQ 问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 线段树和树状数组:单点修改、区间查询,区间求和问题 中,我们学习了带单点修改、区间

稀疏表(倍增优化DP):区间最值问题

摘要: 元素不变的区间最值问题,稀疏表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 给定一个数组,其中的元素可以修改,要查询数组中某个区间的和。过程中需要维护元素修改的操作,并且要高效查询区间的和

倍增法

摘要: 倍增法原理、代码模板、例题与应用场景 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 倍增法算法思想在递推状态的时候,只递推状态空间中 2 的幂次,当需要求其它位置的时候,利用以下性质,

增删改后的最大子数组和

摘要: 本文介绍最大子数组和的一类变种:可以增删改的情况 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三

【贪心难题】力扣1505-最多K次交换相邻数位后得到的最小整数

摘要: 贪心+树状数组 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个贪心的问题,这是第 196 场周赛 D 题。亮点是在执行贪心策略时需要一些预处理信息,这些预处理信息是通过树状数组

线性探测解决哈希冲突

摘要: 线性探测法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 哈希表在发生冲突时,有开散列法和闭散列法两种主流的处理方法。线性探测法是闭散列法中比较简单的一种。本文我们通过力扣 945,来看一

自定义排序题目清单:定义 Cmp 结构体并重载 () 运算符

摘要: 题目汇总,自定义元素的比较方法,定义 Cmp 结构体病重载 (),比较逻辑中可能含复杂的判断逻辑,Cmp 的实例可能持有额外状态。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 C++

【堆贪心】力扣1642-可以到达的最远建筑

摘要: 一个堆贪心的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 题目 1642. 可以到达的最远建筑 给你一个整数数组 heights ,表示建筑物的高度。另有一些砖块 bricks 和梯