递归回溯

BM55 没有重复数字的全排列

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        backtreckPermute(num,  new ArrayList<Integer>());
        return res;
    }

    public void backtreckPermute(int[] num,  ArrayList<Integer> list){
        if (list.size() == num.length){
            res.add(new ArrayList<>(list));// 注意！！！
            return;
        }
        for (int i = 0; i < num.length; i++) {
            // 去重
            if (list.contains(num[i])) continue;
            // 做选择
            list.add(num[i]);
            // 回溯
            backtreckPermute(num,  list);
            // 撤销选择
            list.remove(list.size() - 1);
        }
    }
}

BM56 有重复数字的全排列

public class Solution {
    boolean[] vis;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, ArrayList<ArrayList<Integer>> ans, int idx, ArrayList<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

57 岛屿数量

public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        // 广度优先搜索算法
        int count = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '0') continue;
                DFS(grid, i, j);
                count++;
            }
        }
        return count;
    }
    
    public void DFS(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
            return;
        }
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        DFS(grid, i - 1, j);
        DFS(grid, i + 1, j);
        DFS(grid, i, j - 1);
        DFS(grid, i, j + 1);
    }
}

BM58 字符串的排列

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if(str.length() == 0) return res;
        char[] chars = str.toCharArray();
        boolean[] used = new boolean[chars.length];
        backtrack(chars, new StringBuilder(), res, used);
        return res;
    }
    
    public void backtrack(char[] chars, StringBuilder string, ArrayList<String> res, boolean[] used){
        if(string.length() == chars.length){
            res.add(string.toString());
            return;
        }
        
        for(int i = 0; i < chars.length; i++){
            if(used[i] == true) continue;
            // 注意注意注意！！！
            if(i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;
            string.append(chars[i]);
            used[i] = true;
            backtrack(chars, string, res, used);
            used[i] = false;
            string.deleteCharAt(string.length() - 1);
        }
    }
}

BM59 N皇后问题

BM60 括号生成

import java.util.*;
public class Solution {
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<>();
        if(n == 0) return res;
        StringBuilder track = new StringBuilder();
        // 可用的左括号的右括号数量初始化为n
        backtrack(n, n, track, res);
        return res;
    }
    
    public void backtrack(int left, int right, StringBuilder track, ArrayList<String> res){
        // 括号数量小于0，则不合法
        if(left < 0 || right < 0) return;
        // 若剩下的左括号多，则不合法
        if(right < left) return;
        // 若左右括号刚好都为0，则合法，添加结果
        if(left == 0 && right == 0){
            res.add(track.toString());
            return;
        }
        // 尝试添加左括号
        track.append('(');
        backtrack(left - 1, right, track, res);
        track.deleteCharAt(track.length() - 1);
        // 尝试添加右括号
        track.append(')');
        backtrack(left, right - 1, track, res);
        track.deleteCharAt(track.length() - 1);
    }
}

BM61 矩阵最长递增路径

import java.util.*;
import java.util.Arrays;
public class Solution {
    public int solve (int[][] matrix) {
        int maxRes = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            Arrays.fill(dp[i], 1);// 初始化
        }
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                maxRes = Math.max(maxRes, maxLength(matrix, i, j, dp));
            }
        }
        return maxRes;
    }
    // 计算当前位置[row, col]的最大长度
    public int maxLength(int[][] matrix, int row, int col, int[][] dp){
        // 特殊情况处理1：边界
        if(row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length) return 0;
        
        if(dp[row][col] != 1) return dp[row][col];
        
        // 如果左边/右边/上边/下边递增
        if(row > 0 && matrix[row][col] > matrix[row - 1][col]){
            dp[row][col] = Math.max(dp[row][col], maxLength(matrix, row - 1, col, dp) + 1);
        }
        if(row < matrix.length - 1 && matrix[row][col] > matrix[row + 1][col]){
            dp[row][col] = Math.max(dp[row][col], maxLength(matrix, row + 1, col, dp) + 1);
        }
        if(col > 0 && matrix[row][col] > matrix[row][col - 1]){
            dp[row][col] = Math.max(dp[row][col], maxLength(matrix, row, col - 1, dp) + 1);
        }
        if(col < matrix[0].length - 1 && matrix[row][col] > matrix[row][col + 1]){
            dp[row][col] = Math.max(dp[row][col], maxLength(matrix, row, col + 1, dp) + 1);
        }
        // 当前值大于周边值,或者当前位置为边界
        return dp[row][col];
    }
}