LeetCode -- 递归 dfs、回溯

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList();
        if (n == 0) {
            return result;
        }
        // 必须要用字符串，每次拼接要产生新对象。不能用 StringBuffer StringBuilder 之类，栈里不能都操作一个对象
        dfs(n, n, "", result);
        return result;
    }

    private void dfs(int leftN, int rightN, String currentNodeStr, List<String> result) {
        // 左右括号都用完
        if (leftN == 0 && rightN == 0) {
            result.add(currentNodeStr);
            return;
        }

        // 剩余的右括号不仅要 cover 掉剩余的左括号，还要 cover 掉现有没匹配上的左括号
        // 所以剩余的右括号一定要大于剩余的左括号
        if (rightN < leftN) {
            return;
        }

        // 左、右递归
        if (leftN > 0) {
            // 必须要 leftN-1 ，不能 leftN--
            dfs(leftN-1, rightN, currentNodeStr + "(", result);
        }
        if (rightN > 0) {
            // 必须要 rightN-1 ，不能 rightN--
            dfs(leftN, rightN-1, currentNodeStr + ")", result);
        }
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        int islandNum = 0;
        for (int i=0; i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                // 深度优先遍历，对一格陆地（=='1'）遍历,
                // 就会把与它连通的所有陆地遍历到，全部标记为2。从而这一次标记到的作为一个岛屿数量 +1
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islandNum++;
                }
            }
        }
        return islandNum;
    }

    private void dfs(char[][] grid, int x, int y) {
        if (!isInGrid(grid, x, y)) {
            return;
        }
        if (grid[x][y] != '1') {
            return;
        }
        // 访问过的标记为2，不再重复访问
        grid[x][y] = '2';
        // 对这个格子的上下左右分别dfs
        // 上
        dfs(grid, x, y+1);
        // 下
        dfs(grid, x, y-1);
        // 左
        dfs(grid, x-1, y);
        // 右
        dfs(grid, x+1, y);
    }

   // 判断这个格子是否已经超出了 grid 的范围
    private boolean isInGrid(char[][] grid, int x, int y) {
        // 注意是 >= 0 不是 >0
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
}

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxAreaOfIsland = 0;
        for (int i=0;i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                // 每次 dfs 完的都是一整块岛屿
                if (grid[i][j] == 1) {
                    int thisIslandArea = dfs(grid, i, j);
                    maxAreaOfIsland = Math.max(maxAreaOfIsland, thisIslandArea);
                }
            }
        }
        return maxAreaOfIsland;
    }

    private int dfs(int[][] grid, int x, int y) {
        if (!isInGrid(grid, x, y)) {
            return 0;
        }
        if (grid[x][y] != 1) {
            return 0;
        }
        grid[x][y] = 2;

        // 自己1 + 上下左右
        return 1 + dfs(grid, x, y+1)
                + dfs(grid, x, y-1)
                + dfs(grid, x-1, y)
                + dfs(grid, x+1, y);
    }

    private boolean isInGrid(int[][] grid, int x, int y) {
        return x>=0 && x<grid.length && y>=0 && y<grid[0].length;
    }
}

class Solution {


    private static List<List<String>> res = new ArrayList();


    public Solution() {
        // 不知道为啥，提交答案的时候似乎有之前用例的残余
        res.clear();
    }

    public List<List<String>> solveNQueens(int n) {
        dfs(n, getInitChessBoard(n), 0);
        return res;
    }

    private void dfs(int n, char[][] chessBoard, int newQueenRow) {
        if (newQueenRow == n) {
            res.add(char2DArray2StringList(chessBoard, n));
            return;
        }


         // 对每个分支 dfs。每个分支是每一列。（列的变化通过在 chessBoard 的放置传递进去，而层数即行的变化需要作为显式参数）
        for (int newQueenCol=0;newQueenCol<n;++newQueenCol) {
            // 不能 return 返回，因为对那些不满足条件的，要回溯，即回去恢复现场
            /* if (!canSet(n, chessBoard, newQueenRow, newQueenCol)) {
                return;
            }
            */
            if (canSet(n, chessBoard, newQueenRow, newQueenCol)) {
                // 可以设置了再设置
                chessBoard[newQueenRow][newQueenCol] = 'Q';
                dfs(n, chessBoard, newQueenRow + 1);
                // 回溯就指的是这一步，不满足条件的不要 return退出搜索，而是到这里回来后恢复现场
                chessBoard[newQueenRow][newQueenCol] = '.';
            }
        }
    }

    private boolean canSet(int n, char[][] chessBoard, int newQueenRow, int newQueenCol) {
        // 不用检查同一行（每次 dfs 层数 +1 也就是说限制了一行只能放置一个）

        // 检查同一列上面
        for (int i=0; i<newQueenRow; i++) {
            // 不是自己且为 Q
            if (chessBoard[i][newQueenCol] == 'Q') {
                return false;
            }
        }

        // 检查左上斜对角（不用检查下半截）
        // 注意不是双层循环，斜对角要横纵坐标同进同退，是单层循环
        for (int i=newQueenRow-1,j=newQueenCol-1;i>=0 && j>=0; i--,j--) {
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查右上斜对角（不用检查下半截）
        // 注意不是双层循环，斜对角要横纵坐标同进同退，是单层循环
        for (int i=newQueenRow-1,j=newQueenCol+1;i>=0 && j<n; i--,j++) {
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    } 

    private char[][] getInitChessBoard(int n) {
        char[][] initChessBoard = new char[n][n];
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                initChessBoard[i][j] = '.';
            }
        }
        return initChessBoard;
    }

    private List<String> char2DArray2StringList(char[][] charArray, int n) {
        List<String> list = new ArrayList();
        for (int i=0;i<n;i++) {
            // copy 一行的字符 到 字符串 s
            String s = String.copyValueOf(charArray[i], 0, n);
            list.add(s);
        }
        return list;
    }

   
}

class Solution {

    public Solution() {
        resList.clear();
    }

    private List<String> resList = new ArrayList();

    private static Map<Character, List<Character>> buttonMap = new HashMap();

    static {
        buttonMap.put('2', Arrays.asList('a', 'b', 'c'));
        buttonMap.put('3', Arrays.asList('d', 'e', 'f'));
        buttonMap.put('4', Arrays.asList('g', 'h', 'i'));
        buttonMap.put('5', Arrays.asList('j', 'k', 'l'));
        buttonMap.put('6', Arrays.asList('m', 'n', 'o'));
        buttonMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
        buttonMap.put('8', Arrays.asList('t', 'u', 'v'));
        buttonMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
    }


    public List<String> letterCombinations(String digits) {
        if (digits == null || "".equals(digits)) {
            return resList;
        }
        dfs(digits, 0, "");
        return resList;
    }

    private void dfs(String digits, int curButtonLayer, String curRes) {
        // 走到最后一层叶子节点，结果获得，递归结束
        if (curButtonLayer == digits.length()) {
            resList.add(curRes);
            return;
        }

        //根据层数获得当前按钮
        Character curButton = digits.charAt(curButtonLayer);
        //根据当前按钮获得当前按钮上的字符
        List<Character> buttonChars = buttonMap.get(curButton);

        // 递归树的分支是每个按钮上对应的那几个字符，因此每次递归对这几个字符分别递归
        for (int i=0;i<buttonChars.size();i++) {
            // 递归树的层数是按钮的总个数，每次递归层数加一
            dfs(digits, curButtonLayer + 1, curRes+buttonChars.get(i));
        }
    }
}