排序

散列

递归

汉诺塔

点击展开题目 汉诺塔

汉诺塔(又称河内塔)问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象成模型就是说：

有三根相邻的柱子，标号分别为$A$、$B$、$C$，$A$柱子按金字塔状叠放着$n$个不同大小的圆盘，现在要把所有盘子一个一个移动到柱子$C$上，并且任何时候同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并给出具体的移动方案。

输入描述： 一个正整数$n$($1\le n\le 16$)，表示圆盘的个数。

输出描述： 第一行输出一个整数，表示至少需要的移动次数。

接下来每行输出一次移动，格式为X->Y，表示从柱子$X$移动最上方的圆盘到柱子$Y$最上方。

输入样本：

1

样本输出：

1
A->C

代码长度限制[待补充] KB | 时间限制[待补充] ms | 内存限制[待补充] MB | 栈限制[待补充] KB

思路 该问题运用递归思想求解。 将$n$个盘子从$A$柱移到$C$柱，可拆解为三个步骤： 先把上面$n - 1$个小盘从$A$移到$B$，这需要$S_{n - 1}$次； 接着把最底下最大的$1$个盘子从$A$移到$C$，需$1$次； 最后把$n - 1$个小盘从$B$移到$C$，又需$S_{n - 1}$次。 由此得到总步数公式$S_n = 2\cdot S_{n - 1}+1$，初始条件$S_1 = 1$，进而推出通项公式$S_n = 2^n - 1$。在具体移动过程中，大盘的移动操作必须夹在两次小盘搬运中间，以保证符合规则。

C++

#include <bits/stdc++.h>
using namespace std;
int n;
void f(int n, char from, char to, char mid)
{
    if(n == 0) return;
    else
    {
        f(n - 1, from, mid, to);
        printf("%c->%c\n", from, to);
        f(n - 1, mid, to, from);
    }
}

int main()
{
    cin >> n;
    cout << pow(2, n) - 1 << "\n";
    f(n, 'A', 'C', 'B');
    return 0;
}

Java

[待补充]

Python

[待补充]

贪心

二分

two pointers

其他高效技巧与算法

并查集 (Disjoint-Set)

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．

顾名思义，并查集支持两种操作：

合并（Unite）：合并两个元素所属集合（合并对应的树）． 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合． 并查集在经过修改后可以支持单个元素的删除、移动或维护树上的边权．使用动态开点线段树还可以实现 可持久化并查集．

路径压缩

查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询．

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点．

836. 合并集合

点击展开题目

一共有 $n$ 个数，编号是 $1 \sim n$，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

1. M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中；

输入格式

第一行输入整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1 \le n,m \le 10^5$

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

C++

##include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int p[N];
int n, m;
// find(x) 表示：寻找节点 x 所在集合的根节点。
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);//如果 x 不是根节点，就先找到 x 的父节点 p[x] 的根节点，然后把 x 直接连到这个根节点上。
	return p[x];
}

int main()
{
 	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) p[i] = i;
	while(m --)
	{
		char c;
		int a, b;
		cin >> c >> a >> b;
		int pa, pb;
		pa = find(a), pb = find(b);
		if(c == 'M')
		{
			if(pa != pb) p[pa] = pb;
		}
		else
		{
			cout << (pa == pb ? "Yes" : "No") << endl;
		}
	}
	return 0;
}

图论：最短路 (Shortest Path)

注

求从某个源点到其余各点的最短路径 — Dijkstra算法 每一对顶点之间的最短路径 — Floyd算法

单源最短路

正权边

Dijkstra Ⅰ

稠密图 邻接矩阵 S集合表示当前已确定最短距离的点

1. 初始化距离 $dist[1] = 0, dist[others] = inf$
2. 循环$n$次，找到不在$S$中距离集合$S$最近的点$t$，将$t$加到集合$S$中，用$t$更新其他点的距离($t$到其他点$q$距离能否更新其他点到$q$的距离)

时间复杂度 $O(n^2)$

空间复杂度 $O(n^2)$

循环次数	1	2	3	4	5	6
s	$\{1\}$	$\{1,2\}$	$\{1,2,3\}$	$\{1,2,3,6\}$	$\{1,2,3,6,5\}$	$\{1,2,6,5,4\}$
v	$\{2,3,4,5,6\}$	$\{3,4,5,6\}$	$\{4,5,6\}$	$\{4,5\}$	$\{4\}$	$\{\}$

C++

##include <bits/stdc++.h>
using namespace std;
const int N = 550;
int g[N][N];
int dist[N];
bool st[N];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        st[t] = true;
        for(int j = 1; j <= n; j ++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    printf("%d\n", dijkstra());
    
    return 0;
}

Dijkstra Ⅱ （堆优化）

稀疏图 邻接表

C++

##include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int  j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", dijkstra());
    return 0;
}

存在负权边

Bellman-Ford

SPFA

多源最短路

Floyd

贡献者: Withnoidea

上一页入门模拟