算法解释

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。

深度优先搜索

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为 1（起始节点）->2（遍历更深一层的左子节点）->4（遍历更深一层的左子节点）->2（无子节点，返回父结点）->1（子节点均已完成遍历，返回父结点）->3（遍历更深一层的右子节点）->1（无子节点，返回父结点）->结束程序（子节点均已完成遍历）。如果我们使用栈实现，我们的栈顶元素的变化过程为 1->2->4->3。

示例

深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存在入度不为零的点，则说明有环。

有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这种做法叫做状态记录或记忆化（memoization)。

岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0。

示例 1：

输入:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
输出: 6

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

此题是十分标准的搜索题，我们可以拿来练手深度优先搜索。一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。

当然，我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时笔者推荐使用递归式写法，同时也方便进行回溯（见下节）。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。

代码

1.使用栈：

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
29
30
31
vector<int> direction{-1, 0, 1, 0, -1};
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int m = grid.size(), n = m ? grid[0].size() : 0;
    int local_area, area = 0, x, y;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j]) {
                local_area = 1;
                grid[i][j] = 0;
                stack<pair<int, int>> island;
                island.push({i, j});
                while (!island.empty()) {
                    auto [r, c] = island.top();
                    island.pop();
                    for (int k = 0; k < 4; k++) {
                        x = r + direction[k];
                        y = c + direction[k+1];
                        if (x >= 0 && x < m
                            && y >= 0 && y < n && grid[x][y] == 1) {
                            grid[x][y] = 0;
                            local_area++;
                            island.push({x, y});
                        }
                    }
                }
                area = max(area, local_area);
            }
        }
    }
    return area;
}

注意：这里我们使用了一个小技巧，对于四个方向的遍历，可以创造一个数组 [-1, 0, 1, 0, -1]，每相邻两位即为上下左右四个方向之一。

2.使用递归：

在辅函数里，一个一定要注意的点是辅函数内递归搜索时，边界条件的判定。边界判定一般有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合法（即判断放在辅函数第一行）。

第一种：

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
vector<int> direction{-1, 0, 1, 0, -1};
// 主函数
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) 
        return 0;
    int max_area = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1)
                max_area = max(max_area, dfs(grid, i, j));
        }
    }
    return max_area;
}
// 辅函数
int dfs(vector<vector<int>>& grid, int r, int c) {
    if (grid[r][c] == 0) 
        return 0;
    grid[r][c] = 0;
    int x, y, area = 1;
    for (int i = 0; i < 4; i++) {
        x = r + direction[i];
        y = c + direction[i+1];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) 
            area += dfs(grid, x, y);
    }
    return area;
}

第二种：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> direction{-1, 0, 1, 0, -1};
// 主函数
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) 
        return 0;
    int max_area = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            max_area = max(max_area, dfs(grid, i, j));
        }
    }
    return max_area;
}
// 辅函数
int dfs(vector<vector<int>>& grid, int r, int c) {
    if (r < 0 || r >= grid.size()
        || c < 0 || c >= grid[0].size() || grid[r][c] == 0)
        return 0;
    grid[r][c] = 0;
    return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c)
        + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
}

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected =
[[1,1,0],
[1,1,0],
[0,0,1]]
输出：2

示例 2：

输入：isConnected =
[[1,0,0],
[0,1,0],
[0,0,1]]
输出：3

实际上与上一题是一样的，上题中矩阵每个元素都可看做一个结点，上下左右相邻即有关系；本题中每一行或列为一个结点，元素为 1 即有关系。这里我们采用第一种递归写法。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 主函数
int findCircleNum(vector<vector<int>>& friends) {
    int n = friends.size(), count = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(friends, i, visited);
            count++;
        }
    }
    return count;
}
// 辅函数
void dfs(vector<vector<int>>& friends, int i, vector<bool>& visited) {
    visited[i] = true;
    for (int k = 0; k < friends.size(); k++) {
        if (friends[i][k] == 1 && !visited[k])
            dfs(friends, k, visited);
    }
}

太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights，heights[r][c] 表示坐标 (r, c) 上单元格高于海平面的高度。

岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动既可流向太平洋也可流向大西洋。

示例 1：

