做网站属于无形资产还是费用,个人怎么做淘宝客网站,企业域名怎么查找,教育培训网站抄袭#LeetCode 491. Non-decreasing Subsequences #LeetCode 491. 视频讲解#xff1a;回溯算法精讲#xff0c;树层去重与树枝去重 | LeetCode#xff1a;491.递增子序列_哔哩哔哩_bilibili 首先#xff0c;本题不能考虑首先对数组排序#xff0c;排序会导致数组直接变为一个…#LeetCode 491. Non-decreasing Subsequences #LeetCode 491. 视频讲解回溯算法精讲树层去重与树枝去重 | LeetCode491.递增子序列_哔哩哔哩_bilibili 首先本题不能考虑首先对数组排序排序会导致数组直接变为一个递增的序列。本题依然是一个组合问题所以无序i 在for loop中依然是从startIndex 开始。与之前的去重逻辑不同每一层会有一个uset 变量是记录本层元素是否重复使用新的一层uset都会重新定义不是之前去重那样的全局变量同样回溯的时候也不需要删除元素也是在树层去重。
代码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex) {if (startIndex nums.length) {return;}if (path.size() 1) {result.add(new ArrayList(path));}HashSetInteger uset new HashSet();for (int i startIndex; i nums.length; i) {if (!path.isEmpty() path.getLast() nums[i] || uset.contains(nums[i])) {continue;}uset.add(nums[i]);path.addLast(nums[i]);backtracking(nums, i 1);path.removeLast();}}
}
#LeetCode 46. Permutations #LeetCode 46. 视频讲解组合与排列的区别回溯算法求解的时候有何不同| LeetCode46.全排列_哔哩哔哩_bilibili 与之前的组合问题不同的地方在于排列是有序的[1, 2] 和[2, 1] 是不同的如果用used 数组那么在for loop 遍历的时候也是通过used 数组的标记来判断下一次取具体哪一个数字。
回溯方法代码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger permute(int[] nums) {boolean[] used new boolean[nums.length];Arrays.fill(used, false);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() nums.length) {result.add(new LinkedList(path));return;}for (int i 0; i nums.length; i) {if (used[i]) {continue;}used[i] true;path.addLast(nums[i]);backtracking(nums, used);used[i] false;path.removeLast();}}
}
#LeetCode 47. Permutations II #LeetCode 47. 视频讲解回溯算法求解全排列如何去重| LeetCode47.全排列 II_哔哩哔哩_bilibili 如果完成了之前的题目那么这个题目较简单排列的思想与上一个题目相似去重与之前组合去重相似记得数组需要排序。
回溯方法代码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger permuteUnique(int[] nums) {boolean[] used new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() nums.length) {result.add(new LinkedList(path));return;}for (int i 0; i nums.length; i) {if (i 0 nums[i] nums[i-1] !used[i-1]) {continue;}if (used[i]) {continue;}path.addLast(nums[i]);used[i] true;backtracking(nums, used);used[i] false;path.removeLast();}}
}
