22. 括号生成
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);
}
}
}
200. 岛屿数量
695. 岛屿的最大面积
注意深度优先遍历，对一格陆地（=='1'）遍历, 就会把与它连通的所有陆地遍历到，全部标记为2, 完成一个岛屿。从而这一次标记到的作为一个岛屿数量 +1
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++;
}
}
}
岛屿数量
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;
}
}
51. N 皇后
在类中定义一个全局的结果
树的最大层数是行，每个分支是列，每次递归行数加一，循环对每一列进行递归
递归函数的最开始，判断 如果行数已经到了最后一行（=n），添加到全局结果中，return
判断可以放置，就先在棋盘上放置好（设为 "Q"），再进行递归
注意如果 判断不可以放置，不用 return，而是回来之后恢复现场，重新设为 "."，也就是回溯恢复现场
判断能否放置：检查此次皇后放置位置的同一列的上半部分。以及左上斜对角和右上斜对角（下半部分不用检查），检查斜对角的时候注意是单层循环，ij行列同时加减，不是双层循环
关于回溯
先将第一个皇后放在第一行的第一列上，符合题目要求
开始放置第二个皇后。放在第二行的第一个与第一行的皇后为同一列，不符合题意，继续向后搜素，放在第二列上面与第一个皇后在同一斜线上，不符合题意，继续向后搜素，发现放在第三列符合题意
开始放置第三个皇后。放在第三行的任意位置都会出现冲突，此时需要回溯，将第二个皇后放置在第四列，此时符合题意，继续放置第三个皇后，发现第三个皇后放置在第三行的第二列符合题意
继续放置第四个皇后。放在第四行的任意位置都会出现冲突，此时需要回溯，第三个皇后向后移动，发现依然不符合题意，继续回溯，第二行的皇后无法再向后移动，继续回溯，将第一个皇后向后移动到第二列，符合题意
移动第二个皇后，发现放在第四列符合题意
移动第三个皇后，发现放在第一列符合题意
移动第四个皇后，发现放在第三列符合题意
回溯结束
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;
}
}
17. 电话号码的字母组合
递归树的层数是按钮的总个数，每次递归层数加一
递归树的分支是每个按钮上对应的那几个字符，因此每次递归对这几个字符分别递归
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));
}
}
}
标签：return,题意,递归,--,dfs,int,buttonMap,LeetCode From： https://www.cnblogs.com/suBlog/p/17371026.html