递归、回溯（牛客）

题目来自牛客题目库 算法篇面试必刷TOP101。

BM55 没有重复项数字的全排列(中等)

题目

题目链接

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].

（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0<n≤6

要求：空间复杂度 O(n!) ，时间复杂度O(n!)

示例：

示例1：
输入：[1,2,3]
返回值：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2：
输入：[1]
返回值：[[1]]

解法 递归、回溯

• 终止条件：要交换的下标到达数组末尾，没有可以交换的了。
• 返回值：确定好位置的数组。
• 本级任务：每一级遍历当前元素开始的后续元素，每一级交换一次位置。

import java.util.*;

public class Solution {

    public void swap(ArrayList<Integer> nums, int a, int b) {
        int temp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, temp);
    }

    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> nums, int index) {
        if(index == nums.size() - 1)
            res.add(nums);
        else {
            // 遍历后续元素
            for(int i = index; i < nums.size(); i++) {
                // 二者交换
                swap(nums, i, index);
                // 递归向后找
                recursion(res, nums, index + 1);
                // 回溯
                swap(nums, i, index);
            }
        }
    }
    
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> nums = new ArrayList<>();
        Arrays.sort(num);
        for(int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }
        recursion(res, nums, 0);
        return res;
    }
}

BM56 有重复项数字的全排列(中等)

题目

题目链接

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围：0<n≤8 ，数组中的值满足 −1≤val≤5

要求：空间复杂度 O(n!)，时间复杂度 O(n!)

示例：

示例1：
输入：[1,1,2]
返回值：[[1,1,2],[1,2,1],[2,1,1]]
示例2：
输入：[0,1]
返回值：[[0,1],[1,0]]

解法 递归、回溯

import java.util.*;

public class Solution {

    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp, int[] num, Boolean[] vis) {
        // 临时数组满了，加入输出
        if(temp.size() == num.length) {
            // 需要声明新的数组传入，而不能直接传入temp
            res.add(new ArrayList<Integer>(temp));
            return ;
        }
        for(int i = 0; i < num.length; i++) {
            // 如果该元素已经被加入了，则不需要再加入
            if(vis[i] == true)
                continue;
            // 当前元素与同一层的上一个元素相同，且上一个元素已经用过时，不需要加入
            if(i > 0 && num[i] == num[i - 1] && !vis[i - 1])
                continue;
            vis[i] = true; // 标记为用过
            temp.add(num[i]);
            recursion(res, temp, num, vis);
            vis[i] = false; // 回溯
            temp.remove(temp.size() - 1);
        }
    }
    
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        // 注意布尔数组的声明
        Boolean[] vis = new Boolean[num.length];
        // 填充数组
        Arrays.fill(vis, false);
        Arrays.sort(num); // 排序
        recursion(res, temp, num, vis);
        return res;
    }
}

BM57 岛屿数量(中等)

题目

题目链接

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

例如：

输入

[

[1,1,0,0,0],

[0,1,0,1,1],

[0,0,0,1,1],

[0,0,0,0,0],

[0,0,1,1,1]

]

对应的输出为3

(注：存储的01数据其实是字符’0’,’1’)

示例：

示例1：
输入：[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
返回值：3
示例2：
输入：[[0]]
返回值：0
示例3：
输入：[[1,1],[1,1]]
返回值：1

解法 dfs

step 1：优先判断空矩阵等情况。

step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。

step 3：接着将该位置的1改为0，然后使用dfs判断四个方向是否为1，分别进入4个分支继续修改。

• 终止条件：周围没有1或者数组越界
• 返回值：空
• 本级任务：将相邻的1置为0

import java.util.*;
public class Solution {
    //深度优先遍历与i，j相邻的所有1
    public void dfs(char[][] grid, int i, int j) { 
        int n = grid.length;
        int m = grid[0].length;
        // 置为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);
    }
    
    public int solve (char[][] grid) {
        int n = grid.length;
        //空矩阵的情况
        if (n == 0)  
            return 0;
        int m = grid[0].length;
        //记录岛屿数
        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;
    }
}

BM58 字符串的排列(中等)

题目

题目链接

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10 要求：空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。

示例：

示例1：
输入："ab"
返回值：["ab","ba"]
说明：返回["ba","ab"]也是正确的  
示例2：
输入："aab"
返回值：["aab","aba","baa"]
示例3：
输入："abc"
返回值：["abc","acb","bac","bca","cab","cba"]
示例4：
输入：""
返回值：[""]

解法 递归、回溯

和BM56一模一样，只是把整数数组操作换成了字符串操作。

import java.util.*;

public class Solution {

    public void recursion(ArrayList<String> res, char[] charStr, StringBuffer temp, Boolean[] vis) {
        if(temp.length() == charStr.length) {
            res.add(new String(temp));
            return ;
        }
        for(int i = 0; i < charStr.length; i++){
            if(vis[i] == true)
                continue;
            if(i > 0 && charStr[i] == charStr[i - 1] && !vis[i - 1])
                continue;
            vis[i] = true;
            temp.append(charStr[i]); // 加入字符用append()方法
            recursion(res, charStr, temp, vis);
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1); // 删除字符用deleteCharAt()方法
        }
    }

    public ArrayList<String> Permutation (String str) {
        ArrayList<String> res = new ArrayList<>();
        if(str == null || str.length() == 0)
            return res;
        // 字符串转为字符数组
        char[] charStr = str.toCharArray();
        Boolean[] vis = new Boolean[str.length()];
        Arrays.fill(vis, false);
        Arrays.sort(charStr);
        // 初始化空可变长字符串
        StringBuffer temp = new StringBuffer();
        recursion(res, charStr, temp, vis);
        return res;
    }
}

