Meeting Room I, II

相关题目: Meeting Rooms Meeting Rooms II Meeting Rooms 简单题, 但是可以作为 sort 的使用范例. template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare »

Cycle Detection

判断是否成环, 主要有两个算法: Floyd's algorithm Brent's algorithm Given sequence $x_0, x_1, ...$, 有 $x_{i + 1} = f(x_i)$. 如果存在 $\mu$, $\lambda$ 使 sequence 满足 $x_ »

Largest Rectangle in Histogram

Largest Rectangle in Histogram | LeetCode OJ 在 Historgram 中寻找 largest rectangle 有三种思路: Brute force 方法, 遍历所有可能的 (l, r), 在 inner loop 中更新一个 min height 的变量. 复杂度是 »

Trapping Rain Water I, II

Trapping Rain Water | LeetCode OJ Trapping Rain Water II | LeetCode OJ 这两题很有意思。其实本质上就是从边界的「最短木板」出发,然后追踪每个 cell 的 maxmin 边界,然后就可以得到 cell 周围(上下左右)的 cells »

Single Number 系列

这个系列的题目主要是考位 Bit Manipulation, 不过感觉十分 tricky. Single Number: every element appears twice except for one. Single Number II: every element appears three times except for one. Single »

Suffix Automaton Tutorial

Preface 目前中英文站点上并没有很好的 Suffix Automaton (后缀自动机, 简称 SAM ) 教程. 比较知名的材料有两个, 一是陈立杰的 营员交流资料 , 二是某俄国人的某 SAM 博文, 但这两个材料都不好懂. 在下反复啃了几天后, 略有所得, 在此记录一下. Introduction 较为靠谱的 SAM 资料: A short guide to »