厦工品牌网站设计php网站开发注意问题

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

厦工品牌网站设计,php网站开发注意问题,wordpress域名变回ip,上海公司车牌申请条件回溯算法part05 491.递增子序列解题思路与 90.子集II 不同的点回溯三部曲 46.全排列解题思路遇到的难点思考 47.全排列 II解题思路注意点拓展需要加深理解的点#xff08;需复习 小总结 491.递增子序列 本题和大家刚做过的90.子集II非常像#xff0c;但又很不一样#xff0c… 回溯算法part05 491.递增子序列解题思路与 90.子集II 不同的点回溯三部曲 46.全排列解题思路遇到的难点思考 47.全排列 II解题思路注意点拓展需要加深理解的点需复习 小总结 491.递增子序列 本题和大家刚做过的90.子集II非常像但又很不一样很容易掉坑里。 题目链接 491.递增子序列 文章讲解 491.递增子序列 视频讲解 491.递增子序列 解题思路 在90.子集II中我们是通过排序再加一个标记数组来达到去重的目的。 而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。 与90.子集II不同的点 不能排序不能用之前的used[]数组而要用set且set不需要跟着回溯只负责本层里面取了哪些元素需要判断每个path中元素个数是否大于等于2需要判断每个path是否是递增的 回溯三部曲 递归函数参数 全局变量result和pathstartIndex 终止条件 要遍历整个树可以没有单层遍历逻辑 去重逻辑局部变量HashSet uset; 记录本层元素是否重复使用新的一层uset都会重新定义清空所以要知道uset只负责本层
// uset用数组实现 效率高一些 class Solution {ListListInteger result new ArrayList();ListInteger path new LinkedList();public ListListInteger findSubsequences(int[] nums) {backTracking(nums, 0);return result;}public void backTracking(int[] nums, int startIndex){if(path.size() 2){result.add(new ArrayList(path));}if(startIndex nums.length){ // 这个终止条件可以没有因为我们要遍历整个树return;}int[] uset new int[201];for(int i startIndex; i nums.length; i){if(!path.isEmpty() path.get(path.size() - 1) nums[i] || uset[nums[i] 100] 1) continue; //注意是continue而不是breakuset[nums[i] 100] 1;path.add(nums[i]);backTracking(nums, i 1);path.remove(path.size() - 1);}}
}// // uset用set实现 class Solution {ListListInteger result new ArrayList();ListInteger path new LinkedList();public ListListInteger findSubsequences(int[] nums) {backTracking(nums, 0);return result;}public void backTracking(int[] nums, int startIndex){if(path.size() 2){result.add(new ArrayList(path));}if(startIndex nums.length){ // 这个终止条件可以没有因为我们要遍历整个树return;}HashSetInteger uset new HashSet();for(int i startIndex; i nums.length; i){if(!path.isEmpty() path.get(path.size() - 1) nums[i] || uset.contains(nums[i])) continue; //注意是continue而不是breakuset.add(nums[i]);path.add(nums[i]);backTracking(nums, i 1);path.removeLast();}} }46.全排列 本题重点感受一下排列问题 与 组合问题组合总和子集问题的区别。 为什么排列问题不用 startIndex 题目链接 46.全排列 文章讲解 46.全排列 视频讲解 46.全排列 解题思路 不需要i startIndex控制for循环开始位置每次从i 0开始 需要判断当前元素是否已经取过 遇到的难点 如何不重复取自身元素used数组其实就是记录此时path里都有哪些元素使用了一个排列里一个元素只能使用一次 思考 这道题的used数组和之前题目中的used数组作用的不同 这道题的used数组记录此时path里都有哪些元素使用了之前题目中的used数组树层上对组合去重一般要先将数组排序
// 解法1通过判断path中是否存在数字排除已经选择的数字 // 感觉这种比解法2好理解 class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger permute(int[] nums) {if (nums.length 0) return result;backtrack(nums, path);return result;}public void backtrack(int[] nums, LinkedListInteger path) {if (path.size() nums.length) {result.add(new ArrayList(path));}for (int i 0; i nums.length; i) {// 如果path中已有则跳过if (path.contains(nums[i])) {continue;} path.add(nums[i]);backtrack(nums, path);path.removeLast();}} }// 法2通过used判断是否path中已取过当前数字 class Solution {ListListInteger result new ArrayList();ListInteger path new LinkedList();boolean[] used;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 ArrayList(path));}for(int i 0; i nums.length; i){if(used[i]){continue;}used[i] true;path.add(nums[i]);backTracking(nums);used[i] false;path.removeLast();}} }47.全排列 II 本题 就是我们讲过的40.组合总和II去重逻辑 和46.全排列的结合可以先自己做一下然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] true 也行used[i - 1] false 也行 题目链接 47.全排列 II 文章讲解 47.全排列 II 视频讲解 47.全排列 II 解题思路 40.组合总和II去重逻辑 和46.全排列的结合 注意点 nums数组排序 Arrays.sort(nums);树层去重 if(i 0 nums[i - 1] nums[i] used[i - 1] false) continue; // 树层去重取过的元素不再重复取 if(used[i] true) continue; // 取过的数标记为1拓展 去重代码中如果改成 used[i - 1] true 也是正确的! 这是为什么呢就是上面我刚说的如果要对树层中前一位去重就用used[i - 1] false如果要对树枝前一位去重用used[i - 1] true。 对于排列问题树层上去重和树枝上去重都是可以的但是树层上去重效率更高 树枝去重图例
需要加深理解的点需复习 树层去重和树枝去重used数组在不同题中的作用为什么这道题的used数组需要作为参数参与递归结合40.组合总和II和90.子集II进行思考491.递增子序列中的uset
小总结 491.递增子序列 不能用之前的used[]数组而要用set且set不需要跟着回溯只负责本层里面取了哪些元素 used数组不需要回溯不需要放在递归参数里面 46.全排列 used数组其实就是记录此时path里都有哪些元素使用了一个排列里一个元素只能使用一次 used数组要回溯要放在递归参数里面 47.全排列 II used数组去重取过的元素不再重复取 used数组要回溯要放在递归参数里面 class Solution {ListListInteger result new ArrayList();ListInteger path new LinkedList();boolean[] used;public ListListInteger permuteUnique(int[] nums) {used new boolean[nums.length];Arrays.sort(nums);backTracking(nums, used);return result;}public void backTracking(int[] nums, boolean[] used){if(path.size() nums.length){result.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {// 树层去重if(i 0 nums[i - 1] nums[i] used[i - 1] false) continue; // 树层去重if(used[i] true) continue; // 取过的数标记为1used[i] true;path.add(nums[i]);backTracking(nums, used);used[i] false;path.removeLast();}} }