算法笔记---回溯

floodfill

/**
 * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
 * 一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 * 你可以假设网格的四个边均被水包围。
 */
复制代码

• 所谓floodfill，类似于感染，滴一滴红墨水，染红周围
• 可以看作是一个dfs

思路：找到“1”，然后dfs所有与该位相连的，完整一个dfs后，res++
随之遍历整个数组
复制代码

public class NumberOfIslands {
    // 四个方向遍历数组
    int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    int m,n;
    // 访问位
    boolean[][] visited;
    // 判断是否下标是否合法
    private boolean inArea(int x,int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    public int numIslands(char[][] grid) {
        if(grid == null||grid.length==0||grid[0].length==0){
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 当前位为“1”，且未访问过
                if(grid[i][j]=='1'&&!visited[i][j]){
                    dfs(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }
    // 进行dfs，
    private void dfs(char[][] grid,int i,int j){
        // dfs时，访问位
        visited[i][j] = true;
        // 进行四个方向的遍历
        for (int k = 0; k < 4; k++) {
           int x = i+d[k][0];
           int y = j+d[k][1];
            // 确定下标合法，当前为“1”，为访问过（三者条件）
            if(inArea(x,y)&&grid[x][y]=='1'&&!visited[x][y]){
                dfs(grid,x,y);
            }
        }
    }
}
复制代码

二维平面回溯

/**
 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 */
复制代码

• 这个时候dfs是需要递归终止条件：当找到所有单词后返回
• dfs很有套路：四个方向，访问位都是最基本的

思路：主要是dfs，递归结束条件（所有的单词找到），满足条件则访问位确定
遍历四个方向
最后一定要注意：该点未找到满足条件，则回溯（访问为false）
复制代码

public class searchWord {
    //四个方向
    private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int m, n;
    //访问位
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {

        if(board == null || word == null)
            throw new IllegalArgumentException("board&nbs***bsp;word can not be null!");

        m = board.length;
        if(m == 0)
            throw new IllegalArgumentException("board can not be empty.");
        n = board[0].length;
        if(n == 0)
            throw new IllegalArgumentException("board can not be empty.");

        visited = new boolean[m][n];
        // 遍历数组
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++)
                if(searchWord(board, word, 0, i, j))
                    return true;

        return false;
    }
    // 判断下标是否合法
    private boolean inArea( int x , int y ){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    private boolean searchWord(char[][] board,String word,int index,int x,int y){
        // 递归条件
        if(index == word.length()-1){
            return board[x][y] == word.charAt(index);
        }
        // 满足条件，则确定访问位
        if(board[x][y] == word.charAt(index)){
            visited[x][y] = true;
        // 四个方向
        for (int i = 0; i < 4; i++) {
            int newx = x+d[i][0];
            int newy = y+d[i][1];
            //下标合法，未访问，继续dfs
            if(inArea(newx,newy)&&!visited[newx][newy]&&searchWord(board,word,index+1,newx,newy)){
                return true;
            }
        }
        //没有找到则回溯
        visited[x][y] = false;
    }
    return false;
    }
}
复制代码

排列问题

给定一个没有重复数字的序列，返回其所有可能的全排列。
复制代码

N皇后问题

求 n皇后求解个数
复制代码

public class N_QueensII {
    /**
     * 记录某列是否已有皇后摆放
     */
    private boolean col[];

    /**
     * 记录某条正对角线（左上右下）是否已有皇后摆放（某条对角线对应的摆放位置为 x - y + n - 1）
     */
    private boolean dia1[];

    /**
     * 记录某条斜对角线（左下右上）是否已有皇后摆放（某条对角线对应的摆放位置为 x + y）
     */
    private boolean dia2[];

    public int totalNQueens(int n) {
        // 依然可以使用 51 号问题的解决思路，但问题是有没有更好的方法
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];
        return putQueen(n, 0);
    }

    /**
     * 递归回溯方式摆放皇后
     *
     * @param n     待摆放皇后个数
     * @param index 已摆放皇后个数
     */
    private int putQueen(int n, int index) {
        int res = 0;
        if (index == n) {
            return 1;
        }
        // 表示在 index 行的第 i 列尝试摆放皇后
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[i - index + n - 1] && !dia2[i + index]) {
                // 递归
                col[i] = true;
                dia1[i - index + n - 1] = true;
                dia2[i + index] = true;
                res += putQueen(n, index + 1);
                // 回溯
                col[i] = false;
                dia1[i - index + n - 1] = false;
                dia2[i + index] = false;
            }
        }
        return res;
    }
}
复制代码