Leetcode百题斩-回溯

回溯是一个特别经典的问题，也被排在了百题斩的第一部分，那么我们接下来来过一下这个系列。

这个系列一共八道题，偶然间发现我两年前还刷到这个系列的题，回忆起来当时刚经历淘系大变动与jf出走海外事件，大量同事离职闹得人心慌心慌，可能是当时也心生担忧于是未雨绸缪了一下。

不知不觉已经过了三年安稳的日子了，生于忧患死于安乐，该努力起来了

时间有点久远，记忆逐渐忘却了，之前用c++去攻取，那么这次用java重写一轮看看感觉如何

17. Letter Combinations of a Phone Number[medium]

思路：手机9键打字，根据按得数字枚举可能打印的字母。这个就是典型的递归，记录当前递归的位数，然后每位再扩展可能组成的字符串，最终位数到达结尾时结束

class Solution {private final List<String> phoneNumberLetter = Arrays.asList("abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz");public List<String> letterCombinations(String digits) {if (Objects.equals(digits, "")) {return Collections.emptyList();}return getLetter(0, digits, "");}public List<String> getLetter(Integer pos, String digits, String currentLetter) {List<String> newLetter = new ArrayList<>();int dLen = digits.length();if (pos == dLen) {newLetter.add(currentLetter);return newLetter;}int currentDigit = digits.charAt(pos) - '2';String currentChars = phoneNumberLetter.get(currentDigit);int cLen = currentChars.length();for (int i = 0; i < cLen; i++) {String newCurrentLetter = currentLetter + currentChars.charAt(i);newLetter.addAll(getLetter(pos + 1, digits, newCurrentLetter));}return newLetter;}
}

22. Generate Parentheses[medium]

思路：括号生成，给定括号数量，枚举可能出现的情况。这种，又是个按位递归的问题，但其实这次要记录的并不是位数，记录一下剩余左右括号的数量即可，因为需要保证左括号数量一定大于右括号数量。

class Solution {public List<String> generateParenthesis(int n) {return getParenthesis(n, n, "");}private List<String> getParenthesis(int leftNum, int rightNum, String currentString) {List<String> result = new ArrayList<>();if (rightNum == 0 && leftNum == 0) {result.add(currentString);return result;}if (rightNum - 1 >= leftNum) {result.addAll(getParenthesis(leftNum, rightNum - 1, currentString + ")"));}if (leftNum > 0) {result.addAll(getParenthesis(leftNum - 1, rightNum, currentString + "("));}return result;}
}

39. Combination Sum[medium]

思路：又是求特地和问题，但这次的区别就是，集合内的元素可以重复使用，且不限制顺序。要求枚举所有可能的情况。于是再来一个递归，将所需求和的数量作为递归参数，每个数字挨个往里面加即可，最后注意一下，因为集合问题，不用考虑顺序，于是直接按顺序添加，并再加一个位置变量来记录当前添加的字符即可。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {return combinationSum(candidates, target, 0);}private List<List<Integer>> combinationSum(int[] candidates, int target, int pos) {List<List<Integer>> result = new java.util.ArrayList<>();int len = candidates.length;for (int i = pos; i < len; i++) {int current = candidates[i];if (current >= target) {if (current == target) {result.add(new java.util.ArrayList<>(Collections.singletonList(current)));}continue;}combinationSum(candidates, target - current, i).forEach(list -> {list.add(current);result.add(list);});}return result;}
}

46. Permutations[medium]

思路：求全排列，这题如果用c++，可以直接用模板库，再方便不过了，但现在自己选择了用java，那就自己暴力写呗

依旧是递归位置，然后需要一个参数记录一下已经投入的变量集合，当然注意一下。由于这个变量共享，因此一定要在每轮递归结束的时候将变量清除

class Solution {public List<List<Integer>> permute(int[] nums) {return getPermutation(0, nums, new HashSet<>());}private List<List<Integer>> getPermutation(int pos, int[] nums, Set<Integer> used) {List<List<Integer>> result = new java.util.ArrayList<>();int len = nums.length;for (int i = 0; i < len; i++) {if (used.contains(i)) {continue;}used.add(i);int currentNum = nums[i];if (pos == len - 1) {List<Integer> list = new ArrayList<>();list.add(currentNum);result.add(list);used.remove(i);return result;} else {result.addAll(getPermutation(pos + 1, nums, used).stream().peek(list -> list.add(currentNum)).collect(Collectors.toList()));}used.remove(i);}return result;}
}

78. Subsets[Meduim]

思路：求集合的子集，这就是最经典的递归回溯问题了。按位回溯，每个位置回溯是否包含当前字符的两种情况

class Solution {public List<List<Integer>> subsets(int[] nums) {return getSubsets(0, nums);}private List<List<Integer>> getSubsets(int pos, int[] nums) {List<List<Integer>> result = new ArrayList<>();int len = nums.length;if (pos == len - 1) {List<Integer> list1 = new ArrayList<>();list1.add(nums[pos]);result.add(list1);List<Integer> list2 = new ArrayList<>();result.add(list2);return result;}result.addAll(getSubsets(pos + 1, nums).stream().peek(list -> list.add(nums[pos])).collect(Collectors.toList()));result.addAll(getSubsets(pos + 1, nums));return result;}
}

79. Word Search[Medium]

