递归 搜索 回溯 算法专题

小结

如果每个分支只有两个, 即是二叉树 就用类似二叉树遍历的方法
如果每个分支有多个, 即是多叉树, 就是用循环, 循环的次数为分叉数
层数用递归出口来规定
记录的结果是int类型, 放在参数中不需要考虑结果的恢复现场, 但是回溯要恢复
记录的结果是一个数组, 放在全局变量和参数都可以, 但是都需要考虑恢复现场

一. 找出所有子集的异或总和再求和

找出所有子集的异或总和再求和

class Solution {int sum;int path;//当前这个一层和path异或或的结果public int subsetXORSum(int[] nums) {dfs(nums, 0);return sum;}public void dfs(int[] nums, int pos){sum += path;for(int i = pos; i < nums.length; i++){path ^= nums[i];dfs(nums, i + 1);path ^= nums[i];//恢复现场}}
}

二. 全排列II

全排列II
解法一:

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permuteUnique(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();check = new boolean[nums.length];Arrays.sort(nums);dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {if (path.size() == nums.length) {if (!ret.contains(path))ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// 剪枝if (check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) {// 已经被选过 || 不是第一个&&和前一个相等&&前一个没有被选过continue;}path.add(nums[i]);check[i] = true;dfs(nums, pos + 1);check[i] = false;path.remove(path.size() - 1);}}
}

三. 电话号码的字母组合

电话号码的字母组合

class Solution {List<String> ret;StringBuffer path;String[] hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {ret = new ArrayList<>();path = new StringBuffer();if(digits.length() == 0) return ret;dfs(digits, 0);return ret;}public void dfs(String digits, int pos){//pos 有多少层if(path.length() == digits.length()){ret.add(path.toString());return;}String cur = hash[digits.charAt(pos) - '0'];for(int i = 0; i < cur.length(); i++){//每一层有多少个path.append(cur.charAt(i));dfs(digits, pos + 1);path.deleteCharAt(path.length() - 1);}}
}

四. 括号生成

括号生成
有效括号:

1. 左括号的数量等于右括号的数量
2. 从头开始的任意一个子串, 左括号的数量 >= 右括号的数量

class Solution {int left;int right;StringBuffer path;List<String> ret;public List<String> generateParenthesis(int n) {path = new StringBuffer();ret = new ArrayList<>();dfs(n);return ret;}public void dfs(int n) {if (path.length() == 2 * n) {ret.add(path.toString());return;}if (left < n) {//left数量不能超过npath.append('(');left++;dfs(n);path.deleteCharAt(path.length() - 1);left--;}if(right < left){//因为是一个一个添加, 有括号的数量不能大于左括号的数量path.append(')');right++;dfs(n);path.deleteCharAt(path.length() - 1);right--;}}
}

五. 组合

组合

class Solution {List<List<Integer>> ret;List<Integer> path;int k;public List<List<Integer>> combine(int n, int _k) {ret = new ArrayList<>();path = new ArrayList<>();k = _k;int[] nums = new int[n];for(int i = 0; i < n; i++){nums[i] = i + 1;}dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos){if(path.size() == k){ret.add(new ArrayList<>(path));return ;}for(int i = pos; i < nums.length; i++){path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);}}
}

六. 目标和

目标和

class Solution {int ret;int target;public int findTargetSumWays(int[] nums, int _target) {target = _target;dfs(nums, 0, 0);return ret;}public void dfs(int[] nums, int pos, int sum){if(pos == nums.length){if(sum == target) ret++;return;}dfs(nums, pos + 1,  sum + nums[pos]);dfs(nums, pos + 1, sum - nums[pos]);}
}

七. 组合总和

组合总和

class Solution {List<List<Integer>> ret;List<Integer> path;int target;public List<List<Integer>> combinationSum(int[] nums, int _target) {ret = new ArrayList<>();path = new ArrayList<>();target = _target;dfs(nums, 0, 0);return ret;}public void dfs(int[] nums, int pos, int sum){if(sum == target){ret.add(new ArrayList<>(path));return;}if(sum > target || pos >= nums.length) return;for(int i = pos; i < nums.length; i++){//i = pos 表示后面只需要考虑没考虑过的情况, 没选过的元素path.add(nums[i]);//参数传i 表示可重复选择同一个元素dfs(nums, i, sum + nums[i]);path.remove(path.size() - 1);}}
}

八. 字母大小写全排列

字母大小写全排列

class Solution {List<String> ret;StringBuffer path;public List<String> letterCasePermutation(String s) {ret = new ArrayList<>();path = new StringBuffer();dfs(s, 0);return ret;}public void dfs(String s, int i) {if (i == s.length()) {ret.add(path.toString());return;}char ch = s.charAt(i);//不变path.append(ch);dfs(s, i + 1);path.deleteCharAt(path.length() - 1);if (ch < '0' || ch > '9') {char tmp = change(ch);path.append(tmp);dfs(s, i + 1);path.deleteCharAt(path.length() - 1);}}public char change(char ch) {if (ch >= 'a' && ch <= 'z') {return ch -= 32;}return ch += 32;}
}

九. 优美的排列

优美的排列

class Solution {int ret;int[] arr;boolean[] check;int n;List<Integer> path;public int countArrangement(int _n) {path = new ArrayList<>(n);n = _n;check = new boolean[n+1];arr = new int[n+1];for(int i = 1; i <= n; i++){arr[i] = i;}dfs(arr, 1);return ret;}
//pos表示遍历到的位置public void dfs(int[] arr, int pos){if(pos == arr.length){ret++;return;}for(int i = 1; i <= n; i++){if(!check[i]){if(arr[i] % pos == 0 || pos % arr[i] == 0){check[i] = true;path.add(arr[i]);dfs(arr, pos + 1);check[i] = false;path.remove(path.size() - 1);}}}}
}

下面是和矩阵相关的爆搜

十. N皇后

N皇后
boolean[] checkCol 记录要添加的这一列中是否已经有元素
boolean[] dig1 记录要添加的对角线上是否有元素
boolean[] dig2 记录要添加的反对角线上是否有元素
对角线上的元素 y = x + b, y - x = b, 为了防止负数出现, 两边同时+n, y - x + n = b + n
对角线上的元素 y = -x + b, y + x = b
如果两个元素在同一个对角线上, 那么y - x + n 的值是相等的
如果两个元素在同一个反对角线上, 那么y + x 的值是相等的

class Solution {List<List<String>> ret;char[][] path;boolean[] checkCol;boolean[] dig1;boolean[] dig2;public List<List<String>> solveNQueens(int n) {ret = new ArrayList<>();path = new char[n][n];checkCol = new boolean[n];dig1 = new boolean[2 * n];dig2 = new boolean[2 * n];for(int i = 0; i < n; i++){Arrays.fill(path[i], '.');//先全部初始化为'.'}dfs(n, 0);return ret;}public void dfs(int n, int row) {if (row == n) {List<String> tmp = new ArrayList<>();for(int i = 0; i < n; i++){tmp.add(new String(path[i]));}System.out.println(tmp.toString());ret.add(new ArrayList<>(tmp));return;}for (int col = 0; col < n; col++) {if (!checkCol[col] && !dig1[row - col + n] && !dig2[row + col]) {path[row][col] = 'Q';checkCol[col] = true;dig1[row - col + n] = true;dig2[row + col] = true;dfs(n, row + 1);path[row][col] = '.';checkCol[col] = false;dig1[row - col + n] = false;dig2[row + col] = false;}}}
}

十一. 有效的数独

有效的数独
row[i][j] 表示第 i 行有没有 j 这个数, 有为true, 没有为false
col[i][j] 表示第 i 列有没有 j 这个数, 有为true, 没有为false
grid[i][j][k] 表示的是每个块中有没有这个数
每个格的下标 ij 和每个块中的下标的对应关系是grid[i /3][j / 3]

class Solution {boolean[][] row;boolean[][] col;boolean[][][] grid;public boolean isValidSudoku(char[][] board) {row = new boolean[9][10];col = new boolean[9][10];grid = new boolean[3][3][10];for(int i = 0; i < 9; i++){for( int j = 0; j < 9; j++){if(board[i][j] != '.'){int num = board[i][j] - '0';if(row[i][num] || col[j][num] || grid[i /3][j / 3][num]){return false;}row[i][num] = col[j][num] = grid[i /3][j / 3][num] = true;}}}return true;}
}

十二. 解数独

解数独

class Solution {boolean[][] row;boolean[][] col;boolean[][][] grid;public void solveSudoku(char[][] board) {row = new boolean[9][10];col = new boolean[9][10];grid = new boolean[3][3][10];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.') {int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}dfs(board);}
//返回true表示这个位置填的是正确的public boolean dfs(char[][] board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {for (int num = 1; num <= 9; num++) {if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {board[i][j] = (char) ('0' + num);row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;if (dfs(board))return true;//当所有的都返回true才是正确的, 才能返回trueboard[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;}}return false;//全部数字都试了一遍, 没有返回true, 说明前面的填错了, 返回false}}}return true;//全部填完, 返回true}
}

十三. 单词搜索

类型: 在矩阵中进行深度优先遍历
这种题一般都有一个问题, 就是元素不能重复使用, 可以使用一个boolean[][] 类型的数组来记录使用情况, 也可以在遍历完一个元素后, 修改这个元素, 但推荐使用第一种方法

class Solution {boolean[][] vis;//用于判断此时的数是否已经用过, 用过的数不能再用int m, n;char[] word;public boolean exist(char[][] board, String _word) {m = board.length;n = board[0].length;vis = new boolean[m][n];word = _word.toCharArray();//先找到第一个字符的所有位置for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board, i, j, 1)){//开始匹配下标为1的字符return true;}vis[i][j] = false;}}}return false;}//利用向量数组, 上下左右匹配字符, 省的写四个dfsint[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public boolean dfs(char[][] board, int i, int j, int pos){if(pos == word.length){return true;}for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];//上下左右位置的下标//xy是合法的                       && 没有被使用过&& 和下一个字符匹配的上if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board, x, y, pos + 1)) return true;vis[x][y] = false;}}return false;}
}

十四. 黄金矿工

黄金矿工

class Solution {boolean[][] vis;int ret;int m, n;int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public int getMaximumGold(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] != 0) {vis[i][j] = true;dfs(grid, i, j, grid[i][j]);vis[i][j] = false;}}}return ret;}public void dfs(int[][] grid, int i, int j, int sum) {ret = Math.max(ret, sum);for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && grid[x][y] != 0) {vis[x][y] = true;dfs(grid, x, y, sum + grid[x][y]);vis[x][y] = false;}}}
}

十五. 不同路径III

不同路径III

class Solution {boolean[][] vis;int m, n;int step;//记录0的个数int ret;int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public int uniquePathsIII(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int bx = 0;int by = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {step++;}else if (grid[i][j] == 1) {bx = i;by = j;}}}vis[bx][by] = true;dfs(grid, bx, by, 0);return ret;}public void dfs(int[][] grid, int i, int j, int count) {if (grid[i][j] == 2) {//在所有的爆搜结果中, 指取0的个数和step相同的if (count - 1 == step) {ret++;}return;}for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1) {vis[x][y] = true;dfs(grid, x, y, count + 1);vis[x][y] = false;}}}}