BM59 N皇后问题(较难)

题目

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后， 要求：任何两个皇后不同行，不同列也不在同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1≤ n ≤9

要求：空间复杂度 O(1) ，时间复杂度 O(n!)

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例：

示例1：
输入：1
返回值：1
示例2：
输入：8
返回值：92

解法 递归

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

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

import java.util.*;
public class Solution {
    private int res;
    //判断皇后是否符合条件
    public boolean isValid(int[] pos, int row, int col){ 
        //遍历所有已经记录的行
        for(int i = 0; i < row; i++){
            //不能同行同列同一斜线
            if(row == i || col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i])) 
                return false;
        }
        return true;
    }
    
    //递归查找皇后种类
    public void recursion(int n, int row, int[] pos){ 
        //完成全部行都选择了位置
        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); 
            }
        }
    }
    public int Nqueen (int n) {
        res = 0;
        //下标为行号，元素为列号，记录皇后位置
        int[] pos = new int[n]; 
        Arrays.fill(pos, 0);
        //递归
        recursion(n, 0, pos); 
        return res; 
    }
}

BM60 括号生成(中等)

题目

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

”((()))”, “(()())”, “(())()”, “()()()”, “()(())”

数据范围：0≤n≤10

要求：空间复杂度 O(n)，时间复杂度 O(2^n^)

示例：

示例1：
输入：1
返回值：["()"]
示例2：
输入：2
返回值：["(())","()()"]

解法 递归

每当我们使用一个左括号之后，就剩下 n - 1 个左括号和 n 个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后者就是一个子问题，可以使用递归：

• 终止条件： 左右括号都使用了n个，将结果加入数组。
• 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
• 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。

import java.util.*;
public class Solution {
    public void recursion(int left, int right, String temp, ArrayList<String> res, int n){
        //左右括号都用完了，就加入结果
        if(left == n && right == n){ 
            res.add(temp);
            return;
        }
        //使用一次左括号
        if(left < n){
            recursion(left + 1, right, temp + "(", res, n);
        }
        //使用右括号个数必须少于左括号
        if(right < n && left > right){ 
            recursion(left, right + 1, temp + ")", res, n);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        //记录结果
        ArrayList<String> res = new ArrayList<String>(); 
        //递归
        recursion(0, 0, "", res, n); 
        return res;
    }
}

BM61 矩阵最长递增路径(中等)

题目

题目链接

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。

2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围：01≤n,m≤1000，0≤matrix[i][j]≤1000

进阶：空间复杂度 O(nm) ，时间复杂度 O(nm)

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，

其中的一条最长递增路径如下图所示：

示例：

示例1：
输入：[[1,2,3],[4,5,6],[7,8,9]]
返回值：5
说明：1->2->3->6->9即可。当然这种递增路径不是唯一的。  
示例2：
输入：[[1,2],[4,3]]
返回值：4
说明：1->2->3->4  

解法 dfs

• 终止条件： 进入路径最后一个点后，四个方向要么是矩阵边界，要么没有递增的位置，路径不能再增长，返回上一级。

• 返回值： 每次返回的就是本级之后的子问题中查找到的路径长度加上本级的长度。

• 本级任务： 每次进入一级子问题，先初始化后续路径长度为0，然后遍历四个方向（可以用数组表示，下标对数组元素的加减表示去往四个方向），进入符合不是边界且在递增的邻近位置作为子问题，查找子问题中的递增路径长度。因为有四个方向，所以最多有四种递增路径情况，因此要维护当级子问题的最大值。

  step 1：使用一个dp数组记录i，j处的单元格拥有的最长递增路径，这样在递归过程中如果访问到就不需要重复访问。

  step 2：遍历矩阵每个位置，都可以作为起点，并维护一个最大的路径长度的值。

  step 3：对于每个起点，使用dfs查找最长的递增路径：只要下一个位置比当前的位置数字大，就可以深入，同时累加路径长度。

import java.util.*;
public class Solution {
    //记录四个方向
    private int[][] dirs = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int n, m;
    //深度优先搜索，返回最大单元格数
    public int dfs(int[][] matrix, 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] = Math.max(dp[i][j], dfs(matrix, dp, nexti, nextj) + 1);
        }
        return dp[i][j];
    }
    
    public int solve (int[][] matrix) {
        //矩阵不为空
        if (matrix.length == 0 || matrix[0].length == 0) 
            return 0;
        int res = 0;
        n = matrix.length;
        m = matrix[0].length;
        //i，j处的单元格拥有的最长递增路径
        int[][] dp = new int[m + 1][n + 1];   // new int声明的数组默认值全为0 
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < m; j++)
                //更新最大值
                res = Math.max(res, dfs(matrix, dp, i, j)); 
        return res;
    }
}