• 回溯系列--11个题

    组合问题

    第77题. 组合

    题⽬链接：https://leetcode-cn.com/problems/combinations/

    给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

    ⽰例: 输⼊: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

    1. class Solution {
    2.  
    3.     List> result = new ArrayList<>();
    4.     // List path = new ArrayList<>(); LinkedList增添的时间复杂度更低
    5.     LinkedList path = new LinkedList<>(); 
    6.  
    7.     public List> combine(int n, int k) {
    8.         // backtraking(n, k, 0);  返回范围 [1, n] 中所有可能的 k 个数的组合。所以index从1开始
    9.         backtraking(n, k, 1);
    10.         return result;
    11.     }
    12.  
    13.     void backtraking(int n, int k, int index) {
    14.         if(path.size() == k) {
    15.             // result.add(path); new ArrayList<>() 将LinkedList类型的path转换为ArrayList类型
    16.             result.add(new ArrayList<>(path));
    17.             return;
    18.         }
    19.  
    20.         for(int i = index; i <= n; i++){
    21.             path.add(i);
    22.             // backtraking(n, k , index + 1);
    23.             backtraking(n, k ,i + 1);
    24.             path.remove(path.size() - 1);
    25.             // path.removeLast();
    26.         }
    27.     }
    28. }

    第216题.组合总和III

    链接：https://leetcode-cn.com/problems/combination-sum-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]]

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> combinationSum3(int k, int n) {
    6.         backtracking(k, n, 0, 1);
    7.         return result;
    8.     }
    9.     
    10.     void backtracking(int k, int n,int sum, int index) {
    11.         if(sum == n && path.size() == k) {
    12.             result.add(new ArrayList<>(path));
    13.             return;
    14.         }
    15.  
    16.         for(int i = index; i <= 9 && n >= sum + i; i++) {
    17.             path.add(i);
    18.             sum += i;
    19.             backtracking(k, n, sum, i + 1);
    20.             sum -= i;
    21.             path.remove(path.size() - 1);
    22.         }
    23.     }
    24. }

    17.电话号码的字母组合

    题⽬链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

    给定⼀个仅包含数字 2-9 的字符串，返回所有它能表⽰的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    ⽰例: 输⼊："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

    说明：尽管上⾯的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

    1. class Solution {
    2.      String[] letterMap = new String[]{
    3.             "",//0
    4.             "",//1
    5.             "abc",//2
    6.             "def",//3
    7.             "ghi",//4
    8.             "jkl",//5
    9.             "mno",//6
    10.             "pqrs",//7
    11.             "tuv",//8
    12.             "wxyz"//9
    13.         };
    14.     List result = new ArrayList<>();
    15.     StringBuilder path = new StringBuilder();
    16.     public List letterCombinations(String digits) {
    17.         if(digits == null || digits.length() == 0) return result;
    18.        backTracking(digits, 0);
    19.        return result;
    20.     }
    21.  
    22.     void backTracking(String digits, int index) {
    23.         if(index == digits.length()) {
    24.             result.add(path.toString());
    25.             return;
    26.         }
    27.         String s = letterMap[digits.charAt(index) - '0'];
    28.         for(int i = 0; i < s.length(); i++){ //对每个按键的水平遍历
    29.             path.append(s.charAt(i));
    30.             backTracking(digits, index + 1); //对不同按键的深度递归
    31.             path.deleteCharAt(path.length() - 1);
    32.         }
    33.     }
    34. }

    39. 组合总和

    题⽬链接：https://leetcode-cn.com/problems/combination-sum/

    给定⼀个⽆重复元素的数组 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] ]

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.     public List> combinationSum(int[] candidates, int target) {
    5.         Arrays.sort(candidates);
    6.         backtracking(candidates, target, 0, 0);
    7.         return result;
    8.     }
    9.  
    10.     void backtracking(int[] candidates, int target, int sum, int index) {
    11.         if(target == sum) {
    12.             // result.add(path);
    13.             result.add(new ArrayList<>(path));
    14.             return;
    15.         }
    16.  
    17.         for(int i = index; i < candidates.length && target >= sum + i; i++){ //target >= sum + i要提前排序
    18.             path.add(candidates[i]);
    19.             sum += candidates[i];
    20.             backtracking(candidates, target, sum, i);
    21.             sum -= candidates[i];
    22.             path.remove(path.size() - 1);
    23.         }
    24.     }
    25. }

    40.组合总和II

    题⽬链接：https://leetcode-cn.com/problems/combination-sum-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] ]

    1. class Solution {
    2.     // public List> combinationSum2(int[] candidates, int target) {
    3.         List> result = new ArrayList<>();
    4.     LinkedList path = new LinkedList<>();
    5.     boolean[] used;
    6.     public List> combinationSum2(int[] candidates, int target) {
    7.         used = new boolean[candidates.length];
    8.         Arrays.fill(used, false);
    9.         Arrays.sort(candidates);
    10.         backtracking(candidates, target, 0, 0);
    11.         return result;
    12.     }
    13.  
    14.     void backtracking(int[] candidates, int target, int sum, int index) {
    15.         if(target == sum) {
    16.             // result.add(path);
    17.             result.add(new ArrayList<>(path));
    18.             return;
    19.         }
    20.  
    21.         // for(int i = index; i < candidates.length && target >= sum + i; i++){ //target >= sum + i要提前排序
    22.         for(int i = index; i < candidates.length && target >= sum + candidates[i]; i++){
    23.         // if(i > 0 && candidates[i-1] == candidates[i] && used[i - 1] == false){
    24.             if(i > 0 && candidates[i-1] == candidates[i] && used[i - 1] == false){
    25.             continue;
    26.         }
    27.             path.add(candidates[i]);
    28.             sum += candidates[i];
    29.             used[i] = true;
    30.             backtracking(candidates, target, sum, i + 1);
    31.             used[i] = false;
    32.             sum -= candidates[i];
    33.             path.remove(path.size() - 1);
    34.         }
    35.     }
    36.     }

    分割问题

    131.分割回⽂串

    题⽬链接：https://leetcode-cn.com/problems/palindrome-partitioning/

    给定⼀个字符串 s，将 s 分割成⼀些⼦串，使每个⼦串都是回⽂串。 返回 s 所有可能的分割⽅案。

    ⽰例: 输⼊: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.     public List> partition(String s) {
    5.         backtracking(s, 0);
    6.         return result;
    7.     }
    8.  
    9.     void backtracking(String s, int index) {
    10.         if(index == s.length()) {
    11.             // result.add(path);
    12.             result.add(new ArrayList(path));
    13.             return;
    14.         }
    15.  
    16.         for(int i = index; i < s.length(); i++) {
    17.             if(isvalid(s, index ,i)) {
    18.                 //  path.add(s.subStr(i, index));
    19.                 // path.add(s.substring(i+1, index));
    20.                 path.add(s.substring(index, i+1));
    21.                 backtracking(s, i+1);
    22.                 path.removeLast();
    23.             }else {
    24.                 continue;
    25.             }
    26.              
    27.         }
    28.  
    29.     }
    30.     
    31.         boolean isvalid(String s, int startIndex, int end) {
    32.         for (int i = startIndex, j = end; i < j; i++, j--) {
    33.             if (s.charAt(i) != s.charAt(j)) {
    34.                 return false;
    35.             }
    36.         }
    37.         return true;
    38.     }
    39. }

    子集问题

    第78题. ⼦集

    题⽬地址：https://leetcode-cn.com/problems/subsets/

    给定⼀组不含重复元素的整数数组 nums，返回该数组所有可能的⼦集（幂集）。

    说明：解集不能包含重复的⼦集。 

    ⽰例: 输⼊: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.    
    5.     public List> subsets(int[] nums) {
    6.         
    7.         backStraking(nums, 0);
    8.         return result;
    9.     }
    10.  
    11.     void backStraking(int[] nums, int index) {
    12.         result.add(new ArrayList<>(path));
    13.  
    14.         if(index >= nums.length) {
    15.             return;
    16.         }
    17.  
    18.         for(int i = index; i < nums.length; i++) {
    19.            
    20.             path.add(nums[i]);
    21.             // backStraking(nums, index +1);  怎么能用index呢？！
    22.             backStraking(nums, i +1);
    23.             path.removeLast();
    24.            
    25.         }
    26.     }
    27. }

    491.递增⼦序列

    题⽬链接：https://leetcode-cn.com/problems/increasing-subsequences/

    给定⼀个整型数组, 你的任务是找到所有该数组的递增⼦序列，递增⼦序列的长度⾄少是 2。

    ⽰例: 输⼊: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

    说明: 给定数组的长度不会超过15。

    ·        数组中的整数范围是 [-100,100]。

            给定数组中可能包含重复数字，相等的数字应该被视为递增的⼀种情况。

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.     public List> findSubsequences(int[] nums) {
    5.         backtracking(nums,0);
    6.         return result;
    7.     }
    8.  
    9.     void backtracking(int[] nums,int index) {
    10.         if(path.size() > 1) { //递增子序列长度至少为2
    11.             result.add(new ArrayList<>(path));
    12.         }
    13.  
    14.         if(index == nums.length){
    15.             return;
    16.         }
    17.  
    18.         boolean[] used = new boolean[201]; //同一层相同结点不能重复
    19.         for(int i = index; i < nums.length; i++) {
    20.             //纵向判断递增
    21.             if(path.size() > 0 && nums[i] < path.get(path.size() - 1)) {
    22.                 continue;
    23.             }
    24.             //横向判断元素是否重复(序列无序)
    25.             if(used[nums[i] + 100] == true) {
    26.                 continue;
    27.             }
    28.  
    29.             // used[nums[i]] = true; 因为下标没有负数
    30.             used[nums[i] + 100] = true;
    31.             path.add(nums[i]);
    32.             backtracking(nums, i + 1);
    33.             path.removeLast();
    34.            
    35.  
    36.         }
    37.     }
    38. }

    排列问题

    46.全排列

    题⽬链接：https://leetcode-cn.com/problems/permutations/

    给定⼀个 没有重复 数字的序列，返回其所有可能的全排列。

    ⽰例: 输⼊: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.     public List> permute(int[] nums) {
    5.         boolean[] used = new boolean[nums.length + 1]; 
    6.         Arrays.fill(used, false);
    7.         backtracking(nums,used);
    8.         return result;
    9.     }
    10.  
    11.      //同一树枝标记用过 used[i] == true
    12.      //将used作为参数传递 比较的是同一树枝和同一树层
    13.      //将used放在for循环上面，比较的是for循环是否有重复元素
    14.     void backtracking(int[] nums, boolean[] used) {
    15.         if(path.size() == nums.length) {
    16.             result.add(new ArrayList<>(path));
    17.             return;
    18.         }
    19.  
    20.         for(int i = 0; i < nums.length; i++) {
    21.             if(used[i] == true) {
    22.                 continue;
    23.             }
    24.             used[i] = true;
    25.             path.add(nums[i]);
    26.             backtracking(nums, used);
    27.             path.remove(path.size() - 1);
    28.             used[i] = false;
    29.         }
    30.     }
    31. }

    47.全排列 II

    题⽬链接：https://leetcode-cn.com/problems/permutations-ii/

    给定⼀个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

    ⽰例 1： 输⼊：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]

    ⽰例 2： 输⼊：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    提⽰： 1 <= nums.length <= 8 -10 <= nums[i] <= 10

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.     int len;
    5.     public List> permuteUnique(int[] nums) {
    6.         len = nums.length;
    7.         boolean[] used = new boolean[nums.length + 1]; //[]是长度  <>是范型  ()是内容
    8.         Arrays.fill(used, false);
    9.         Arrays.sort(nums);
    10.         backTracking(nums,used);
    11.         return result;
    12.     }
    13.  
    14.     void backTracking(int[] nums, boolean[] used){
    15.         if(path.size() == nums.length) {
    16.             result.add(new ArrayList<>(path));
    17.             return;
    18.         }
    19.  
    20.         for(int i = 0; i < len; i++) {
    21.             //纵向判断
    22.             if(used[i] == true) continue;
    23.             //横向判断  原序列需要排序
    24.             if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
    25.  
    26.             used[i] = true;
    27.             path.add(nums[i]);
    28.             backTracking(nums, used);
    29.             path.removeLast();
    30.             used[i] = false;
    31.         }
    32.     }
    33. }

    棋盘问题

    第51题. N皇后

    题⽬链接： https://leetcode-cn.com/problems/n-queens/ n

    皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

    8 皇后问题的⼀种解法：

    给定⼀个整数 n，返回所有不同的 n 皇后问题的解决⽅案。 每⼀种解法包含⼀个明确的 n 皇后问题的棋⼦放置⽅案，该⽅案中 'Q' 和 '.' 分别代表了皇后 和空位。

    ⽰例: 输⼊: 4 输出: [ [".Q..",  "...Q", "Q...", "..Q."],["..Q.",  "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

    1. class Solution {
    2.     List> result = new ArrayList<>();
    3.     
    4.     public List> solveNQueens(int n) {
    5.         char[][] chessboard = new char[n][n];
    6.         for(char[] c : chessboard) {
    7.             Arrays.fill(c,'.');
    8.         }
    9.         backtracking(n, 0, chessboard);
    10.         return result;
    11.  
    12.     }
    13.  
    14.     void backtracking(int n, int row, char[][] chessboard){
    15.         if(row == n) {
    16.             result.add(Array2List(chessboard));
    17.             return;
    18.         }
    19.  
    20.         for(int col = 0; col < n; col++) { //行和列都是从0开始
    21.             if(isvalid(n,row,col,chessboard)) {
    22.                 chessboard[row][col] = 'Q';
    23.                 backtracking(n, row + 1, chessboard);
    24.                 chessboard[row][col] = '.';
    25.             }
    26.         }
    27.     }
    28.  
    29.     public List Array2List(char[][] chessboard) {
    30.         List list = new ArrayList<>();
    31.         
    32.         for (char[] c : chessboard) {
    33.             list.add(String.copyValueOf(c));
    34.         }
    35.         return list;
    36.     }
    37.  
    38.     public boolean isvalid(int n, int row, int col, char[][] chessboard) {
    39.         // 检查列
    40.         for (int i=0; i
    41.             if (chessboard[i][col] == 'Q') {
    42.                 return false;
    43.             }
    44.         }
    45.  
    46.         // 检查45度对角线
    47.         for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
    48.             if (chessboard[i][j] == 'Q') {
    49.                 return false;
    50.             }
    51.         }
    52.  
    53.         // 检查135度对角线
    54.         for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
    55.             if (chessboard[i][j] == 'Q') {
    56.                 return false;
    57.             }
    58.         }
    59.         return true;
    60.     }
    61. }

  • 相关阅读:
    Mainflux IoT：Go语言轻量级开源物联网平台，支持HTTP、MQTT、WebSocket、CoAP协议
    SpringBoot对于SpringMVC的支持
    验证UDP端口是否开放
    数据结构 【树状数组】【线段树】【珂朵莉树】
    【ML-SVM案例学习】案例一：对鸢尾花数据进行SVM分类（附源码）
    ElasticSearch7.3学习(二)----内部基于_version乐观锁控制机制
    【汇编语言-王爽】第八章：数据处理的两个基本问题
    【Linux】常用命令汇总
    请看看我的stata回归分析思路有没有问题？
    一文讲清Java中的四种引用类型的区别(关于弱引用是如何解决ThreadLocal内存泄漏问题)
  • 原文地址：https://blog.csdn.net/m0_48489427/article/details/132848698