【牛客网】递归/回溯

BM55 没有重复项数字的全排列

class Solution {
public:
    void recursion(vector<vector<int>> &res, vector<int> &num, int index){
        //分支进入结尾，找到一种排列
        if(index == num.size() - 1)
            res.push_back(num);
        else{
            //遍历后续的元素
            for(int i = index; i < num.size(); i++){
                //交换二者
                swap(num[i], num[index]);
                //继续向后找
                recursion(res, num, index + 1);
                //回溯
                swap(num[i], num[index]);
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        //先按字典序排序
        sort(num.begin(), num.end());
        vector<vector<int>> res;
        //递归获取
        recursion(res, num, 0);
        return res;
    }
};
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

BM56 有重复项数字的全排列

class Solution {
public:
    void recursion(vector<vector<int>> &res, vector<int> &num, vector<int> &temp, vector<int> &vis){
        //临时数组满了加入输出
        if(temp.size() == num.size()){
            res.push_back(temp);
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < num.size(); i++){
            //如果元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
                //当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] = 1;
            //加入数组
            temp.push_back(num[i]);
            recursion(res, num, temp, vis);
            //回溯
            vis[i] = 0;
            temp.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        //先按字典序排序
        sort(num.begin(), num.end());
        //标记每个位置的元素是否被使用过
        vector<int> vis(num.size(), 0);
        vector<vector<int>> res;
        vector<int> temp;
        //递归获取
        recursion(res, num, temp, vis);
        return res;
    }
};
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

BM57 岛屿数量

他这个关键有一个改0操作，很需要注意。

class Solution {
public:
    //深度优先遍历与i,j相邻的所有1
    void dfs(vector<vector<char>> &grid, int i, int j){
        int n = grid.size();
        int m = grid[0].size();
        //置为0
        grid[i][j] = '0';
        //后续四个方向遍历
        if(i - 1 >= 0 && grid[i - 1][j] == '1')
            dfs(grid, i - 1, j);
        if(i + 1 < n && grid[i + 1][j] == '1')
            dfs(grid, i + 1, j);
        if(j - 1 >= 0 && grid[i][j - 1] == '1')
            dfs(grid, i, j - 1);
        if(j + 1 < m && grid[i][j + 1] == '1')
            dfs(grid, i, j + 1);
    }
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();
        //空矩阵的情况
        if(n == 0)
            return 0;
        int m = grid[0].size();
        //记录岛屿数
        int count = 0;
        //遍历矩阵
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //遍历到1的情况
                if(grid[i][j] == '1'){
                    //计数
                    count++;
                    //将与这个1相邻的所有1置为0
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};
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

BM58 字符串的排列

知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

class Solution {
public:
    void recursion(vector<string> &res, string &str, string &temp, vector<int> &vis){
        //临时字符串满了加入输出
        if(temp.length() == str.length()){
            res.push_back(temp);
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < str.length(); i++){
            //如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] = 1;
            //加入临时字符串
            temp.push_back(str[i]);
            recursion(res, str, temp, vis);
            //回溯
            vis[i] = 0;
            temp.pop_back();
        }
    }
    vector<string> Permutation(string str) {
        //先按字典序排序，使重复字符相邻
        sort(str.begin(), str.end());
        //标记每个位置的字符是否被使用过
        vector<int> vis(str.size(), 0);
        vector<string> res;
        string temp;
        //递归获取
        recursion(res, str, temp, vis);
        return res;
    }
};
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

BM59 N皇后问题

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

n个皇后，不同行不同列，那么肯定棋盘每行都会有一个皇后，每列都会有一个皇后。如果我们确定了第一个皇后的行号与列号，则相当于接下来在n−1n-1n−1行中查找n−1n-1n−1个皇后，这就是一个子问题，因此使用递归：

• 终止条件： 当最后一行都被选择了位置，说明n个皇后位置齐了，增加一种方案数返回。
• 返回值： 每一级要将选中的位置及方案数返回。
• 本级任务： 每一级其实就是在该行选择一列作为该行皇后的位置，遍历所有的列选择一个符合条件的位置加入数组，然后进入下一级。

具体做法：

class Solution {
public:
    //判断皇后是否符合条件
    bool isValid(vector<int> &pos, int row, int col){
        //遍历所有已经记录的行
        for(int i = 0; i < row; i++){
            //不能同行同列同一斜线
            if(row == i || col == pos[i] || abs(row - i) == abs(col - pos[i]))
                return false;
        }
        return true;
    }
    
    //递归查找皇后
    void recursion(int n, int row, vector<int> &pos, int &res){
        //完成全部行都选择了位置
        if(row == n){
            res++;
            return;
        }
        //遍历所有列
        for(int i = 0; i < n; i++){
            //检查该位置是否符合条件
            if(isValid(pos, row, i)){
                //加入位置
                pos[row] = i;
                //递归继续查找
                recursion(n, row + 1, pos, res);
            }
        }
    }
    int Nqueen(int n) {
        int res = 0;
        //下标为行号，元素为列号，记录皇后位置
        vector<int> pos(n, 0);
        //递归
        recursion(n, 0, pos, res);
        return res;
    }
};
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

BM60 括号生成

class Solution {
public:
    void recursion(int left, int right, string temp, vector<string> &res, int n){
        //左右括号都用完了就加入结果
        if(left == n && right == n){
            res.push_back(temp);
            return;
        }
        //使用一次左括号
        if(left < n)
            recursion(left + 1, right, temp + "(", res, n);
        //使用右括号个数必须少于左括号
        if(right < n && left > right)
            recursion(left, right + 1, temp + ")", res, n);
    }
    vector<string> generateParenthesis(int n) {
        //记录结果
        vector<string> res;
        //记录每次组装的字符串
        string temp;
        //递归
        recursion(0, 0, temp, res, n);
        return res;
    }
};
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

BM61 矩阵最长递增路径

class Solution {
public:
    //记录四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n, m;
    //深度优先搜索，返回最大单元格数
    int dfs(vector<vector<int>> &matrix, vector<vector<int>> &dp, int i, int j){
        if(dp[i][j] != 0)
            return dp[i][j];
        dp[i][j]++;
        for(int k = 0; k < 4; k++){
            int nexti = i + dirs[k][0];
            int nextj = j + dirs[k][1];
            //判断条件
            if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j]){
                dp[i][j] = max(dp[i][j], dfs(matrix, dp, nexti, nextj) + 1);
            }
        }
        return dp[i][j];
    }
    int solve(vector<vector<int>> &matrix) {
        //矩阵不为空
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int res = 0;
        n = matrix.size();
        m = matrix[0].size();
        //i, j处的单元格拥有最长递增路径
        vector<vector<int>> dp(n, vector<int> (m));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                //更新最大值
                res = max(res, dfs(matrix, dp, i, j));
        return res;
    }
};
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