17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
回溯算法
class Solution {Map<String, String> map = new HashMap<String, String>() {{put("2", "abc");put("3", "def");put("4", "ghi");put("5", "jkl");put("6", "mno");put("7", "pqrs");put("8", "tuv");put("9", "wxyz");}};List<String> out = new ArrayList<String>();private void backtrack(String combination, String digits){if (digits.length() == 0){out.add(combination);} else {String digit = digits.substring(0, 1);String letters = map.get(digit);for (int i = 0; i < letters.length(); ++i){String letter = letters.substring(i, i + 1);backtrack(combination + letter, digits.substring(1));}}}public List<String> letterCombinations(String digits) {if (digits.length() != 0){backtrack("", digits);}return out;}}
93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
回溯
class Solution {
int n;
String s;
List<String> res = new ArrayList<>();
Deque<String> segments = new LinkedList<>();
private boolean valid(String segment) {
int m = segment.length();
if (m > 3) {
return false;
}
return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : m == 1;
}
private void updateOutput(int curPos) {
String segment = s.substring(curPos + 1, n);
if (valid(segment)) {
segments.add(segment);
res.add(String.join(".", segments));
segments.removeLast();
}
}
private void backtrace(int prev, int dots) {
int maxPos = Math.min(prev + 4, n - 1);
for (int cur = prev + 1; cur < maxPos; cur++) {
String segment = s.substring(prev + 1, cur + 1);
if (valid(segment)) {
segments.add(segment);
if (dots == 1) {
updateOutput(cur);
} else {
backtrace(cur, dots - 1);
}
segments.removeLast();
}
}
}
public List<String> restoreIpAddresses(String s) {
n = s.length();
this.s = s;
backtrace(-1, 3);
return res;
}
}
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.
回溯算法
class Solution {
private int m, n;
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
m = board.length;
n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(0, i, j, visited, board, word)) {
return true;
}
}
}
return false;
}
private boolean dfs(int curLen, int row, int col, boolean[][] visited, char[][] board, String word) {
if (curLen == word.length()) {
return true;
}
if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != word.charAt(curLen) || visited[row][col]) {
return false;
}
visited[row][col] = true;
for (int[] d : directions) {
if (dfs(curLen + 1, row + d[0], col + d[1], visited, board, word)) {
return true;
}
}
visited[row][col] = false;
return false;
}
}
257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/
2 3
5
输出: [“1->2->5”, “1->3”]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
回溯
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private void backtrace(TreeNode node, List<String> res, List<Integer> values) {
if (node == null) {
return;
}
values.add(node.val);
if (isLeaf(node)) {
res.add(buildPath(values));
} else {
backtrace(node.left, res, values);
backtrace(node.right, res, values);
}
values.remove(values.size() - 1);
}
private boolean isLeaf(TreeNode node) {
return node.left == null && node.right == null;
}
private String buildPath(List<Integer> values) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.size(); i++) {
sb.append(values.get(i));
if (i != values.size() - 1) {
sb.append("->");
}
}
return sb.toString();
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
List<Integer> values = new ArrayList<>();
backtrace(root, res, values);
return res;
}
}
46. 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯算法
class Solution {
private void backtrack(List<Integer> permute, List<List<Integer>> permutes, boolean[] visited, int[] nums) {
if (permute.size() == nums.length) {
permutes.add(new ArrayList<>(permute));
return;
}
for (int i = 0; i < visited.length; ++i) {
if (visited[i]) {
continue;
}
visited[i] = true;
permute.add(nums[i]);
backtrack(permute, permutes, visited, nums);
permute.remove(permute.size() - 1);
visited[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permute = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
backtrack(permute, permutes, visited, nums);
return permutes;
}
}
47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
回溯算法
在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。
class Solution {
private void backtrack(List<List<Integer>> permutes, List<Integer> permute, boolean[] visited, int[] nums) {
if (permute.size() == nums.length) {
permutes.add(new ArrayList<>(permute));
return;
}
for (int i = 0; i < nums.length; ++i){
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
if (visited[i]) {
continue;
}
visited[i] = true;
permute.add(nums[i]);
backtrack(permutes, permute, visited, nums);
permute.remove(permute.size() - 1);
visited[i] = false;
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permute = new ArrayList<>();
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
backtrack(permutes, permute, visited, nums);
return permutes;
}
}
剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
回溯
class Solution {
List<String> res = new LinkedList<>();
char[] c;
private void dfs(int x) {
if (x == c.length -1) {
res.add(String.valueOf(c));
return;
}
HashSet<Character> set = new HashSet<>();
for (int i = x; i < c.length; i++) {
if (set.contains(c[i])) {
continue;
}
set.add(c[i]);
swap(i, x);
dfs(x + 1);
swap(i, x);
}
}
private void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
}
77. 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
回溯算法
按照上面的套路，不过不是最优的方法。
class Solution {
private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int n, int k, boolean[] visited) {
if (combination.size() == k) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = 1; i <= n; ++i) {
if (visited[i]) {
return;
}
visited[i] = true;
combination.add(i);
backtrack(combinations, combination, n, k, visited);
combination.remove(combination.size() - 1);
visited[i] = false;
}
}
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
boolean[] visited = new boolean[n + 1];
backtrack(combinations, combination, n, k, visited);
return combinations;
}
}
回溯
稍微优化一下
class Solution {
private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
if (combination.size() == k) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = start; i <= n; i++) {
combination.add(i);
backtrace(combinations, combination, i + 1, n, k);
combination.remove(combination.size() - 1);
}
}
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
backtrace(combinations, combination, 1, n, k);
return combinations;
}
}
剪枝操作
关于剪枝操作的讲解部分见https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
class Solution {
private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
if (k == 0) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = start; i <= n - k + 1; ++i) { // 剪枝操作
combination.add(i);
backtrack(combinations, combination, i + 1, n, k - 1);
combination.remove(combination.size() - 1);
}
}
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
boolean[] visited = new boolean[n + 1];
backtrack(combinations, combination, 1, n, k);
return combinations;
}
}
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
回溯算法
class Solution {
private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int[] candidates, int target) {
if (target == 0) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < candidates.length; i++) {
int temp = candidates[i];
if (temp <= target) {
combination.add(temp);
backtrace(combinations, combination, i, candidates, target - temp);
combination.remove(combination.size() - 1);
}
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtrace(combinations, new ArrayList<>(), 0, candidates, target);
return combinations;
}
}
40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
回溯、剪枝
class Solution {
private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int[] candidates, int target, boolean[] visited) {
if (target == 0) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < candidates.length; i++) {
int temp = candidates[i];
if (i != 0 && candidates[i - 1] == candidates[i] && !visited[i - 1]) {
continue;
}
if (temp <= target) {
visited[i] = true;
combination.add(temp);
backtrace(combinations, combination, i + 1, candidates, target - temp, visited);
combination.remove(combination.size() - 1);
visited[i] = false;
} else {
break;
}
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
Arrays.sort(candidates);
boolean[] visited = new boolean[candidates.length];
backtrace(combinations, combination, 0, candidates, target, visited);
return combinations;
}
}
回溯，不需要visited
import java.util.*;
public class Solution {
private ArrayList<ArrayList<Integer>> res;
private ArrayList<Integer> cur;
private void backtrace(int[] num, int target, int start) {
if (target == 0) {
res.add(new ArrayList(cur));
return;
}
for (int i = start; i < num.length; i++) {
int temp = num[i];
// i > start是关键
if (i > start && num[i - 1] == num[i] ) {
continue;
}
if (temp <= target) {
cur.add(temp);
backtrace(num, target - temp, i + 1);
cur.remove(cur.size() - 1);
} else {
break;
}
}
}
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
res = new ArrayList();
cur = new ArrayList();
Arrays.sort(num);
backtrace(num, target, 0);
return res;
}
}
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
回溯算法
class Solution {
int num;
private void backtrace(List<List<Integer>> combinations, List<Integer> combination, int start, int k, int n) {
if (n == 0 && combination.size() == num) {
combinations.add(new ArrayList<>(combination));
return;
}
for (int i = start; i <= 9 - k + 1; i++) {
if (i <= n) {
combination.add(i);
backtrace(combinations, combination, i + 1, k - 1, n - i);
combination.remove(combination.size() - 1);
} else {
break;
}
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> combinations = new ArrayList<>();
num = k;
backtrace(combinations, new ArrayList<>(), 1, k, n);
return combinations;
}
}
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
回溯算法
class Solution {
private void backtrace(List<List<Integer>> result, List<Integer> temp, int start, int[] nums, int size) {
if (temp.size() == size) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
backtrace(result, temp, i + 1, nums, size);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) {
backtrace(result, new ArrayList<>(), 0, nums, i);
}
return result;
}
}
90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
回溯算法
class Solution {
private void backtrace(List<List<Integer>> result, List<Integer> temp, int start, int[] nums, int size, boolean[] visited) {
if (temp.size() == size) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i - 1] == nums[i] && !visited[i - 1]) {
continue;
}
visited[i] = true;
temp.add(nums[i]);
backtrace(result, temp, i + 1, nums, size, visited);
visited[i] = false;
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
for (int i = 0; i <= nums.length; i++) {
backtrace(result, new ArrayList<>(), 0, nums, i, visited);
}
return result;
}
}
剑指 Offer 12. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
回溯
class Solution {
private int m, n;
private int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
m = board.length;
n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(0, i, j, visited, board, word)) {
return true;
}
}
}
return false;
}
private boolean dfs(int curLen, int r, int c, boolean[][] visited, char[][] board, String word) {
if (curLen == word.length()) {
return true;
}
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) {
return false;
}
visited[r][c] = true;
for (int[] d : direction) {
if (dfs(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
return true;
}
}
visited[r][c] = false;
return false;
}
}
131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]
回溯算法
class Solution {
private boolean check(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
return true;
}
private void backtrace(List<List<String>> result, List<String> temp, String s) {
if (s.length() == 0) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < s.length(); i++) {
if (check(s, 0, i)) {
temp.add(s.substring(0, i + 1));
backtrace(result, temp, s.substring(i + 1));
temp.remove(temp.size() - 1);
}
}
}
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrace(result, new ArrayList<>(), s);
return result;
}
}
301. 删除无效的括号
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:
输入: ")("
输出: [""]
回溯算法
class Solution {
Set<String> set = new HashSet<>();
int maxLen = 0;
public List<String> removeInvalidParentheses(String s) {
int rmLeft = 0, rmRight = 0;
// 1、对于括号，有选和不选两种情况；对于字母，必须选
// 2、用计数器维护字符串状态，"("则加一，")"则减一
// 3、set去重
// 4、提前计算应当删除的左括号或者右括号的数量，用于剪枝
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
rmLeft++;
} else if (s.charAt(i) == ')'){
if (rmLeft > 0) {
rmLeft--;
} else {
rmRight++;
}
}
}
helper(s, 0, 0, new StringBuilder(), rmLeft, rmRight);
return new ArrayList<>(set);
}
private void helper(String s, int idx, int count, StringBuilder path, int rmLeft, int rmRight) {
if (count < 0 || rmLeft < 0 || rmRight < 0) {
return;
}
if (idx == s.length()) {
if (count == 0 && rmLeft == 0 && rmRight == 0) {
if (path.length() >= maxLen) {
maxLen = path.length();
set.add(path.toString());
}
}
return;
}
// 添加当前字符到path中
char c = s.charAt(idx);
path.append(c);
if (c == '(') {
helper(s, idx + 1, count + 1, path, rmLeft, rmRight);
} else if (c == ')') {
helper(s, idx + 1, count - 1, path, rmLeft, rmRight);
} else {
helper(s, idx + 1, count, path, rmLeft, rmRight);
}
// 不添加当前字符到path中
path.deleteCharAt(path.length() - 1);
if (c == '(') {
helper(s, idx + 1, count, path, rmLeft - 1, rmRight);
} else if (c == ')') {
helper(s, idx + 1, count, path, rmLeft, rmRight - 1);
}
}
}
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
递归
- 左右括号数为0，添加结果
- 左右括号数相等，只能添加”（“
- 左右括号数不相等，可以添加“(”也可以添加“)”
class Solution {
ArrayList<String> result;
public List<String> generateParenthesis (int n) {
// write code here
result = new ArrayList<>();
if (n <= 0) {
return result;
}
getParenthesis("", n, n);
return result;
}
private void getParenthesis(String s, int left, int right) {
if (left == 0 && right == 0) {
result.add(s);
return;
}
if (left == right) {
getParenthesis(s + "(", left - 1, right);
} else {
if (left > 0) {
getParenthesis(s + "(", left - 1, right);
}
getParenthesis(s + ")", left, right - 1);
}
}
}
37. 解数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
Note:
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
回溯算法
详细题解见https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/
class Solution {
private int n = 3;
private int N = n * n;
private int[][] rows = new int[N][N+1];
private int[][] cols = new int[N][N+1];
private int[][] boxes = new int[N][N+1];
private char[][] board;
private boolean solved = false;
private boolean checkPlace(int d, int row, int col) {
int index = (row / n) * n + col / n;
return rows[row][d] + cols[col][d] + boxes[index][d] == 0;
}
private void placeNumber(int d, int row, int col) {
int index = (row / n) * n + col / n;
rows[row][d]++;
cols[col][d]++;
boxes[index][d]++;
board[row][col] = (char)(d + '0');
}
private void removeNumber(int d, int row, int col) {
int index = (row / n) * n + col / n;
rows[row][d]--;
cols[col][d]--;
boxes[index][d]--;
board[row][col] = '.';
}
private void placeNextNumber(int row, int col) {
if (row == N - 1 && col == N - 1) {
solved = true;
} else {
if (col == N - 1) {
backtrack(row + 1, 0);
} else {
backtrack(row, col + 1);
}
}
}
private void backtrack(int row, int col) {
if (board[row][col] == '.') {
for (int d = 1; d <= N; d++) {
if (checkPlace(d, row, col)) {
placeNumber(d, row, col);
placeNextNumber(row, col);
if (!solved) {
removeNumber(d, row, col);
}
}
}
} else {
placeNextNumber(row, col);
}
}
public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
char num = board[i][j];
if (num != '.') {
int d = Character.getNumericValue(num);
placeNumber(d, i, j);
}
}
}
backtrack(0, 0);
}
}
还有一种效率更高的方法，选择的格子（’.’）在一行、一列和一个九宫格中可选数字最少的格子开始填数字。这样能更快找到结果。
剪枝条件:我们应该选择的格子（'.'）在一行、一列和一个九宫格中可选数字最少的格子开始填数字。
对于每行、每列和每个9宫格都可以用一个9位的2进制数字来标识该行（列，9宫格）那些数字可以填。
用1表示可填0表示不可填
如例题中第一行 ：["5","3",".",".","7",".",".",".","."]
第一行中 有数字 5 3 7
下标 8 7 6 5 4 3 2 1 0
二进制数 1 1 0 1 0 1 0 1 1
因为5 3 7 已经有了，所以第一行1 2 4 6 8 9可填
一共有9行所以用9个int表示行row[9],同理9列col[9],9个9宫格cell[3][3]
class Solution {
final int N = 9;
int[] row = new int [N], col = new int [N];
//ones数组表示0~2^9 - 1的整数中二进制表示中1的个数:如ones[7] = 3 ones[8] = 1
//map数组表示2的整数次幂中二进制1所在位置（从0开始） 如 map[1] = 0,map[2] = 1, map[4] = 2
int[] ones = new int[1 << N], map = new int[1 << N];
int[][] cell = new int[3][3];
public void solveSudoku(char[][] board) {
init();
int cnt = fill_state(board);
dfs(cnt, board);
}
void init(){
for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cell[i][j] = (1 << N) - 1;
//以上2个循环把数组的数初始化为二进制表示8个1，即一开始所以格子都可填
for(int i = 0; i < N; i++) map[1 << i] = i;
//统计0~2^9 - 1的整数中二进制表示中1的个数
for(int i = 0; i < 1 << N; i++){
int n = 0;
for(int j = i; j != 0; j ^= lowBit(j)) n++;
ones[i] = n;
}
}
int fill_state(char[][] board){
int cnt = 0; //统计board数组空格('.')的个数
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(board[i][j] != '.'){
int t = board[i][j] - '1';
//数独中 i,j位置为数组下标，修改row col cell数组中状态
change_state(i, j, t);
}else cnt++;
}
}
return cnt;
}
boolean dfs(int cnt, char[][] board){
if(cnt == 0) return true;
int min = 10, x = 0, y = 0;
//剪枝，即找出当前所以空格可填数字个数最少的位置 记为x y
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(board[i][j] == '.'){
int k = ones[get(i, j)];
if(k < min){
min = k;
x = i;
y = j;
}
}
}
}
//遍历当前 x y所有可选数字
for(int i = get(x, y); i != 0; i ^= lowBit(i)){
int t = map[lowBit(i)];
change_state(x, y, t);
board[x][y] = (char)('1' + t);
if(dfs(cnt - 1, board)) return true;
//恢复现场
change_state(x, y, t);
board[x][y] = '.';
}
return false;
}
void change_state(int x, int y, int t){
row[x] ^= 1 << t;
col[y] ^= 1 << t;
cell[x / 3][y / 3] ^= 1 << t;
}
//对维护数组x行,y列的3个集合(行、列、九宫格)进行&运算
//就可以获得可选数字的集合(因为我们用1标识可填数字)
int get(int x, int y){
return row[x] & col[y] & cell[x / 3][y / 3];
}
int lowBit(int x){
return -x & x;
}
}
//作者：ri-mu-tu-yuan-12
51. N皇后
51. N 皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[“.Q..”, // 解法 1
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q..”]
]
解释: 4 皇后问题存在两个不同的解法。
回溯算法
在 nn 的矩阵中摆放 n 个皇后，并且每个皇后不能在同一行，同一列，同一对角线上，求所有的 n 皇后的解。
一行一行地摆放，在确定一行中的那个皇后应该摆在哪一列时，需要用三个标记数组来确定某一列是否合法，这三个标记数组分别为：列标记数组、45 度对角线标记数组和 135 度对角线标记数组。
45 度对角线标记数组的长度为 2 n - 1，通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。
135 度对角线标记数组的长度也是 2 * n - 1，(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。
class Solution {
private List<List<String>> result;
private char[][] nQueens;
private boolean[] colUsed;
private boolean[] diagonal1; //45度对角线
private boolean[] diagonal2; //135度对角线
private int n;
private void backtrack(int row) {
if (row == n) {
List<String> temp = new ArrayList<>();
for (char[] chars : nQueens) {
temp.add(new String(chars));
}
result.add(temp);
return;
}
for (int col = 0; col < n; col++) {
int index1 = col + row; //45度对角线索引
int index2 = n - 1 - (row - col); //135度对角线索引
if (colUsed[col] || diagonal1[index1] || diagonal2[index2]) {
continue;
}
nQueens[row][col] = 'Q';
colUsed[col] = diagonal1[index1] = diagonal2[index2] = true;
backtrack(row + 1);
colUsed[col] = diagonal1[index1] = diagonal2[index2] = false;
nQueens[row][col] = '.';
}
}
public List<List<String>> solveNQueens(int n) {
result = new ArrayList<>();
nQueens = new char[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(nQueens[i], '.');
}
colUsed = new boolean[n];
diagonal1 = new boolean[2 * n - 1];
diagonal2 = new boolean[2 * n - 1];
this.n = n;
backtrack(0);
return result;
}
}
若有收获，就点个赞吧
0 人点赞
