新网站建设需要注意,怎么才能百度做网站,新乡手机网站建设哪家专业,wordpress数字资源下载会员目录
491.递增子序列
46.全排列
47.全排列 II 491.递增子序列 本题和大家刚做过的 90.子集II 非常像#xff0c;但又很不一样#xff0c;很容易掉坑里。 代码随想录 视频讲解#xff1a;回溯算法精讲#xff0c;树层去重与树枝去重 | LeetCode#xff1a;491.递增子序…目录
491.递增子序列
46.全排列
47.全排列 II 491.递增子序列 本题和大家刚做过的 90.子集II 非常像但又很不一样很容易掉坑里。 代码随想录 视频讲解回溯算法精讲树层去重与树枝去重 | LeetCode491.递增子序列_哔哩哔哩_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 {LinkedListInteger path new LinkedList();ListListInteger result new ArrayList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){if(path.size() 1 ) result.add(new LinkedListInteger(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 代码随想录 视频讲解组合与排列的区别回溯算法求解的时候有何不同| LeetCode46.全排列_哔哩哔哩_bilibili 题解思路
排列和组合问题还是有区别的和组合最大的区别在于求全排列问题每层都是从0开始搜索而不是startIndex需要used数组记录path里都放了哪些元素了最后对听卡哥视频讲解思路然后自己写出来最好u1s1听卡哥讲算法是一种享受本题需要注意的一点就是 if(used[i] true) continue;在每轮递归中求全排列中都是从0开始搜索需要通过uesd的数组记录path中已经添加过的元素添加过的元素直接跳过就行
class Solution {LinkedListInteger path new LinkedList();ListListInteger result new ArrayList();boolean[] used; //需要used数组记录path里都放了哪些元素了public ListListInteger 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 LinkedListInteger(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 也行 代码随想录 视频讲解回溯算法求解全排列如何去重| LeetCode47.全排列 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 {LinkedListInteger path new LinkedList();ListListInteger result new ArrayList();boolean[] used;public ListListInteger 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 LinkedListInteger(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();}}
}
