LeetCode 热题 HOT 100：回溯专题

LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/

文章目录

- 17. 电话号码的字母组合
- 22. 括号生成
- 39. 组合总和
- 46. 全排列
- 补充：47. 全排列 II （待优化)
- 78. 子集
- 79. 单词搜索
- 124. 二叉树中的最大路径和
- 200. 岛屿数量
- 437. 路径总和 III

17. 电话号码的字母组合

题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {List<String> list;Map<Character, String> map;public List<String> letterCombinations(String digits) {ap = new HashMap<>();res = new LinkedList<>();if(digits.length() == 0){return res;}map.put('2', "abc");map.put('3', "def");map.put('4', "ghi");map.put('5', "jkl");map.put('6', "mno");map.put('7', "pqrs");map.put('8', "tuv");map.put('9', "wxyz");backTrack(digits, 0, new StringBuilder());return list;}public void backTrack(String digits, int ind, StringBuilder sb){ // 参数：输入的字符串、字符串的索引、拼接的英文字符串if(digits.length() == ind){list.add(sb.toString());}else{char ch = digits.charAt(ind);String str = map.get(ch); // 获取按键下面的字符序列for (int i = 0; i < str.length(); i++) {sb.append(str.charAt(i));backTrack(digits, ind + 1, sb);sb.deleteCharAt(sb.length()-1); // 回溯}}}
}

参考题解：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

在这里插入图片描述

22. 括号生成

题目链接：https://leetcode.cn/problems/generate-parentheses/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

思路一：

class Solution {List<String> res;public List<String> generateParenthesis(int n) {res = new LinkedList<>();backTrack(n, 0, 0, "");return res;}public void backTrack(int n, int left, int right, String str){if(left < right){return;}if(left == n && right == n){res.add(str);return;}else{if(left < n){backTrack(n, left+1, right, str+"(");}backTrack(n, left, right+1, str+")");}}
}

思路二：

class Solution {List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n) {if(n<=0){return res;}getBracket("", n, n);return res;}public void getBracket(String str, int left, int right){if(left == 0 && right == 0){res.add(str);return;}if(left == right){getBracket(str+"(", left-1, right);}else{if(left > 0){getBracket(str+"(", left-1, right);}getBracket(str+")", left, right-1);}}
}

39. 组合总和

题目链接：https://leetcode.cn/problems/combination-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates, target, 0);return res;}public void dfs(int[] candidates, int target, int ind){ // 关键点在于索引if(target == 0){res.add(new ArrayList<>(list));return;}for(int i = ind; i < candidates.length; i ++){if(target - candidates[i] >= 0){list.add(candidates[i]);dfs(candidates, target - candidates[i], i); // 每次在当前的索引上进行遍历，作用在于：如果没有索引：target=5，5-3-2 作用等同于 5-2-3, 那么会有两种组合[2,3]与[3,2]// 但是在索引的约束下，不会出现这种情况 list.remove(list.size()-1);}}}
}

参考链接：https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
在这里插入图片描述

46. 全排列

题目链接：https://leetcode.cn/problems/permutations/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] visited = new boolean[nums.length]; // 标志数组dfs(nums, 0, visited);return res;}public void dfs(int[] nums, int size, boolean[] visited){if(size == nums.length){res.add(new ArrayList<>(list));return;}for(int i = 0; i < nums.length; i ++){if(!visited[i]){visited[i] = true;list.add(nums[i]);dfs(nums, size+1, visited);list.remove(list.size()-1); // 回溯visited[i] = false;}}}
}

参考链接：https://leetcode.cn/problems/permutations/solutions/9914/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

在这里插入图片描述

补充：47. 全排列 II （待优化)

题目链接：https://leetcode.cn/problems/permutations-ii/description/?envType=featured-list&envId=2cktkvj%3FenvType%3Dfeatured-list&envId=2cktkvj

class Solution {List<List<Integer>> res = new LinkedList<>();List<Integer> list = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] visited = new boolean[nums.length]; // 标志数组dfs(nums, 0, visited);return res;}public void dfs(int[] nums, int size, boolean[] visited){if(size == nums.length){for (List<Integer> result : res) {if(result.equals(list)){return;}}res.add(new ArrayList<>(list));return;}for(int i = 0; i < nums.length; i ++){if(!visited[i]){visited[i] = true;list.add(nums[i]);dfs(nums, size+1, visited);list.remove(list.size()-1);visited[i] = false;}}}
}

78. 子集

