当前位置: 首页 > news >正文

代码随想录算法训练营第二十九天|491.递增子序列、46.全排列、47.全排列 II

目录

491.递增子序列

46.全排列

47.全排列 II


491.递增子序列

本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。 

代码随想录

视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili

题解思路:

本题还是有点坑的,这里的如何记录使用过的数组的方式很容易给人造成误解,具体的解释如下:
1、使用数组来做哈希,初始化数组里面的元素都设置为0,如果设置成全局变量,那么每轮递归的时候相同元素只能使用一次,以[4,6,7,7]来说,不能取到4677这个组合的,显然不符合题意,因为本题不是对排序后的数组进行树层去重的,因此出现相同元素不一定是相邻元素,只能出现一个记录一个。
2、每次递归数组uesd都会重置为0的代码直接嵌套在递归里面,因为树枝不需要去重的,需要及时把使用过的元素重置为0;回溯的时候之前标记为1的地方仍然为1,并没有重置为0。
以上两点的解读就是为什么不把uesd设置为全局变量,使用used[nums[i] + 100] = 0把使用过的元素重置为0,而是直接嵌套在递归里面,可以及时往下搜索的时候及时置为0,不会造成树枝去重的原理,

class Solution {LinkedList<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){if(path.size() > 1 ) result.add(new LinkedList<Integer>(path));if(startIndex == nums.length) return;int[] used = new int[201]; //使用数组来做哈希,初始化数组里面的元素都设置为0,如果设置成全局变量,那么每轮递归的时候相同元素只能使用一次,以[4,6,7,7]来说,不能取到4677这个组合的,显然不符合题意。因为本题不是对排序后的数组进行树层去重的,因此出现相同元素不一定是相邻元素,只能出现一个记录一个。//具体方式解读为:这里每次递归数组uesd都会重置为0,因为树枝不需要去重的,需要及时把使用过的元素重置为0;回溯的时候之前标记为1的地方仍然为1,并没有重置为0。这就是为什么不把uesd设置为全局变量,使用used[nums[i] + 100] = 0把使用过的元素重置为0,而是直接嵌套在递归里面,可以及时往下搜索的时候及时置为0,不会造成树枝去重的原理,for(int i = startIndex; i < nums.length; i++){if((path.size() != 0 && nums[i] < path.getLast()) || used[nums[i] + 100] == 1 ){continue;}used[nums[i] + 100] = 1;path.add(nums[i]);backtracking(nums, i + 1);path.removeLast();}}
}

46.全排列

本题重点感受一下,排列问题 与 组合问题,组合总和,子集问题的区别。 为什么排列问题不用 startIndex 

代码随想录

视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili

题解思路:

排列和组合问题还是有区别的,和组合最大的区别在于求全排列问题,每层都是从0开始搜索而不是startIndex,需要used数组记录path里都放了哪些元素了!!!最后对听卡哥视频讲解思路,然后自己写出来最好,u1s1听卡哥讲算法是一种享受!!!本题需要注意的一点就是: if(used[i] == true) continue;在每轮递归中求全排列中都是从0开始搜索,需要通过uesd的数组记录path中已经添加过的元素,添加过的元素直接跳过就行

class Solution {LinkedList<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();boolean[] used; //需要used数组记录path里都放了哪些元素了public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];backtracking(nums);return result;}public void backtracking(int[] nums){if(path.size() == nums.length){result.add(new LinkedList<Integer>(path));return;}for(int i = 0; i < nums.length; i++){ if(used[i] == true) continue;//在每轮递归中求全排列中都是从0开始搜索,需要通过uesd的数组记录path中已经添加过的元素,添加过的元素直接跳过就行path.add(nums[i]);used[i] = true;backtracking(nums);path.removeLast();used[i] = false;}}
}

47.全排列 II 

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合,可以先自己做一下,然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行,used[i - 1] == false 也行

代码随想录

视频讲解:回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili

题解思路:

本题需要先把数组进行排序,使得相同的元素相邻才好进行树层去重,具体的注意细节代码中有详细注释,本题容易疑惑的两行代码见如下分析:
1、if(i > 0 && nums[i] == nums[i -1] && used[i - 1] == false) continue; //为了避免以相同元素开头的组合重复添加到结果集中进行树层去重
2、if(used[i] == true) continue; //在每轮递归中求全排列中都是从0开始搜索,需要通过uesd的数组记录path中已经添加过的元素,添加过的元素直接跳过就行

class Solution {LinkedList<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {used = new boolean[nums.length];Arrays.sort(nums); //需要先把数组进行排序,使得相同的元素相邻才好进行树层去重backtracking(nums);return result;}public void backtracking(int[] nums){if(path.size() == nums.length){result.add(new LinkedList<Integer>(path));return;} for(int i = 0; i < nums.length; i++){if(i > 0 && nums[i] == nums[i -1] && used[i - 1] == false) continue; //为了避免以相同元素开头的组合重复添加到结果集中进行树层去重if(used[i] == true) continue; //在每轮递归中求全排列中都是从0开始搜索,需要通过uesd的数组记录path中已经添加过的元素,添加过的元素直接跳过就行path.add(nums[i]);used[i] = true;backtracking(nums);used[i] = false;path.removeLast();}}
}
http://www.lryc.cn/news/69145.html

相关文章:

  • 【Kafka】Kafka监控工具Kafka-eagle简介
  • Java操作MongoDB
  • Java断言(assert)的介绍和使用
  • 我的世界Fabric mod开发-快速漏斗
  • AI“应用商店”来了!OpenAI首批70个ChatGPT Plugin最全梳理
  • NSS LitCTF部分wp
  • 【开发者指南】如何在MyEclipse中编辑HTML或JSP文件?(一)
  • 关于博客停更的原因
  • 智能感知编码优化与落地实践
  • OpenCL编程指南-5.1工作项函数-整数函数-公共函数
  • 教你接入Midjourney,不用梯子也能玩
  • Mysql中常用到的查询关键字
  • 【ROS】ROS1工具详解
  • 论Plant Simulation中的Init的使用及调用顺序
  • nginx实现正向代理
  • 【spark】
  • ADO.NET 面试题
  • 第三篇、基于Arduino uno,用oled0.96寸屏幕显示dht11温湿度传感器的温度和湿度信息——结果导向
  • 什么是npu算力盒子,算力是越大越好吗?
  • 后端返回文件流时,前端如何处理并成功下载流文件以及解决下载后打开显示不支持此文件格式
  • Ansible的脚本-playbook 剧本
  • python lambda表达式表达式详解及应用
  • Windows 10计算机性能优化:让你的电脑更流畅
  • SpringMVC底层原理源码解析
  • 【CSS系列】第八章 · CSS浮动
  • janus videoroom 对接freeswitch conference 篇1
  • cs109-energy+哈佛大学能源探索项目 Part-2.1(Data Wrangling)
  • __101对称二叉树------进阶:你可以运用递归和迭代两种方法解决这个问题吗?---本题还没用【迭代】去实现
  • 怎么取消只读模式?硬盘进入只读模式怎么办?
  • 如何使用Java生成Web项目验证码