输入: heights =
[[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,7,1,4,5],
[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights =
[[2,1],
[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

虽然题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那么在不剪枝的情况下复杂度会很高。因此我们可以反过来想，从两个大洋开始向上流，这样我们只需要对矩形四条边进行搜索。搜索完成后，只需遍历一遍矩阵，满足条件的位置即为两个大洋向上流都能到达的位置。

代码 
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
29
30
31
32
33
34
35
36
37
38
39
40
vector<int> direction{-1, 0, 1, 0, -1};
// 主函数
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty())
        return {};
    vector<vector<int>> ans;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<bool>> can_reach_p(m, vector<bool>(n, false));
    vector<vector<bool>> can_reach_a(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        dfs(matrix, can_reach_p, i, 0);
        dfs(matrix, can_reach_a, i, n - 1);
    }
    for (int i = 0; i < n; i++) {
        dfs(matrix, can_reach_p, 0, i);
        dfs(matrix, can_reach_a, m - 1, i);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (can_reach_p[i][j] && can_reach_a[i][j])
                ans.push_back(vector<int>{i, j});
        }
    }
    return ans;
}
// 辅函数
void dfs(const vector<vector<int>>& matrix, vector<vector<bool>>& can_reach,
         int r, int c) {
    if (can_reach[r][c])
        return;
    can_reach[r][c] = true;
    int x, y;
    for (int i = 0; i < 4; i++) {
        x = r + direction[i];
        y = c + direction[i+1];
        if (x >= 0 && x < matrix.size() 
            && y >= 0 && y < matrix[0].size() && matrix[r][c] <= matrix[x][y])
            dfs(matrix, can_reach, x, y);
    }
}

回溯法

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。

顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节点]的步骤，只是多了回溯的步骤，变成[修改当前节点状态]→[递归子节点]→[回改当前节点状态]。

两个小诀窍，一是按引用传状态，二是所有的状态修改在递归完成后回改。

回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

按数组序穷举所有可能的排列，已经取过的标记一下，找到一组后向前回溯，取消标记，继续按此方法搜索。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> temp;
    vector<int> isIn(nums.size(), 0);
    retSeq(result, temp, nums, 0, isIn);
    return result;
}
void retSeq(vector<vector<int>> &result, vector<int> temp, vector<int> nums, int len, vector<int> isIn) {
    if(len == nums.size())
        result.push_back(temp);
    else {
        for(int i = 0; i < nums.size(); i++) {
            if(isIn[i] == 0) {
                isIn[i] = 1;
                temp.push_back(nums[i]);
                len++;
                retSeq(result, temp, nums, len, isIn);
                len--;
                temp.pop_back();
                isIn[i] = 0;
            }
        }
    }
}

这里提供一份更简洁优雅的代码，因为数字互不重复，所以穷举所有交换即可。代码框架和上面还是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 主函数
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    backtracking(nums, 0, ans);
    return ans;
}
// 辅函数
void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans) {
    if (level == nums.size() - 1) {
        ans.push_back(nums);
        return;
    }
    for (int i = level; i < nums.size(); i++) {
        swap(nums[i], nums[level]); // 修改当前节点状态
        backtracking(nums, level+1, ans); // 递归子节点
        swap(nums[i], nums[level]); // 回改当前节点状态
    }
}

不难看出回溯算法代码框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
主函数 {
       定义结果数组;
       调用辅函数(目标数组，结果数组，递归层数);
       返回结果数组;
}
辅函数 {
       递归出口;
       循环 {
           完成当前层的操作;
           递归调用下一层的辅函数;
           回溯当前层的改变量;   
       }
}

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4]]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

和上一题区别在于取的数字个数和不考虑取出顺序，第一点只是影响了结果数组大小，第二点可以这样解决：向后取数字，控制取出的组合升序，这样就避免了重复。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 主函数
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> comb(k, 0);
    int count = 0;
    backtracking(ans, comb, count, 1, n, k);
    return ans;
}
// 辅函数
void backtracking(vector<vector<int>>& ans, vector<int>& comb, int& count, int pos, int n, int k) {
    if (count == k) {
        ans.push_back(comb);
        return;
    }
    for (int i = pos; i <= n; i++) {
        comb[count++] = i;
        backtracking(ans, comb, count, i + 1, n, k);
        count--;
    }
}

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board =
[[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]],
word = “ABCCED”
输出：true

示例 3：

输入：board =
[[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]],
word = “ABCB”
输出：false

在我们对任意位置进行深度优先搜索时，我们先标记当前位置为已访问，以避免重复遍历（如防止向右搜索后又向左返回）；在所有的可能都搜索完成后，再回改当前位置为未访问，防止干扰其它位置搜索到当前位置。

