做网站月入5万,意大利天天电信app下载,网站超级外链,delphi xe10网站开发考试周连考不复习就挂科了 一直没更新十分抱歉 今天开始在周日前补回来
491.递增子序列
在90.子集I中我们是通过排序#xff0c;再加一个标记数组来达到去重的目的。
而本题求自增子序列#xff0c;是不能对原数组进行排序的#xff0c;排完序的数组都是自增子序列了。
…考试周连考不复习就挂科了 一直没更新十分抱歉 今天开始在周日前补回来
491.递增子序列
在90.子集I中我们是通过排序再加一个标记数组来达到去重的目的。
而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。
所以不能使用之前的去重逻辑
Java
class Solution {ListListInteger result new ArrayList();ListInteger path new ArrayList();public ListListInteger findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex){if(path.size() 1)result.add(new ArrayList(path)); HashSetInteger hs new HashSet();for(int i startIndex; i nums.length; i){if(!path.isEmpty() path.get(path.size() -1 ) nums[i] || hs.contains(nums[i]))continue;hs.add(nums[i]);path.add(nums[i]);backTracking(nums, i 1);path.remove(path.size() - 1);}}
}与递增条件结合
整个 if 语句如下
if (!path.isEmpty() path.get(path.size() - 1) nums[i] || hs.contains(nums[i]))continue;第一部分 !path.isEmpty() path.get(path.size() - 1) nums[i] 用于确保当前选择的数字 nums[i] 满足递增条件即当前数字必须大于 path 中的最后一个数字。第二部分 hs.contains(nums[i]) 用于确保当前数字没有在同一层递归中重复选择。
当满足这两个条件中的任意一个时都会跳过当前数字 nums[i]不将其加入 path防止生成重复的子序列。
HashSet 的作用
HashSet 用来存储在当前层递归中已经选择过的数字。如果当前数字已经在 HashSet 中存在说明这个数字已经在当前递归层被选择过了就跳过当前数字避免重复选择。通过 hs.contains(nums[i]) 判断如果当前数字已经出现过就跳过否则将它添加到 HashSet 中表示已经选择过这个数字。
46.全排列
首先排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了但是在[2,1]中还要在使用一次1所以处理排列问题就不用使用startIndex了。
这里和77.组合问题131.切割问题和78.子集问题最大的不同就是for循环里不用startIndex了。
因为排列问题每次都要从头开始搜索例如元素1在[1,2]中已经使用过了但是在[2,1]中还要再使用一次1。
而used数组其实就是记录此时path里都有哪些元素使用了一个排列里一个元素只能使用一次。
Java
class Solution {ListListInteger result new ArrayList();// 存放符合条件结果的集合LinkedListInteger path new LinkedList();// 用来存放符合条件结果boolean[] used;public ListListInteger permute(int[] nums) {if (nums.length 0){return result;}used new boolean[nums.length];backtracking(nums);return result;}private void backtracking(int[] nums){if (path.size() nums.length){result.add(new ArrayList(path));return;}for (int i 0; i nums.length; i){if (used[i]){continue;}used[i] true;path.add(nums[i]);backtracking(nums);path.removeLast();used[i] false;}}
}递归过程
遍历数组 nums 中的每个元素 nums[i]。如果该元素已经被使用used[i] 为 true跳过当前元素。如果该元素没有被使用将其添加到 path 中并标记为已使用。递归调用 permuteHelper(nums)生成下一个元素。回溯从当前排列中移除最后一个元素并将该元素标记为未使
47.全排列II
给定一个可包含重复数字的序列要返回所有不重复的全排列。
这里又涉及到去重了。要强调的是去重一定要对元素进行排序
Java
class Solution {//存放结果ListListInteger result new ArrayList();//暂存结果ListInteger path new ArrayList();public ListListInteger permuteUnique(int[] nums) {boolean[] used new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backtracking(nums, used);return result;}private 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) {// used[i - 1] true说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] false说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] false) {used[i] true;//标记同⼀树⽀nums[i]使⽤过防止同一树枝重复使用path.add(nums[i]);backtracking(nums, used);path.remove(path.size() - 1);//回溯说明同⼀树层nums[i]使⽤过防止下一树层重复used[i] false;//回溯}}}
}回溯总结 回溯算法能解决如下问题
组合问题N个数里面按一定规则找出k个数的集合排列问题N个数按一定规则全排列有几种排列方式切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集棋盘问题N皇后解数独等等