思路：棋盘搜索问题，二维递归回溯的经典问题，回溯四个方向即可，注意一下为了避免往回回溯形成死循环，每次回溯点需要抹掉，回溯完成后恢复即可

class Solution {public boolean exist(char[][] board, String word) {int xLen = board.length;for (int i = 0; i < xLen; i++) {int yLen = board[i].length;for (int j = 0; j < yLen; j++) {if (search(i, j, board, word, 0)) {return true;}}}return false;}private boolean search(int x, int y, char[][] board, String word, int pos) {char currentChar = board[x][y];//System.out.println(x + "*" + y + "*" + currentChar + "*" + pos);if (board[x][y] != word.charAt(pos)) {return false;}board[x][y] = 0;boolean bingo = false;if (pos == word.length() - 1) {bingo = true;} else if (x > 0 && search(x - 1, y, board, word, pos + 1)) {bingo = true;} else if (y > 0 && search(x, y - 1, board, word, pos + 1)) {bingo = true;} else if (x < board.length - 1 && search(x + 1, y, board, word, pos + 1)) {bingo = true;} else if (y < board[x].length - 1 && search(x, y + 1, board, word, pos + 1)) {bingo = true;}board[x][y] = currentChar;return bingo;}
}

131. Palindrome Partitioning[Medium]

思路：将字符串分割成多个回文子串，求所有分割方案。其实分隔子串这类问题，首先想到的就是递归回溯。按位进行回溯，从每个位置开始，先枚举添加的回文串，再递归剩余的子串。至于回文串判断，这里就采用最暴力的双指针进行判断，为了避免重复，将已经判断过的结果进行持久化记录一下。如果想优化预处理回文串，可以看之前的一篇回文串的文章，那里介绍了从立方复杂度的暴力求法到最佳常数复杂度的Manarch算法。

class Solution {private Map<String, Boolean> palindromeSet = new HashMap<>();public List<List<String>> partition(String s) {List<List<String>> result = getPartition(s, 0);result.forEach(Collections::reverse);return result;}private List<List<String>> getPartition(String s, int pos) {List<List<String>> result = new ArrayList<>();int len = s.length();if (pos == len) {List<String> endResult = new ArrayList<>();result.add(endResult);return result;}for (int i = pos; i < len; i++) {String current = s.substring(pos, i + 1);if (isPalindrome(current)) {List<List<String>> partition = getPartition(s, i + 1);for (List<String> list : partition) {list.add(current);}result.addAll(partition);}}return result;}private boolean isPalindrome(String s) {if (palindromeSet.containsKey(s)) {return palindromeSet.get(s);}int left = 0;int right = s.length() - 1;boolean palindrome = true;while (left <= right) {if (s.charAt(left) != s.charAt(right)) {palindrome = false;break;}left++;right--;}palindromeSet.put(s, palindrome);return palindrome;}
}

51. N-Queens[Hard]

思路：N皇后问题，可以算是递归回溯系列经典中的经典。给定边长为N的棋盘大小，要求所有能摆出N个不相攻击的皇后摆法（皇后可以任意横着走或者斜着走）。这题显然需要遍历每个棋格去进行递归，递归时维护已经摆上的皇后数量，所需的皇后数量，以及当前棋盘的状态。当摆上皇后时，遍历更新棋盘，标记不可继续放置棋盘的位置。由于棋盘需要反复被标记，导致复杂度变高，这里根据皇后的特性不难发现，只需要维护三个集合 ，即可分别表示皇后所在列，以及所在的两个斜线，从而避免反复标记棋盘。而针对皇后所在行，每次放置皇后时跳到下一行即可避免同行皇后。此外，由于按顺序遍历所有棋格，因此可以直接用一维字符数组代替二维棋盘，最后转换一下即可表示棋盘最终形态

class Solution {public List<List<String>> solveNQueens(int n) {char[] board = new char[n * n];for (int i = 0; i < n * n; i++) {board[i] = '.';}Set<Integer> s1 = new HashSet<>();Set<Integer> s2 = new HashSet<>();Set<Integer> s3 = new HashSet<>();return getNQueens(0, board, 0, n, s1, s2, s3);}private List<List<String>> getNQueens(int pos, char[] board, int now, int n, Set<Integer> s1,Set<Integer> s2, Set<Integer> s3) {List<List<String>> result = new ArrayList<>();if (now == n) {List<String> endResult = getResult(board, n);result.add(endResult);return result;} else if (pos >= n * n) {return Collections.emptyList();}int x = pos / n;int y = pos % n;if (!s1.contains(x + y) && !s2.contains(x - y) && !s3.contains(y)) {board[pos] = 'Q';s1.add(x + y);s2.add(x - y);s3.add(y);int nextPos = (x + 1) * n;result.addAll(getNQueens(nextPos, board, now + 1, n, s1, s2, s3));s1.remove(x + y);s2.remove(x - y);s3.remove(y);board[pos] = '.';}result.addAll(getNQueens(pos + 1, board, now, n, s1, s2, s3));return result;}private List<String> getResult(char[] board, int n) {List<String> result = new ArrayList<>();for (int i = 0; i < n; i++) {StringBuilder sb = new StringBuilder();for (int j = 0; j < n; j++) {sb.append(board[i * n + j]);}result.add(sb.toString());}return result;}
}

最终，递归回溯完结