建设大学网站服务,wordpress国外主题慢,企业网站app,做普工招聘网站说明
在初遇排列组合题目时#xff0c;总让人摸不着头脑#xff0c;但是做多了题目后#xff0c;发现几乎能用同一个模板做完所有这种类型的题目#xff0c;大大提高了解题效率。本文简要介绍这种方法。
题目列表
所有题目均从leetcode查找#xff0c;便于在线验证 46.…说明
在初遇排列组合题目时总让人摸不着头脑但是做多了题目后发现几乎能用同一个模板做完所有这种类型的题目大大提高了解题效率。本文简要介绍这种方法。
题目列表
所有题目均从leetcode查找便于在线验证 46.全排列 47.全排列 II 78.子集 90.子集 II 39.组合总和 40.组合总和 II
模板代码
本文所有题目都可以用以下模板代码解决
public class Template{private ListListInteger res new ArrayList();public ListListInteger permute(int[] nums) {LinkedListInteger path new LinkedList();dfs(nums, path);return res;}private void dfs(int[] nums, LinkedListInteger path) {if (path.size() nums.length) { res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {path.addLast(nums[i]);dfs(nums,path);path.removeLast();}}
}上述代码是求nums无重复元素的全排列每个元素允许选择多次。以123为例如下图所示从上往下看选择第一个元素的时候 可以选择123假设第一个选定为1将选定的元素存入path中即path[1]那么第二个元素也能选择123同理第二个元素也选择1即path[1,1]时选择第三个元素依然能选择123。当第三个元素选定后此时path的长度等于nums的长度一个排列结果就计算出来了加入到结果res中去接着回溯按照同样的逻辑运行下去最后得到全排列结果。
题解
46. 全排列
题目描述
给定一个不含重复数字的数组 nums 返回其所有可能的全排列 。你可以按任意顺序返回答案。 示例 1 输入 nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2 输入 nums [0,1] 输出[[0,1],[1,0]] 示例 3 输入 nums [1] 输出[[1]] 思路
和模板代码相比只多一个限制 一个元素只能选择一次。 还是以123为例如下图当path[1]选择第二个元素时由于已经选择了1所以再选择1时应该被剪掉红叉表示。 为了判断某个元素是否被使用过可以定义一个used数组维护方式如下
当元素被加入path中时该元素被使用used[i]1当元素被移除path时该元素未被使用used[i]0 在计算时如果发现元素已经被使用则剪枝。 完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class Permute_046 {private ListListInteger res new ArrayList();public ListListInteger permute(int[] nums) {if(nums.length0) return res;LinkedListInteger path new LinkedList();int[] used new int[nums.length];dfs(nums, path, used);return res;}private void dfs(int[] nums, LinkedListInteger path, int[] used) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if(used[i]1) continue;//剪枝同个元素不能选择多次path.addLast(nums[i]);used[i] 1;dfs(nums,path,used);path.removeLast();used[i] 0;}}
}
执行结果 小结
求数字数组无重复元素的全排列在模板代码的基础上修改
已经选择过的数字不能重复选择使用used数组判断某个元素是否被使用过
47.全排列 II
题目描述
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1 输入 nums [1,1,2] 输出 [[1,1,2], [1,2,1], [2,1,1]] 示例 2 输入 nums [1,2,3] 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 思路
和模板代码相比多了以下限制 一个元素只能选择一次。可能存在重复元素 重复元素造成之前的全排列结果存在重复现在的问题是怎么去重 以112为例如下图我们第一个元素可以选择112很明显选择第一个1的排列和选择第二个1的排列情况相同所以选择第二个1的时候应该剪枝。为了判断重复可以先将nums从小到大排序如果i0nums[i]nums[i-1]说明重复应该剪枝i等于0时代表该元素第一次被选择肯定不存在重复。 需要注意的是再上图绿色标记部分此时path[1], 选择第二个元素时遍历i的范围为0,1,2。即第二个元素有可能加入nums[0],nums[1],nums[2]。 i0时如果第二个元素选择nums[0],因为path中已经选择了第一个1所以剪枝used[i]1i1时path[1,1]i2时path[1,2] 上面的步骤2来看满足条件i0nums[i]nums[i-1]按照上面的逻辑应该被剪枝但是显然[1,1,2]是一个合法的排列结果不应该被剪掉。仔细观察发现只有同层存在相同元素时才应该剪枝不同层则不应该剪。 对于应该被剪枝的部分红x标记回溯后第一个1会被标记为未使用即nums[i-1]0对于不应该被剪枝的部分绿色标记第一个1会被标记为使用即nums[i-1]1 现在我们只取情况1所以判断条件可以改写为nums[i]nums[i-1]used[i-1]0
完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class PermuteUnique_047 {private ListListInteger res new ArrayList();public ListListInteger permuteUnique(int[] nums) {if (nums.length 0) return res;ListInteger path new ArrayList();int[] used new int[nums.length];Arrays.sort(nums);//排序方便判断同层是否重复nums[i-1]nums[i]则重复dfs(nums, path, used);return res;}private void dfs(int[] nums, ListInteger path, int[] used) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (used[i] 1) continue;//剪枝同个元素不能选多次if (i 0 nums[i] nums[i - 1] used[i - 1] 0) continue;//剪枝避免同层重复path.add(nums[i]);used[i] 1;dfs(nums, path, used);path.remove(path.size() - 1);used[i] 0;}}
}
执行结果 小结
求数字数组有重复元素的全排列在模板代码的基础上修改
已经选择过的数字不能重复选择使用used数组判断某个元素是否被使用过使用nums[i]nums[i-1]判断重复对nums从小到大排序同层重复剪枝nums[i]nums[i-1]used[i-1]0
78.子集
题目描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1 输入 nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2 输入 nums [0] 输出 [[],[0]] 思路
和模板代码相比多了以下限制 一个元素只能选择一次。求子集其长度不一定是nums.length而是在这个范围[0,nums.length]求的是组合而非排列即[1,2][2,1]是同一种结果 对于限制2 长度不再是nums.length那么在向res加入path时应该分别判断长度是0~nums.length时加入结果。 对于限制3 以123为例如果将nums排序后path后入的元素比上一个元素还要小时应该剪枝。
完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;public class Subsets_078 {private ListListInteger res new ArrayList();public ListListInteger subsets(int[] nums) {if (nums.length 0) return res;LinkedListInteger path new LinkedList();int[] used new int[nums.length];Arrays.sort(nums);//保证后入的元素一定大于先入的元素所以排序for (int i 0; i nums.length; i) {dfs(nums, path, used, i);}return res;}private void dfs(int[] nums, LinkedListInteger path, int[] used, int len) {if (path.size() len) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (used[i] 1) continue;//剪枝同个元素不能选多次if (!path.isEmpty() nums[i] path.peekLast()) continue;//剪枝选择的下个元素比上个元素还要小path.addLast(nums[i]);used[i] 1;dfs(nums, path, used, len);path.removeLast();used[i] 0;}}
}
执行结果 优化代码
可以优化如下 dfs中的for循环不是固定从0开始而是从传入的begin开始。第一个元素从0开始找第二个元素就只能从1开始找。总是从排序数组的下个元素找包含两个隐含信息同一个元素不可能被同时选择多次下一个总是大于上一个元素。所以之前的剪枝逻辑都可以去掉。 package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Subsets_078 {private ListListInteger res new ArrayList();public ListListInteger subsets(int[] nums) {if (nums.length 0) return res;ListInteger path new ArrayList();Arrays.sort(nums);dfs(nums, 0,path);return res;}private void dfs(int[] nums, int begin,ListInteger path) {res.add(new ArrayList(path));for (int i begin; i nums.length; i) {path.add(nums[i]);dfs(nums, i1,path);//不能继续找当前元素直接找下个元素path中不可能选择到同一个元素下一个也始终比上一个大path.remove(path.size() - 1);}}
}
优化执行结果 备注后面的组合题都可以使用这个模板
小结
求数组无重复元素的子集 1.对nums排序 2.修改dfs中的for循环让i从begin开始下次遍历时用dfs(nums, i1,path)
90.子集 II
题目描述
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 示例 1 输入 nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2 输入 nums [0] 输出 [[],[0]] 思路
和78 子集相比多了以下限制 nums可能包含重复数组 去重逻辑同层相同则剪枝nums[i]nums[i-1]used[i-1]0
完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class SubsetsWithDup_090_02 {private ListListInteger res new ArrayList();public ListListInteger subsetsWithDup(int[] nums) {if (nums.length 0) return res;ListInteger path new ArrayList();int[] used new int[nums.length];Arrays.sort(nums);dfs(nums, 0, path, used);return res;}private void dfs(int[] nums, int begin, ListInteger path, int[] used) {res.add(new ArrayList(path));for (int i begin; i nums.length; i) {if (i 0 nums[i] nums[i - 1] used[i - 1] 0) continue;//同层相同则剪枝path.add(nums[i]);used[i] 1;dfs(nums, i 1, path, used);path.remove(path.size() - 1);used[i] 0;}}
}
执行结果 小结
求数组有重复元素的子集 1.对nums排序 2.修改dfs中的for循环让i从begin开始下次遍历时用dfs(nums, i1,path) 3. 增加同层相同元素的剪枝逻辑i 0 nums[i] nums[i - 1] used[i - 1] 0
39.组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。 示例 1 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。 示例 2 输入: candidates [2,3,5], target 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3 输入: candidates [2], target 1 输出: [] 思路
和78 子集相比多了以下限制 一个元素可以选择多次目标和要等于target 对于限制1修改dfs中下一个遍历为dfs(nums, ipath) 对于限制2只有当目标和等于target时才加入res中为了避免死循环比如一直选第一个元素当path中的和大于target时应该中止该分支的查找不再向path中加入新的值直接return。
完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class CombinationSum_039 {private ListListInteger res new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {ListInteger path new ArrayList();Arrays.sort(candidates);dfs(candidates, 0, path, target);return res;}private static int cnt 0;private void dfs(int[] candidates, int begin, ListInteger path, int target) {int total path.stream().reduce(0, Integer::sum);if (total target) return;if (total target) {res.add(new ArrayList(path));return;}for (int i begin; i candidates.length; i) {path.add(candidates[i]);dfs(candidates, i, path, target);path.remove(path.size() - 1);}}
}
执行结果 优化代码
在上面的代码中每次dfs都是要对path求和效率低下我们可以直接传入target固定第一个元素后找下一个元素target应该要减去当前元素。比如要在2,3,5中找和为8的组合那么固定第一个元素2下面就应该时找等于8-2的组合。当target为0时说明path的和就等于target当target小于0时说明path中的累加和已经超过了原来的target此时return。
package leetcode.plzh;import java.util.*;public class CombinationSum_039 {private ListListInteger res new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {ListInteger path new ArrayList();Arrays.sort(candidates);dfs(candidates, 0, path, target);return res;}private void dfs(int[] candidates, int begin, ListInteger path, int target) {if(target0) return;if (target 0) {res.add(new ArrayList(path));return;}for (int i begin; i candidates.length; i) {path.add(candidates[i]);dfs(candidates, i, path, target-candidates[i]);path.remove(path.size() - 1);}}
}
优化执行结果
时间由原来的21ms降低为3ms
40.组合总和 II
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
示例 1 输入: candidates [10,1,2,7,6,1,5], target 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2 输入: candidates [2,5,2,1,2], target 5, 输出: [ [1,2,2], [5] ] 思路
和39 组合总和相比多了以下限制 一个元素只能选择一次可能存在重复元素 对于限制1 可以dfs中遍历时查找下一个元素即可dfs(candidates, i1, path, target-candidates[i]); 对于限制2 新增去重逻辑同层相同则剪枝nums[i]nums[i-1]used[i-1]0 完整代码
package leetcode.plzh;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;public class CombinationSum2_040 {private ListListInteger res new ArrayList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);LinkedListInteger path new LinkedList();int[] used new int[candidates.length];dfs(candidates, 0, path, target,used);return res;}public void dfs(int[] candidates, int begin, LinkedListInteger path, int target,int[] used) {if (target 0) return;if (target 0) {res.add(new ArrayList(path));}for (int i begin; i candidates.length; i) {if(i0candidates[i]candidates[i-1]used[i-1]0) continue; //同层相同剪枝path.addLast(candidates[i]);used[i] 1;dfs(candidates, i 1, path, target - candidates[i],used);path.removeLast();used[i] 0;}}
}
执行结果
