铝基板营销型网站建设,哪个做问卷网站佣金高,简述优化搜索引擎的方法,可以建设网站的公司78.子集
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1#xff1a; 输入#xff1a;nums [1,2,3] 输出#xff1a;[[],[1],[2],[1…78.子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
import java.util.ArrayList;
import java.util.List;class Solution {private ListInteger path new ArrayList();private ListListInteger res new ArrayList();public ListListInteger subsets(int[] nums) {backTrace(nums, 0);return res;}private void backTrace(int[] nums, int start) {res.add(new ArrayList(path));if (start nums.length) {return;}for (int i start; i nums.length; i) {path.add(nums[i]);backTrace(nums, i 1);path.remove(path.size() - 1);}}
}90.子集II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 示例 1 输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {private ListInteger path new ArrayList();private ListListInteger res new ArrayList();public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);backTrace(nums, 0);return res;}private void backTrace(int[] nums, int start) {res.add(new ArrayList(path));if (start nums.length) {return;}for (int i start; i nums.length; i) {if (i start nums[i] nums[i - 1]) {continue;}path.add(nums[i]);backTrace(nums, i 1);path.remove(path.size() - 1);}}
}去重需要先对数组进行排序可别忘记了 这里要求有重复元素的集合同一个树层上的元素不能重复同一个树枝上下上可以取重复
491.递增子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。 示例 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]] 示例 2 输入nums [4,4,3,2,1] 输出[[4,4]]
class Solution {public ListListInteger findSubsequences(int[] nums) {backTracing(nums, 0);return res;}private ListInteger path new ArrayList();private ListListInteger res new ArrayList();private void backTracing(int[] nums, int start) {if (path.size() 1) {res.add(new ArrayList(path));}if (start nums.length) {return;}MapInteger, Integer map new TreeMap();for (int i start; i nums.length; i) {if ((path.size() 0 nums[i] path.get(path.size() - 1)) || map.containsKey(nums[i])) {continue;}map.put(nums[i], 0);path.add(nums[i]);backTracing(nums, i 1);path.remove(path.size() - 1);}}
}注意这道题不可以进行排序子集问题又需要去重以前的排列之后判断是不是和前一个相同的逻辑不适用了这里每层用一个map记录数组中的元素是不是出现过出现过的不再使用并且要保证递增序列在每个元素放进path的时候和path中的最后一个元素比较小就不再进行递归了这一枝截断