题目链接：https://leetcode.cn/problems/subsets/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return res;}public void dfs(int[] nums, int i){if(i==nums.length){res.add(new ArrayList(list));return;}// 选 nums[i]list.add(nums[i]);dfs(nums, i+1);// 不选 nums[i]list.remove(list.size()-1);dfs(nums, i+1);}
}

在这里插入图片描述

79. 单词搜索

题目链接：https://leetcode.cn/problems/word-search/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public boolean exist(char[][] board, String word) {for(int i = 0; i < board.length; i ++){for(int j = 0; j < board[0].length; j ++){if(board[i][j] == word.charAt(0)){if(dfs(board, i, j, word, 0)){ // 路径开头不一定只有一处，所以要遍历整个数组return true;}}}}return false;}public boolean dfs(char[][] board, int i, int j, String word, int ind){if(ind >= word.length()){return true;}if(i>=0 && i<board.length && j>=0 && j<board[0].length && board[i][j]==word.charAt(ind) && board[i][j]!='\0'){ // 剪枝char tmp = board[i][j];board[i][j] = '\0'; // 设置不可访问boolean f1 = dfs(board, i, j-1, word, ind+1); // 左boolean f2 = dfs(board, i-1, j, word, ind+1); // 上boolean f3 = dfs(board, i, j+1, word, ind+1); // 右boolean f4 = dfs(board, i+1, j, word, ind+1); // 下board[i][j] = tmp; // 回溯return f1 || f2 || f3 ||f4;}return false;}
}

124. 二叉树中的最大路径和

题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。最大的路径，可能的路径情况：
a
/ \
b c
① b + a + c。
② b + a + a 的父结点。（需要再次递归）
③ a + c + a 的父结点。（需要再次递归）
其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和，因此可以在递归过程中通过比较得出。
情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解。

class Solution {int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if(root == null){return 0;}dfs(root);return max;}/*** 返回经过root的单边分支最大和， 即 Math.max(root, root+left, root+right)*/public int dfs(TreeNode root){if(root == null){return 0;}// 计算左子树最大值，左边分支如果为负数还不如不选择int leftMax = Math.max(0, dfs(root.left));// 计算右子树最大值，右边分支如果为负数还不如不选择int rightMax = Math.max(0, dfs(root.right));// left->root->right 作为路径与已经计算过历史最大值做比较max = Math.max(max, leftMax + root.val + rightMax);// 返回经过root的单边最大分支给当前root的父节点计算使用return root.val + Math.max(leftMax, rightMax);}
}

200. 岛屿数量

题目链接：https://leetcode.cn/problems/number-of-islands/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public int numIslands(char[][] grid) {int sum = 0;for(int i = 0; i < grid.length; i ++){for(int j = 0; j < grid[0].length; j ++){if(grid[i][j] == '1'){dfs(grid, i, j);sum++;}}}return sum;}public void dfs(char[][] grid, int x, int y){if(0<=x && x<grid.length && 0<=y && y<grid[0].length && grid[x][y] == '1'){grid[x][y] ='0';dfs(grid, x, y-1); // 左dfs(grid, x-1, y); // 上dfs(grid, x, y+1); // 右dfs(grid, x+1, y); // 下}}
}

437. 路径总和 III

题目链接：https://leetcode.cn/problems/path-sum-iii/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {// key 是前缀和，value 是前缀和为这个值的路径数量。Map<Long, Integer> map = new HashMap<>();int target;public int pathSum(TreeNode root, int targetSum) {this.target = targetSum;// 可能路径从根节点开始算map.put(0l, 1);return dfs(root, 0l);}public int dfs(TreeNode root, long curSum){if(root == null){return 0;}curSum += root.val; // 当前累计的结点值int res = 0;// 以当前节点为止，去查看从前的 map 集合中是否还存在目标前缀和//              1//             ///            2//           ///          3// 假设目标和为 5// 节点 1 的前缀和为：1// 节点 3 的前缀和为: 1+2+3 = 6// pre(3) - pre(1) = 5// 所以从节点 1 到节点 3 之间有一条符合要求的路径res += map.getOrDefault(curSum-target, 0);// 存储路径的原因是可能节点的前缀和存在相等的情况：//              2//             ///            0//           ///          4// 从节点 2 到节点 4 有两条路径长度等于2map.put(curSum, map.getOrDefault(curSum, 0) + 1);int left = dfs(root.left, curSum); // 调用左子树int right = dfs(root.right, curSum); // 调用右子树res = res + left + right;map.put(curSum, map.get(curSum)-1); // 恢复状态return res;}
}