组合数学

分类

  存在性问题 ：判断满足某种条件的情况或状态是否存在；
  计数性问题： 存在多少种满足某种条件的情况或状态；
  构造性问题： 如果已判断出满足某种条件的状态是存在的，那么如何构造出；
  最优化问题： 找出某种评论标准下的最佳(或较佳)构造方案。

BFS算法(广度优先搜索)

—-

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

双向BFS算法

—-

排列组合

排列组合与搜索

排列组合与动态规划

最短超级串

问题描述

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

示例 1：

输入：[“alex”,”loves”,”leetcode”]
输出：”alexlovesleetcode”
解释：”alex”，”loves”，”leetcode” 的所有排列都会被接受。
示例 2：

输入：[“catg”,”ctaagt”,”gcta”,”ttca”,”atgcatc”]
输出：”gctaagttcatgcatc”

矩阵全排列

编辑距离

问题描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 1.插入一个字符
• 2.删除一个字符
• 3.替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

极小化极大(Minimax)

描述

1
2
3
4
5
6
7
8
9
10
11
12

function minimax(node, depth)  
if node is a terminal node or depth = 0  
    return the heuristic value of node  
if the adversary is to play at node  
    let α := +∞  
    foreach child of node  
        α := min(α, minimax(child, depth-1))  
else {we are to play at node}  
    let α := -∞  
    foreach child of node  
        α := max(α, minimax(child, depth-1))  
return α。