当前位置：首页 > article >正文

代码随想录-算法训练营day29(回溯算法05:非递减子序列,全排列,全排列2)

article 2024/12/5 10:25:46

第七章 回溯算法part05
 
* 491.递增子序列
* 46.全排列
* 47.全排列 II
 
详细布置 
 
491.递增子序列 
 
本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。 
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 
 
视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v  
 
 
46.全排列 
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex 
https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html   
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W  
 
47.全排列 II 
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行 
 
https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html     
 
视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm
 
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ

day29

非递减子序列

 //关键在于不能排序,所以使用哈希法去重
 //树枝上收集结果而不是仅在子叶上,所以一进入回溯函数就收割结果,而且不return,继续往后延伸树枝
 //在for循环外面新建hashset或者hash数组,只管树层上的去重
 class Solution {
     private List<Integer> path = new ArrayList<>();
     private List<List<Integer>> res = new ArrayList<>();
     public List<List<Integer>> findSubsequences(int[] nums) {
         backtracking(nums,0);
         return res;
     }
 
     private void backtracking (int[] nums, int start) {
         if (path.size() > 1) {
             res.add(new ArrayList<>(path));//至少两个
         }
         int[] used = new int[201];//本体题不能排序,用哈希法的数组表现形式去重
         //for循环外面新建,只针对本层for循环不能出现重复元素,也就是只在本树层去重,进入下一层的时候used会更新,所以树枝不去重
         for (int i = start; i < nums.length; i++) {
             if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                     (used[nums[i] + 100] == 1)) continue;
           //如果加进来的数字小,继续;如果加进来得数字相等,看看是在树层还是在树枝;
           //used[nums[i] + 100] == 1 说明本树层上已经用过了,就不能用了;
           //如果是在树枝上,因为已经进入了新的回溯函数,所以nums已经重置了,used[nums[i] + 100] == 0,就可以加进去
             used[nums[i] + 100] = 1;//本层此数用过了
             path.add(nums[i]);
             backtracking(nums, i + 1);
             path.remove(path.size() - 1);
         }
     }
 }

全排列

 class Solution {
     List<List<Integer>> result = new ArrayList<>();
     List<Integer> path = new ArrayList<>();
     int[] used;
     //元素个数确定,数组也行,不对不行,要用path.size==nums.length去判断结束,只能用List
     public List<List<Integer>> permute(int[] nums) {
         //子叶上收集,判断深度方向上结束后收割
         used = new int[nums.length];
         backtricking(nums,0);
         return result;
     }
     private void backtricking(int[] nums,int index){
         if(path.size() == nums.length) {
             result.add(new ArrayList(path));
         }
         for(int i=0;i<nums.length; i++){
             if(used[i] != 0 ) continue;
             used[i] = 1;
             path.add(nums[i]);
             index++;
             backtricking(nums,index);
             index--;
             path.remove(path.size() - 1);
             used[i]=0;
         }
     }
 }

全排列2

 //只是全排列的基础上加了去重的判断
 class Solution {
     List<List<Integer>> result = new ArrayList<>();
     List<Integer> path = new ArrayList<>();
     int[] used;
     //元素个数确定,数组也行,不对不行,要用path.size==nums.length去判断结束,只能用List
     public List<List<Integer>> permuteUnique(int[] nums) {
         //子叶上收集,判断深度方向上结束后收割
         used = new int[nums.length];
         Arrays.sort(nums);
         backtricking(nums,0);
         return result;
     }
     private void backtricking(int[] nums,int index){
         if(path.size() == nums.length) {
             result.add(new ArrayList(path));
         }
         for(int i=0;i<nums.length; i++){
             if(used[i] != 0 || (i>0 && nums[i] == nums[i-1] && used[i-1] == 0) ) continue;
             // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
             // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
             // 只是全排列的基础上加了去重的判断
             used[i] = 1;
             path.add(nums[i]);
             index++;
             backtricking(nums,index);
             index--;
             path.remove(path.size() - 1);
             used[i]=0;
         }
     }
 }

感谢大佬分享:

代码随想录-算法训练营day29【回溯算法05：递增子序列、全排列】-CSDN博客

查看全文

http://www.kler.cn/a/420969.html