代码 
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
bool exist(vector<vector<char>>& board, string word) {
    if (board.empty()) 
        return false;
    int m = board.size(), n = board[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    bool find = false;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            backtracking(i, j, board, word, find, visited, 0);
    }
    return find;
}
void backtracking(int i, int j, vector<vector<char>>& board, string& word, bool& find, vector<vector<bool>>& visited, int pos) {
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
        return;
    if (visited[i][j] || find || board[i][j] != word[pos])
        return;
    if (pos == word.size() - 1) {
        find = true;
        return;
    }
    visited[i][j] = true;
    backtracking(i + 1, j, board, word, find, visited, pos + 1);
    backtracking(i - 1, j, board, word, find, visited, pos + 1);
    backtracking(i, j + 1, board, word, find, visited, pos + 1);
    backtracking(i, j - 1, board, word, find, visited, pos + 1);
    visited[i][j] = false;
}

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]

示例 2：

输入：n = 1
输出：[[“Q”]]

和上一题是类似的，本题也是通过修改状态矩阵来进行回溯。不同的是，我们需要对每一行、列、左斜、右斜建立访问数组，来记录它们是否存在皇后。另外，本题中限制了每一行只有一个皇后，所以不用遍历矩阵中每一个位置，只需遍历每一行即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans;
    if (n == 0)
        return ans;
    vector<string> board(n, string(n, '.'));
    vector<bool> column(n, false), ldiag(2*n-1, false), rdiag(2*n-1, false);
    backtracking(ans, board, column, ldiag, rdiag, 0, n);
    return ans;
}
void backtracking(vector<vector<string>> &ans, vector<string> &board, vector<bool> &column, vector<bool> &ldiag, vector<bool> &rdiag, int row, int n) {
    if (row == n) {
        ans.push_back(board);
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (column[i] || ldiag[n-row+i-1] || rdiag[row+i])
            continue;
        board[row][i] = 'Q';
        column[i] = ldiag[n-row+i-1] = rdiag[row+i] = true;
        backtracking(ans, board, column, ldiag, rdiag, row+1, n);
        board[row][i] = '.';
        column[i] = ldiag[n-row+i-1] = rdiag[row+i] = false;
    }
}

广度优先搜索

广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。

考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为 [1]->[2->3]->[4]，其中方括号代表每一层的元素。

示例

这里要注意，深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否能达到另一个节点。

最短的桥

在给定的二维二进制数组 A 中，存在两座岛（岛是由四面相连的 1 形成的一个最大组）现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目（可以保证答案至少是 1）

示例 1：

输入：A = [[0,1],[1,0]]
输出：1

示例 2：

输入：A = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

本题实际上是求两个岛屿间的最短距离，因此我们可以先通过任意搜索方法找到其中一个岛屿，然后利用广度优先搜索，查找其与另一个岛屿的最短距离。

代码 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
vector<int> direction{-1, 0, 1, 0, -1};
int shortestBridge(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> points;
    bool flipped = false;
    //DFS找到第一个岛屿，标记为2
    for (int i = 0; i < m; i++) {
        if (flipped) 
            break;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dfs(points, grid, m, n, i, j);
                flipped = true;
                break;
            }
        }
    }
    //BFS，一层层向外扩展至找到第二个岛屿
    int x, y;
    int level = 0;
    while (!points.empty()){
        level++;
        //n_points每减一，队列里就排除一个，减到0说明往外扩一层还没有找到，层数加一，继续扩
        int n_points = points.size();
        while (n_points--) {
            auto [r, c] = points.front();
            points.pop();
            for (int k = 0; k < 4; k++) {
                x = r + direction[k];
                y = c + direction[k+1];
                if (x >= 0 && y >= 0 && x < m && y < n) {
                    if (grid[x][y] == 2)
                        continue;
                    if (grid[x][y] == 1)
                        return level;
                    points.push({x, y});
                    grid[x][y] = 2;
                }
            }
        }
    }
    return 0;
}
void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int m, int n, int i, int j) {
    if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == 2)
        return;
    //将边界一圈一个个压入队列
    if (grid[i][j] == 0) {
        points.push({i, j});
        return;
    }
    grid[i][j] = 2;
    dfs(points, grid, m, n, i - 1, j);
    dfs(points, grid, m, n, i + 1, j);
    dfs(points, grid, m, n, i, j - 1);
    dfs(points, grid, m, n, i, j + 1);
}

