深圳网站搭建费用,龙岩seo招聘,php 建设网站制作,网站建设经费计划内容习题
2.3 子集问题
就是组合过程收集path。就像是代码随想录里说得那样#xff0c;组合和分割问题就是收集叶子结点#xff0c;子集问题就是收集每一个节点。 有涉及到同层重复元素的问题。 先排序#xff0c;后再for循环里处理相同数值跳过。 设置函数内的used。 还可以用…习题
2.3 子集问题
就是组合过程收集path。就像是代码随想录里说得那样组合和分割问题就是收集叶子结点子集问题就是收集每一个节点。 有涉及到同层重复元素的问题。 先排序后再for循环里处理相同数值跳过。 设置函数内的used。 还可以用HashSetMap HashSet
//创建
HashSetInteger hs new HashSet();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);
Map
//创建
HashMapInteger,Integer map new HashMap();
//判断
if ( map.getOrDefault( nums[i],0 ) 1 ){//返回 key 相映射的的 value如果给定的 key 在映射关系中找不到则返回指定的默认值。continue;
}
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )1);
2.3.1 78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 还是要画回溯树比较快需要startIdx结束条件就是与length比较。
class Solution {ListListInteger ans new ArrayListListInteger();ListInteger path new ArrayListInteger();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList(path));for(int istartIdx; inums.length; i){path.add(nums[i]);Backtracing(nums, i1);path.removeLast();} }public ListListInteger subsets(int[] nums) {ans.clear();path.clear();Backtracing(nums, 0);return ans;}
}2.3.2 90. 子集 II
涉及同层重复元素的排除。 还是要画回溯树比较好理解。 还记得就是先排序后再for循环里处理相同数值跳过。
class Solution {ListListInteger ans new ArrayListListInteger();ListInteger path new ArrayListInteger();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList(path));for(int istartIdx; inums.length; i){if(i!startIdxnums[i]nums[i-1]){continue;}path.add(nums[i]);Backtracing(nums, i1);path.removeLast();} }public ListListInteger subsetsWithDup(int[] nums) {ans.clear();path.clear();Arrays.sort(nums);Backtracing(nums, 0);return ans;}
}class Solution {ListListInteger ans new ArrayList();// 存放符合条件结果的集合LinkedListInteger path new LinkedList();// 用来存放符合条件结果boolean[] used;private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList(path));if (startIdx nums.length){return;}for (int i startIdx; i nums.length; i){if (i 0 nums[i] nums[i - 1] !used[i - 1]){continue;}path.add(nums[i]);used[i] true;Backtracing(nums, i 1);path.removeLast();used[i] false;}}public ListListInteger subsetsWithDup(int[] nums) {if (nums.length 0){ans.add(path);return ans;}Arrays.sort(nums);used new boolean[nums.length];Backtracing(nums, 0);return ans;}
}2.3.3 491.递增子序列
示例 1至少两个元素 输入nums [4,6,7,7] 输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 想要用used来可是有负数我该怎么处理有说范围-100,100所以可以用数组哦。
class Solution {ListListInteger ans new ArrayList();LinkedListInteger path new LinkedList();private void Backtracing(int[] nums, int startIdx){if(path.size()2){ans.add(new ArrayList(path));}if (startIdx nums.length){return;}int[] used new int[201];for (int i startIdx; i nums.length; i){if (!path.isEmpty() nums[i] path.get(path.size() - 1) || (used[nums[i] 100] 1)) continue;used[nums[i] 100] 1;path.add(nums[i]);Backtracing(nums, i 1);path.removeLast();}}public ListListInteger findSubsequences(int[] nums) {if (nums.length 0){ans.add(path);return ans;}Backtracing(nums, 0);return ans;}
}还可以用HashSetMap HashSet
//创建
HashSetInteger hs new HashSet();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);
Map
//创建
HashMapInteger,Integer map new HashMap();
//判断
if ( map.getOrDefault( nums[i],0 ) 1 ){continue;
}
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )1);
