Backtracking (Java) - ShuweiLeung/Thinking GitHub Wiki
1.（784:Easy）Letter Case Permutation
- 该题就是一个简单的DFS/Backtracking的简单应用
2.（401:Easy）（非常经典题）Binary Watch
- 该题相当于从hour数组和minute数组两个数组中随机的选取num个数组成一个时间表示。为了使用backtracking/DFS，这里将两个数组合并成一个数组进行处理，为了区分hour和minute，将小时的数字在原来基础上全加上100，即8->108与分钟minute作区分。
- 此外该题中要求，对于任何一个时间，都用最少的指示灯来表示，所以，如果用多个指示灯来表示小时"12"或者分钟"60"，则为多余的时间表示，因为时间中"12=0"，"60=0"，因此对于hour>=12或minute>=60的时间枚举结果直接跳过。
- 该题的主要思路是：任意取num个数，那么对于hour和minute的合并数组，对每一个时间值都有"取"或"不取"两种表示，据此展开递归搜索
3.（526:Medium）（经典题）Beautiful Arrangement
- 该题的递归点在于：选取一个未使用过的且合适的数字放在当前的位置上。该题一开始同时记录了未使用的数字和搜索路径，非常复杂且耗时。其实只需要用一个长度为N+1的数组来记录数字的使用情况即可，当数组元素的值为0时代表未使用，1代表已使用。当使用当前的数字传入下一层递归时，待递归函数返回将该数字恢复成"未使用状态"，再尝试之后的数字即可，表述较抽象，参考下面的局部代码。
if (used[i] == 0 && (i % pos == 0 || pos % i == 0)) { //未使用且要满足beautiful的条件
used[i] = 1; //将其标记为已使用，并传给下一层
helper(N, pos + 1, used); //递归函数
used[i] = 0;//等下一层遍历结束再将该数字恢复为"未使用"
}
4+.（46:Medium）（非常非常经典题）Permutations
- 该题是一道非常非常非常经典的题目，之前在做Array类的与Permutations相关的题目时，参考答案是从后往前找第一个值减小的数字的方法，但这次做该题时，采用的是更一般化的思路。类似于第3题（526），我们对输入的Permutations的每一个数字都尝试放在当前位置上，参考代码如下：
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary ，因为不存在重复数字
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){ //遍历每一个数字，都尝试将其放在当前位置
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]); //将该数字放在当前位置
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1); //再将该数字恢复
}
}
}
下次复习一定要看上面的参考链接！！！
5+.（47:Medium）（非常非常经典题）Permutations II
- 该题是第4题（46）的变种，对于输入的序列，可能存在重复的元素。在上题的基础上，我们首先要将输入的数组排序，保证相同元素的位置相邻，这样便于之后的处理。此外，还需要设立一个used数组，used[i]代表输入数组nums[i]是否有使用过。之后，相同的思路，我们遍历每一个数字，都尝试将其放在当前位置。但区别是，因为重复元素的存在，为了避免相同结果的出现，需要作出如下定义：对于多个出现的相同数字，如"22"，必须第一个2被使用过后，才能使用第二个2，从而避免重复。类似于排列组合中，将相同值的元素看成一组，然后一组内再内部排序。而排序后使相同元素集中在一起，就是方便此处的处理。具体的代码参考如下：
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums); //因为存在重复数字，所以要将相同的数字全部排列在一起
boolean[] used = new boolean[nums.length];
backtrack(list, new ArrayList<>(), nums, used);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean[] used){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){ //遍历每一个数字，都尝试将其放在当前位置
//对于多个出现的相同数字，如"22"，必须第一个2被使用过后，才能使用第二个2，从而避免重复。类似于排列组合中，将相同值的元素看成一组，然后一组内再内部排序
if(used[i] == true || i>0 && used[i] == false && used[i-1] == false && nums[i] == nums[i-1])
continue;
used[i] = true;
tempList.add(nums[i]); //将该数字放在当前位置
backtrack(list, tempList, nums, used);
//恢复该数字
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}
6.（89:Medium）Gray Code
- 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
- 直接排列:以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。
- 镜射排列:n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到。
- 二进制数转格雷码（假设以二进制为0的值做为格雷码的0）G：格雷码 B：二进制码 : G(N) = (B(n)/2) XOR B(n)
- 本体采用G(N) = (B(n)/2) XOR B(n)的方式进行求解。
7.（77:Medium）（非常非常经典题）Combinations
- 该题其实和第4题（46）Permutations的思路一样，我们用一个used数组来标记元素是否被使用过，然后对K个数字进行枚举。但与第4题（46）的关键区别在于：(1,2) (2,1)被看作是相同的，即我们不关心排列顺序，只关注组合。因此，为了防止重复的组合出现，需要在递归搜索时设立一个start参数，每次枚举的值只能是大于等于start的元素。
- 注意：在向结果集中添加路径时，需要写res.add(new ArrayList<>(path))，即添加的是路径path的拷贝版本，因为path是一个指针，它所指的路径在之后还会变动，因此不能直接添加path本身。
8.（131:Medium）（经典题）Palindrome Partitioning
- 该题的递归点在于做切分的长度，所以尝试不同长度的切分，只要当前的切分是一个回文字符串，那么以该回文字符串的结束位置为新的索引起点进行下一层的递归搜索。
- 具体思路请参看代码实现。
9.（306:Medium）（经典题）Additive Number
- 该题的递归点在于切分多大长度的数字，在明确这个问题之后，便能以当前起始索引开始，分别以长度为1开始进行数字切割。
- 注意：1.切割的数字可能是大于Integer的最大值的，所以将字符串转化成数字要使用long型 2.当这一层递归的起始索引start指向的是字符'0'时，只能将其切割为数字0，若切割为数字0后不成功，则返回false 3.对于该题的test cases，最大切割长度限制为10即可
- 具体实现细节请参看代码实现。
10.（211:Medium）（非常经典题）Add and Search Word - Data structure design
- 该题考虑使用Map来存储words，key是单词的长度，value是具有该长度的单词集合。在存word时，根据单词长度存储到对应的集合中。在查找word时，如果word中没有'.'，则直接取出对应长度的word集合判断是否存在该单词，否则需要进行进一步的比较，具体比较思路见下：
boolean isSame(String a, String search){
if(a.length() != search.length()){
return false;
}
for(int i = 0; i < a.length(); i++){
if(search.charAt(i) != '.' && search.charAt(i) != a.charAt(i)){
return false;
}
}
return true;
}
该题是Design设计类型题目，discuss中更高效的参考答案是使用Trie，不懂该数据结构，下次复习时再研究
11.（51:Hard）（非常经典题）N-Queens
- N皇后问题：每一行、每一列、每一斜线都只能有一个Queen才符合条件。具体实现思路是：设立一个queens数组，长度为n，queens[i]代表第i行放的queen位于哪一列上。在递归搜索时，设立一个pos变量，代表当前递归层次处理的是第pos行的数据。我们其实无需担心"一行"上有多个queen，因为在实现时就控制一行上只能放一个queen，但需要用queens数组来控制"一列"和"对角线"上不能有多个queen。通过"如果两点的行之差(绝对值)等于列之差(绝对值) 那两点就在同一对角线上"来判断对角线上是否有多个queen。
- 具体的实现细节请直接参看代码、注释及参考链接。
- 参考链接：Edward中文讲解教程
12.（52:Hard）（非常经典题）N-Queens II
- 是第11题（51）的简化版，该题只要求给出N皇后问题的不同答案的数量，而第11题（51）要求给出具体的排列方案，所以该题只需要在第11题（51）的基础上返回结果集的大小即可。
<13???>.（212:Hard）（非常经典题）（数据结构不了解，未做）Word Search II
该题没有做，因为需要用到Trie的数据结构，该数据结构并不懂，需要下次复习时学习研究
<14???>.（126:Hard）（非常经典题）（解法较复杂，未做）Word Ladder II
该题同样是一道老生常谈的题，有很多解法，比较复杂未做，下次复习时再研究学习
15.（351:Medium）（非常非常经典题）Android Unlock Patterns
- The general idea is DFS all the possible combinations from 1 to 9 and skip invalid moves along the way.
- We can check invalid moves by using a jumping table. e.g. If a move requires a jump and the key that it is crossing is not visited, then the move is invalid. Furthermore, we can utilize symmetry to reduce runtime, in this case it reduced from ~120ms to ~70ms.
private int[][] jumps; // jumps[i][j]代表从数字i到数字j必须要经过的中间键
private boolean[] visited; //代表当前哪些数字已经visited过
public int numberOfPatterns(int m, int n) {
jumps = new int[10][10]; //jumps[i][j]初始化值为0
// 初始化jumps数组
jumps[1][3] = jumps[3][1] = 2;
jumps[4][6] = jumps[6][4] = 5;
jumps[7][9] = jumps[9][7] = 8;
jumps[1][7] = jumps[7][1] = 4;
jumps[2][8] = jumps[8][2] = 5;
jumps[3][9] = jumps[9][3] = 6;
jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
visited = new boolean[10];
int count = 0;
// 利用对称性来加速计算提高效率
count += DFS(1, 1, 0, m, n) * 4; // 1, 3, 7, 9 are symmetrical
count += DFS(2, 1, 0, m, n) * 4; // 2, 4, 6, 8 are symmetrical
count += DFS(5, 1, 0, m, n);
return count;
}
private int DFS(int num, int len, int count, int m, int n) {
if (len >= m && len <= n)
count++; // only count if moves are larger than m and less than n
if (len > n)
return count;
visited[num] = true;
for (int next = 1; next <= 9; next++) {
int jump = jumps[num][next];
if (!visited[next] && (jump == 0 || visited[jump])) {
count = DFS(next, len+1, count, m, n); //注意传入的是count，最后将外层的count值进行更新
}
}
visited[num] = false; // backtracking
return count;
}
16.（1087:Medium）（非常非常经典题）Brace Expansion
- 当一对多进行拼接时，直接在当前层进行遍历会使代码简洁，如果是多对一或一对一关系时，可以使用dfs进行拼接。参考代码如下：
public String[] expand(String S) {
List<String> res = new ArrayList<>();
dfs(S, 0, new StringBuilder(), res);
String[] out = new String[res.size()];
for (int i = 0; i < res.size(); i++) { out[i] = res.get(i); }
return out;
}
private void dfs(String s, int index, StringBuilder sb, List<String> res) {
if (index == s.length()) {
if (sb.length() > 0) { res.add(sb.toString()); }
return;
}
char c = s.charAt(index);
int position = sb.length();
if (c == '{') {
List<Character> charList = new ArrayList<>();
// 在当前层遍历{}中的字符会concise，而不是用递归
// 其实简化代码的地方在于如何遍历{}花括号中的字符，因为字符串是多对一对多的mapping关系，对于一对多关系
// 我们用while循环遍历所有可能的拼接，只有在一对一映射时采用dfs
int endIndex = index + 1;
while (endIndex < s.length() && s.charAt(endIndex) != '}') {
if (Character.isLetter(s.charAt(endIndex))) { charList.add(s.charAt(endIndex)); }
endIndex++;
}
Collections.sort(charList);
for (char d : charList) {
sb.append(d);
dfs(s, endIndex + 1, sb, res);
sb.setLength(position); //删除刚刚添加的字符,setLength相当于truncate
}
} else if (Character.isLetter(c)) {
sb.append(s.charAt(index));
dfs(s, index + 1, sb, res);
}
}
17.（980:Hard）（非常非常经典题）Unique Paths III
- First find out where the start and the end is. Also We need to know the number of empty cells因为题目要求我们在到达终点时需要遍历完所有的empty cells.
- We we try to explore a cell, it will change 0 to -2 and do a dfs in 4 direction.我们将cell的值改为-2作为已visited的标志。If we hit the target and pass all empty cells, increment the result.
18.（212:Hard）（非常非常经典题）Word Search II
- 该题是一道Trie和DFS结合在一起的题目，先将words中的单词全部存入一个trie树中，然后从board的每个位置出发，进行dfs，对每个搜索路径都查找Trie中是否有对应的valid的单词。
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
// Initialize your data structure here.
public TrieNode() {
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];
}
return node.item.equals(word);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];
}
return true;
}
}
Set<String> res = new HashSet<String>();
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
//先将words里的单词全部都存入Trie里面
for (String word : words) {
trie.insert(word);
}
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
//然后从board的每个字母出发进行遍历，判断搜索路径是否是一个有效的单词
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(board, visited, "", i, j, trie);
}
}
return new ArrayList<String>(res);
}
public void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) {
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
if (visited[x][y]) return;
str += board[x][y];
if (!trie.startsWith(str)) return;
if (trie.search(str)) {
res.add(str);
}
visited[x][y] = true;
dfs(board, visited, str, x - 1, y, trie);
dfs(board, visited, str, x + 1, y, trie);
dfs(board, visited, str, x, y - 1, trie);
dfs(board, visited, str, x, y + 1, trie);
visited[x][y] = false;
}
19.（1219:Medium）（非常经典题）Path with Maximum Gold
- The idea is so simple, using DFS vs Backtracking, try all possible paths, return the path with maxGold
- Time: O(4 * 3^k), k is the number of cells that have gold. k maximum is 25。Because the first cell has up to 4 choices, the (k-1) remain cells have up to 3 choices. And we make k different gold cells as first cell. So k * 4*3^(k-1) = 4 * 3^k
// Backtracking 保证visited过的位置不会重复访问
public int getMaximumGold(int[][] grid) {
int m = grid.length, n = grid[0].length;
int maxGold = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
maxGold = Math.max(maxGold, findMaxGold(grid, r, c));
return maxGold;
}
private static final int[] directions = new int[]{0, 1, 0, -1, 0};
private int findMaxGold(int[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) return 0;
int origin = grid[r][c];
grid[r][c] = 0; // mark as visited
int maxGold = 0;
for (int i = 0; i < 4; i++)
maxGold = Math.max(maxGold, findMaxGold(grid, directions[i] + r, directions[i+1] + c));
grid[r][c] = origin; // backtrack
return maxGold + origin;
}