单词接龙II

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的转换序列是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

  • 每对相邻的单词之间仅有单个字母不同。
  • 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
  • sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的最短转换序列，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出：[[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]

示例 2：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出：[]

双向BFS构建节点树，再用DFS找出所有通路。

我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那么它们相连。因为题目需要输出修改次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。

我们同时还使用了一个小技巧：我们并不是直接从起始节点进行广度优先搜索，直到找到终止节点为止；而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少的那一端，这样我们可以减少搜索的总结点数。

在搜索结束后，我们还需要通过回溯法来重建所有可能的路径。

搜索图示

代码 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
unordered_map<string, vector<string>> tree;//节点图，把所有符合只差一个字符的单词联系起来
vector<vector<string>> ans;//存储结果
vector<vector<string> > findLadders(string beginWord, string endWord, vector<string> & wordList) {
    //特判
    if(wordList.size() == 0 || find(wordList.begin(), wordList.end(), endWord) == wordList.end()) 
        return {};
    //双向BFS
    swap(beginWord, endWord);//这里交换是为了建立从尾到头的树
    unordered_set<string> bfsFromBegin{beginWord};//从上到下BFS
    unordered_set<string> bfsFromEnd{endWord};//从下到上
    unordered_set<string> dirc(wordList.begin(), wordList.end());//从单词目录中取出所有单词，用于标记是否搜索过
    bool findFlag = false, reverseFlag = false;//上下是否相交，是否转换搜索方向
    while(!bfsFromBegin.empty()){
        unordered_set<string> next;//存放下一层的搜索对象
        for(string s : bfsFromBegin)
            dirc.erase(s);//擦除已经搜索过的
        for(string s1 : bfsFromBegin){
            //寻找只相差一个字符的单词
            for(int i = 0; i < s1.size(); i++){
                string s2 = s1;
                for(char c = 'a'; c <= 'z'; c++){
                    s2[i] = c;
                    if(dirc.count(s2) == 0) 
                        continue;
                    if(bfsFromEnd.count(s2))
                        findFlag = true;
                   	else
                        next.insert(s2);
                    reverseFlag ? tree[s2].push_back(s1) : tree[s1].push_back(s2);
                }
            }
        }
        bfsFromBegin = next;
        //每次只搜索节点次数少的那端
        if(bfsFromBegin.size() > bfsFromEnd.size()){
            reverseFlag = !reverseFlag;
            swap(bfsFromBegin, bfsFromEnd);
        }
        if(findFlag)
            break;
    }
    //DFS寻找所有通路
    vector<string> cur = {beginWord};
    dfs(cur, beginWord, endWord);
    return ans;
}
void dfs(vector<string>& cur, string curWord, string endWord){
    if(curWord == endWord){
        //搜索方向是反着的，要翻转
        reverse(cur.begin(), cur.end());
        ans.push_back(cur);
        reverse(cur.begin(), cur.end());
        return;
    }
    for(string s : tree[curWord]){
        cur.push_back(s);
        dfs(cur, s, endWord);
        cur.pop_back();
    }
}

注意：从前向后DFS会超时，所以从后向前DFS，面向数据编程了属于是（

练习

被围绕的区域

给你一个 m x n 的矩阵 board，由若干字符 ‘X’ 和 ‘O’，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

输入：board =
[[“X”,”X”,”X”,”X”],
[“X”,”O”,”O”,”X”],
[“X”,”X”,”O”,”X”],
[“X”,”O”,”X”,”X”]]
输出：[[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

主要问题在于如何判断是否是被包围的，可以dfs每一个边界元素，把与之相连的标记为 ‘A’，然后遍历矩阵赋值即可。

代码 
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
29
30
31
32
int n, m;
void dfs(vector<vector<char>>& board, int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O')
        return;
    board[x][y] = 'A';
    dfs(board, x + 1, y);
    dfs(board, x - 1, y);
    dfs(board, x, y + 1);
    dfs(board, x, y - 1);
}
void solve(vector<vector<char>>& board) {
    n = board.size();
    if (n == 0)
        return;
    m = board[0].size();
    for (int i = 0; i < n; i++) {
        dfs(board, i, 0);
        dfs(board, i, m - 1);
    }
    for (int i = 1; i < m - 1; i++) {
        dfs(board, 0, i);
        dfs(board, n - 1, i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'A')
                board[i][j] = 'O';
            else if (board[i][j] == 'O')
                board[i][j] = 'X';
        }
    }
}

二叉树的所有路径

给你一个二叉树的根节点 root，按任意顺序返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。

示例 1：

输入：示例

root = [1,2,3,null,5]
输出：[“1->2->5”,”1->3”]

示例 2：

输入：root = [1]
输出：[“1”]

DFS

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void construct_paths(TreeNode* root, string path, vector<string>& paths) {
    if (root != nullptr) {
        path += to_string(root->val);
        if (root->left == nullptr && root->right == nullptr)
            paths.push_back(path);
        else {
            path += "->";
            construct_paths(root->left, path, paths);
            construct_paths(root->right, path, paths);
        }
    }
}
vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> paths;
    construct_paths(root, "", paths);
    return paths;
}

全排列II

给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

重复的来源是相同数字的位置可交换，所以只需限制相同数字的相对位置为固定的即可，可以对数组排序，按照数组下标的相对位置。

代码 
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
vector<int> vis;
void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
    if (idx == nums.size()) {
        ans.emplace_back(perm);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        //不能取的两种情况，一是取过了，二是相同数字但位置在前的还未被取
        if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]))
            continue;
        perm.emplace_back(nums[i]);//比push_back效率高
        vis[i] = 1;
        backtrack(nums, ans, idx + 1, perm);
        vis[i] = 0;
        perm.pop_back();
    }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> perm;
    vis.resize(nums.size());
    sort(nums.begin(), nums.end());
    backtrack(nums, ans, 0, perm);
    return ans;
}

