1.找出所有子集的异或总和再求和（easy）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {int path;int sum;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]; // 恢复现场}}
}2.全排列2
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {List<Integer> path;List<List<Integer>> ret;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 (pos == nums.length) {ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// 剪枝if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] ||check[i - 1] != false)) {path.add(nums[i]);check[i] = true;dfs(nums, pos + 1);// 回溯 -> 恢复现场path.remove(path.size() - 1);check[i] = false;}}}
}3.电话号码的字母组合（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {String[] hash = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz" };List<String> ret;StringBuffer path;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) {if (pos == 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); // 恢复现场}}
}4.括号生成
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {int left, right, n;StringBuffer path;List<String> ret;public List<String> generateParenthesis(int _n) {n = _n;path = new StringBuffer();ret = new ArrayList<>();dfs();return ret;}public void dfs() {if (right == n) {ret.add(path.toString());return;}if (left < n) // 添加左括号{path.append('(');left++;dfs();path.deleteCharAt(path.length() - 1);left--; // 恢复现场}if (right < left) // 添加哎右括号{path.append(')');right++;dfs();path.deleteCharAt(path.length() - 1);right--; // 恢复现场}}
}5.组合
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {List<Integer> path;List<List<Integer>> ret;int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n;k = _k;path = new ArrayList<>();ret = new ArrayList<>();dfs(1);return ret;}public void dfs(int start) {if (path.size() == k) {ret.add(new ArrayList<>(path));return;}for (int i = start; i <= n; i++) {path.add(i);dfs(i + 1);path.remove(path.size() - 1); // 恢复现场}}
}6.目标和
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution{int ret, aim;public int findTargetSumWays(int[] nums, int target) {aim = target;dfs(nums, 0, 0);return ret;}public void dfs(int[] nums, int pos, int path){if(pos == nums.length){if(path == aim) ret++;return;}// 加法dfs(nums, pos + 1, path + nums[pos]);// 减法dfs(nums, pos + 1, path - nums[pos]);}
}7.组合总和
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {int aim;List<Integer> path;List<List<Integer>> ret;public List<List<Integer>> combinationSum(int[] nums, int target) {path = new ArrayList<>();ret = new ArrayList<>();aim = target;dfs(nums, 0, 0);return ret;}public void dfs(int[] nums, int pos, int sum) {if (sum == aim) {ret.add(new ArrayList<>(path));return;}if (sum > aim || pos == nums.length)return;// 枚举 nums[pos] 使⽤多少个for (int k = 0; k * nums[pos] + sum <= aim; k++) {if (k != 0)path.add(nums[pos]);dfs(nums, pos + 1, sum + k * nums[pos]);}// 恢复现场for (int k = 1; k * nums[pos] + sum <= aim; k++) {path.remove(path.size() - 1);}}
}8.字母大小写全排列
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {StringBuffer path;List<String> ret;public List<String> letterCasePermutation(String s) {path = new StringBuffer();ret = new ArrayList<>();dfs(s, 0);return ret;}public void dfs(String s, int pos) {if (pos == s.length()) {ret.add(path.toString());return;}char ch = s.charAt(pos);// 不改变path.append(ch);dfs(s, pos + 1);path.deleteCharAt(path.length() - 1); // 恢复现场// 改变if (ch < '0' || ch > '9') {char tmp = change(ch);path.append(tmp);dfs(s, pos + 1);path.deleteCharAt(path.length() - 1); // 恢复现场}}public char change(char ch) {if (ch >= 'a' && ch <= 'z')return ch -= 32;elsereturn ch += 32;}
}9.优美的排列
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[] check;int ret;public int countArrangement(int n) {check = new boolean[n + 1];dfs(1, n);return ret;}public void dfs(int pos, int n) {if (pos == n + 1) {ret++;return;}for (int i = 1; i <= n; i++) {if (check[i] == false && (i % pos == 0 || pos % i == 0)) {check[i] = true;dfs(pos + 1, n);check[i] = false; // 恢复现场}}}
}10.N皇后
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[] checkCol, checkDig1, checkDig2;List<List<String>> ret;char[][] path;int n;public List<List<String>> solveNQueens(int _n) {n = _n;checkCol = new boolean[n];checkDig1 = new boolean[n * 2];checkDig2 = new boolean[n * 2];ret = new ArrayList<>();path = new char[n][n];for (int i = 0; i < n; i++)Arrays.fill(path[i], '.');dfs(0);return ret;}public void dfs(int row) {if (row == n) {// 添加结果List<String> tmp = new ArrayList<>();for (int i = 0; i < n; i++) {tmp.add(new String(path[i]));}ret.add(new ArrayList<>(tmp));}for (int col = 0; col < n; col++) {// 判断能不能放if (checkCol[col] == false && checkDig1[row - col + n] == false &&checkDig2[row + col] == false) {path[row][col] = 'Q';checkCol[col] = checkDig1[row - col + n] = checkDig2[row +col] = true;dfs(row + 1);// 恢复现场path[row][col] = '.';checkCol[col] = checkDig1[row - col + n] = checkDig2[row +col] = false;}}}
}11.有效的数独
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[][] row, 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;}
}12.解数独
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[][] row, 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);}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) == true)return true; // 重点理解// 恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;}}return false; // 重点理解}}}return true; // 重点理解}
}13.单词搜索
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[][] vis;int m, n;char[] word;public boolean exist(char[][] board, String _word) {m = board.length;n = board[0].length;word = _word.toCharArray();vis = new boolean[m][n];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))return true;vis[i][j] = false;}}return false;}int[] 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;}// 上下左右去匹配 word[pos]// 利⽤向量数组，⼀个 for 搞定上下左右四个⽅向for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && 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;}
}14.黄金矿工
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[][] vis;int m, n;int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };int ret;public int getMaximumGold(int[][] g) {m = g.length;n = g[0].length;vis = new boolean[m][n];for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (g[i][j] != 0) {vis[i][j] = true;dfs(g, i, j, g[i][j]);vis[i][j] = false;}}return ret;}public void dfs(int[][] g, int i, int j, int path) {ret = Math.max(ret, path);for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y] != 0) {vis[x][y] = true;dfs(g, x, y, path + g[x][y]);vis[x][y] = false;}}}
}15.不同路径3
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {boolean[][] vis;int m, n, step;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, 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;}step += 2;vis[bx][by] = true;dfs(grid, bx, by, 1);return ret;}public void dfs(int[][] grid, int i, int j, int count) {if (grid[i][j] == 2) {if (count == step) {ret++;}return;}for (int k = 0; k < 4; k++) {int x = i + dx[k], 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;}}}
}
