网站建设费如何做账,备案 网站首页地址,软件下载网站哪个比较好,安康做企业网站的1.子集II题目链接思路#xff1a;这是一道标准的组合问题数组排序去重。依然是使用回溯。注意#xff1a;去重代码只需要判断同一树层上是否有重复#xff0c;同组合总和II#xff08;https://blog.csdn.net/xiaomingming99/article/details/129396344#xff09;解法这是一道标准的组合问题数组排序去重。依然是使用回溯。注意去重代码只需要判断同一树层上是否有重复同组合总和IIhttps://blog.csdn.net/xiaomingming99/article/details/129396344解法class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger subsetsWithDup(int[] nums) {// 记得数组排序Arrays.sort(nums);back(nums, 0);return res;}private void back(int[] nums, int startIndex) {res.add(new ArrayList(path));for (int i startIndex; i nums.length; i){// 去重if (i startIndex nums[i] nums[i - 1])continue;path.add(nums[i]);back(nums, i 1);path.removeLast(); // 回溯}}
}2.递增子序列题目链接思路回溯数组去重回溯三部曲返回参数startindex和数组nums。 全局变量path(记录单个结果)和res记录结果集合终止条件本题要求递增子序列大小至少为2所以要判断path.size2单层逻辑for循环中需要判断path的最后一个元素是否大于当前nums[i]且还需要添加代码实现同一父节点下的同层上使用过的元素就不能再使用注意1.和||同时出现时优先级更高先执行2.在90.子集II (opens new window)中是通过排序原数组判断同一树层元素是否重复来达到去重。而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。class Solution {private LinkedListInteger path new LinkedList();private ListListInteger res new ArrayList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums,0);return res;}private void backtracking (int[] nums, int start) {// path的size必须大于等于2 且不需要return因为后面可能还有更长的符合条件的序列if (path.size() 2) {res.add(new ArrayList(path));}// 标记数组 用于去重 // 比如[4,6,7,7] 使用这个数组就可以只出现一次[4,6,7] 标记6使用过int[] used new int[201];for (int i start; i nums.length; i) {// 先执行判断path的最后一个元素是否大于当前值如果是则说明不符合递增// 后执行|| 判断当前元素是否被使用过if (!path.isEmpty() 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();}}
}3.全排列题目链接思路回溯的排列问题。回溯三部曲递归函数参数参数只需要nums。不需要startIndex参数因为排列问题每次都要从头开始搜索。全局变量path(记录单个结果)和res记录结果集合递归终止条件只需要收集元素的数组path大小达到和nums数组一样大说明到达叶子结点可以返回单层搜索的逻辑for循环中需要判断当前元素是否已经在path中若在直接continue。注意 首先排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合区别于组合问题。解法class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger permute(int[] nums) {back(nums);return res;}private void back(int[] nums) {// 终止条件if (path.size() nums.length){res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i){// 判断path中是否含有遍历元素if (path.contains(nums[i]))continue;path.add(nums[i]);back(nums);path.removeLast();}}
}