组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[[1,1,6],[1,2,5],[1,7],[2,6]]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[[1,2,2],[5]]

带重复的回溯 = 排序 + 判断。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> res;
vector<int> temp;
void backtrack(vector<int>& candidates, int target, int index) {
    if(target == 0) {
        res.push_back(temp);
        return;
    }
    for(int i = index; i < candidates.size() && target-candidates[i] >= 0; i++) {
        //避免重复，只需要避免取的数和上一层回溯拿掉的数相等即可
        if(i > index && candidates[i] == candidates[i-1])
            continue;
        temp.push_back(candidates[i]);
        backtrack(candidates, target-candidates[i], i+1);
        temp.pop_back();
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    backtrack(candidates, target, 0);
    return res;
}

解数独

编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

输入：输入示例

输出：输出示例

类似 N 皇后，建立数组标记行、列和九宫格内的数字出现情况，然后回溯法填数字即可。

代码 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
bool line[10][10], column[10][10], block[3][3][10];
bool dfs(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char temp = board[i][j];
            if (temp == '.') {
                for (int k = 1; k <= 9; k++) {
                    if (!line[i][k] && !column[j][k] && !block[i/3][j/3][k]) {
                        board[i][j] = k + '0';
                        line[i][k] = true;
                        column[j][k] = true;
                        block[i / 3][j / 3][k] = true;
                        if (dfs(board))
                            return true;
                        board[i][j] = '.';
                        line[i][k] = false;
                        column[j][k] = false;
                        block[i / 3][j / 3][k] = false;
                    }
                }
                return false;
            }
        }
    }
    return true;
}
void solveSudoku(vector<vector<char>>& board) {
    memset(line, 0, sizeof(line));
    memset(column, 0, sizeof(column));
    memset(block, 0, sizeof(block));
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char temp = board[i][j] - '0';
            if (temp != '.' - '0') {
                line[i][temp] = true;
                column[j][temp] = true;
                block[i / 3][j / 3][temp] = true;
            }
        }
    }
    dfs(board);
}

最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。任意两节点只有一条路径。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h。在所有可能的树中，具有最小高度的树（即，min(h)）被称为最小高度树。

请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

暴力解法会超时，这里采用类似拓扑排序（好高级的名词doge)的方法。目标是找到与距离最远的叶节点的距离最小的根节点，如果把树按照最长路径给捋成一条链子，那么很显然应该选取根节点为链子中点的一个或两个节点，如何取到呢，可以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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1)
        return {0};
    if (n == 2)
        return {0, 1};
    vector<int> degree(n);   //每个节点对应的度数
    map<int,vector<int>> m;  //邻接表
    vector<int> ans; //结果
    for (int i = 0; i < edges.size(); i++){
        int u=edges[i][0];
        int v=edges[i][1];
        degree[u]++;
        degree[v]++;
        m[u].push_back(v);
        m[v].push_back(u);
    }
    queue<int> q;
    //把叶子节点入队列
    for (int i = 0; i < n; i++)
        if (degree[i] == 1)
            q.push(i);
    //从外向内一层一层剥
    int k = 0;
    while (n - k > 2){
        int sz=q.size();
        for (int i = 0; i < sz; i++){
            int t = q.front();
            degree[t]--;
            q.pop();
            k++;
            //加入t的邻接叶子节点
            for (auto j : m[t]){
                degree[j]--;
                if (degree[j] == 1)
                    q.push(j);
            }    
        }
    }
    for (int i = 0; i < n - k; i++) {
        ans.push_back(q.front());
        q.pop();
    }
    return ans; 
}