贪心算法, 快排序+堆排序

约瑟夫环问题

[模拟], [单链表]

(稀疏数组)
动作: 交换行列
问询: 值
技巧: 保存行行、列列映射, O(N)空间
链表+链表保存稀疏数据

堆, 堆排序, extract_max(), push(x), max_heapify()操作

实现一个优先级队列
操作: insert, delete min, get min
[最小堆]

实现一个优先级队列
操作: insert, decrease key, find x(大于x的最小的数字下标)
[最小堆]

集合
操作: union / difference / intersection
[Binary Search Tree(BST)]

Matrix Sum: 求奇子阵的总数

DFS求从某一顶点出发到长度为2的简单路径的数目

Kruskal 最小生成树算法

Dijkstra 单源最短路径算法

Bellman-Ford 单源最短路径算法

Topological Sort 拓扑排序

stack, Token
中缀表达式转前缀表达式，并计算前缀表达式的值

长度为N的数列 A[1..N] , 这N个数字恰好是1...N的一个排列, 这个序列的中值为B
求出这个序列有多少个(连续)子序列 A[i..j] 满足： i <= j  且  j-i+1  为奇数, 且中值为 B
O(N) 复杂度, 抽象大于中值的为+1, 小于中值的为-1，然后稍作统计即可

区间最大问题
Sliding Window with velocity = 1, print the maximal in the window range
[线段树]

求移除哪几个数后，使得最长连续相同数的序列长度最长
动态规划

[DFS]

struct Mouse
{
    int index;
    int points;
    int strength;
};
mergeSort() + bubbleSort()
mergeSort() 可以换成 qsort(), 注意 Cmp() 类的书写

归并排序的归并操作
merge A[0,..,mid], A[mid+1,...,rht]

括号栈：提供 全部 O(1) 的 push, pop, top, query(是否为合法括号栈)

队列, 队列的队列, 延迟哈希

统计堆排序, 归并排序, 快排的比较次数

问询：最小值位置
动作：单点自增自减

dfs, 邻接数组, 求连通分量的个数

旅行商问题-TSP
城市数目C<=5，暴力穷举，至多120种情况

迷宫
bfs, 注意细节

哈夫曼树, K叉, 计算最终的带权路径长度(WPL)
K-way HauffmanTree, heap

A[h+1, K] = A[h, 1]
A[h+1, k] = sum(A[h, K..K-k+1])
[大数加法]

给定一组数(果子), 每次合并两个数(两堆果子), 消耗的体力为两个数之和
求最小消耗的体力
[最小堆]

最长回文字符串

使用并查集
需要判断不同的连通分量
并计算每隔连通图内部的边数和节点数

搬箱子, 模拟, 数组实现双向链表, 计算双向链表的头尾

求一棵树中到三个节点距离之和最短的节点
将其视为寻找公共祖先的问题

给定 A[1..N], B[1..N], 求两数列的N^2种和中最小的前N项
[快排+堆]
对 A, B 快排排序, 对相加的和采用最小优先队列, pop最小者, push最小者对应的索引附近的数

0, 1数组
操作: 将区间[l, r]全部变为x
查询: 区间[l, r]中1的数目或者问询最长的连续的1的数目
[线段树]

二分搜索，滑动窗口 O(N log L)

[排序][贪心]

通过dfs遍历全树并记录每个节点所对应的子树的规模

字符串哈希
给定字符串S1...SN, 随机问询如下三个问题
1 x : Sx 是否在 S1...Sx-1中出现, O(1)
2 x y: 询问 Sx, Sy 的最长公共前缀长度, O(log L)
3 x y: 询问 Sx, Sy 的最长公共后缀长度, O(log L)

找到所有这样的节点，满足断开该节点后，子树规模的最大值不超过N/2

问询区间[1..2k+1]的第k大值(即中位数)
划分树, 快排

最小数栈：提供O(1)时间复杂度的push，pop，top，getMin操作

Rotate an array to the right by a given number
of steps.

Find the earliest time when a frog can jump
to the other side of a river.

Calculate the values of counters after applying
all alternating operations: increase counter
by 1; set value of all counters to current
maximum.

Compute number of integers divisible by k
in range [a..b].

Find the minimal nucleotide from a range
of sequence DNA.

Find the minimal average of any slice containing
at least two elements.

Count the number of passing cars on the road.

Compute number of distinct values in an array.

Compute the number of intersections in a
sequence of discs.

Determine whether a triangle can be built
from a given set of edges.

N voracious fish are moving along a river.
Calculate how many fish are alive.

Determine whether a given string of parentheses
(single type) is properly nested.

Cover "Manhattan skyline" using the minimum
number of rectangles.

Find an index of an array such that its value
occurs at more than half of indices in the
array.

Find the index S such that the leaders of
the sequences A[0], A[1], ..., A[S] and A[S
+ 1], A[S + 2], ..., A[N - 1] are the same.

Find the maximal sum of any double slice.

Count factors of given number n.

Find the maximum number of flags that can
be set on mountain peaks.

Find the minimal perimeter of any rectangle
whose area equals N.

Divide an array into the maximum number of
same-sized blocks, each of which should contain
an index P such that A[P - 1] < A[P] > A[P
+ 1].

Calculate the number of elements of an array
that are not divisors of each element.

Count the semiprime numbers in the given
range [a..b]

There are N chocolates in a circle. Count
the number of chocolates you will eat.

Check whether two numbers have the same prime
divisors.

Count the minimum number of jumps required
for a frog to get to the other side of a
river.

Count the number of different ways of climbing
to the top of a ladder.

Divide array A into K blocks and minimize
the largest sum of any block.

Count the minimum number of nails that allow
a series of planks to be nailed.

Compute number of distinct absolute values
of sorted array elements.

Count the number of distinct slices (containing
only unique numbers).

Count the number of triangles that can be
built from a given set of edges.

Find the minimal absolute value of a sum
of two elements.

Find a maximal set of non-overlapping segments.

Tie adjacent ropes to achieve the maximum
number of ropes of length >= K.

Given array of integers, find the lowest
absolute sum of elements.

In a given array, find the subset of maximal
sum in which the distance between consecutive
elements is at most 6.