[Leetcode] Subset 子集

hzc 发布于2019-08-14 12:23 / 2411人阅读

摘要：深度优先搜索复杂度时间空间递归栈空间思路这道题可以转化为一个类似二叉树的深度优先搜索。另外需要先排序以满足题目要求。新的集合要一个新的，防止修改引用。

Subset I

Given a set of distinct integers, nums, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.

深度优先搜索 复杂度

时间 O(NlogN) 空间 O(N) 递归栈空间

思路

这道题可以转化为一个类似二叉树的深度优先搜索。二叉树的根是个空集，它的左子节点是加上第一个元素产生的集合，右子节点不加上第一个元素所产生的集合。以此类推，左子节点的左子节点是加上第二个元素，左子节点的右子节点是不加上第二个元素。而解就是这个二叉树所有的路径，我们要做的就是根据加，或者不加下一元素，来产生一个新的集合，然后继续递归直到终点。另外需要先排序以满足题目要求。

注意

这里要先排序，不然过不了leetcode，但实际上是不用的

如果递归之前先将空集加入结果，那么递归尽头就不需要再加一次空集。反之则需要。

LinkedList在这里效率要高于ArrayList。

新的集合要new一个新的list，防止修改引用。

代码

public class Solution {
    public List> subsets(int[] S) {
        Arrays.sort(S);
        List> res = new ArrayList>();
        List tmp = new ArrayList();
        //先加入空集
        res.add(tmp);
        helper(S, 0, res, tmp);
        return res;
    }
    
    private void helper(int[] S,int index,List> res, List tmp){
        if(index>=S.length) return;
        // 不加入当前元素产生的集合，然后继续递归
        helper(S, index+1, res, tmp);
        List tmp2 = new ArrayList(tmp);
        tmp2.add(S[index]);
        res.add(tmp2);
        // 加入当前元素产生的集合，然后继续递归
        helper(S, index+1, res, tmp2);
    }
}

Subset II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.

深度优先搜索 复杂度

时间 O(NlogN) 空间 O(N) 递归栈空间

思路

思路和上题一样，区别在于如果有重复的只能加一次。好在我们已经先将数组排序（数组中有重复一般都可以用排序解决），所以重复元素是相邻的，我们为了保证重复元素只加一次，要把这些重复的元素在同一段逻辑中一起处理，而不是在递归中处理，不然就太麻烦了。所以我们可以先统计好重复的有n个，然后分别在集合中加上0个，1个，2个...n个，然后再分别递归。

代码

public class Solution {
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List> res = new ArrayList>();
        List tmp = new ArrayList();
        res.add(tmp);
        helper(nums, res, tmp, 0);
        return res;
    }
    
    private void helper(int[] nums, List> res, List tmp, int index){
        if(index >= nums.length) return;
        int oldIndex = index;
        //跳过重复元素，重复元素的个数根据index和oldIndex可以得到
        while(index < nums.length - 1 && nums[index] == nums[index+1]) index++;
        helper(nums, res, tmp, index + 1);
        //依次在集合中加入1个、2个...重复的元素
        for(int i = oldIndex; i <= index; i++){
            List tmp2 = new ArrayList(tmp);
            //这里需要一个循环保证这次加的元素个数
            for(int j = i; j <= index; j++){
                tmp2.add(nums[index]);
            }
            res.add(tmp2);
            helper(nums, res, tmp2, index + 1);
        }
    }
}

私有云服务器托管 Subset 子集 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64448.html

每周一练之数据结构与算法（Set）

摘要：一集合是什么与它相关数学概念有哪些解题集合定义集合是一种包含不同元素的数据结构。集合中的元素称为成员，集合最重要的两个特点集合中的成员是无序集合中不存在相同成员即无序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第四周的练习题，五一放假结束，该收拾好状态啦。下面是之前分享的链接： ...

silvertheo 2019-08-23 17:17 评论0 收藏0
Leetcode[368] Largest Divisible Subset

摘要：让数组从小到大排序。因为如果一个数能被加到这个中的话，说明这个数能被这个中的最大的数整除。同样可以用一个数组来记录之前搜索过的。，表示的是我们搜索的路径是从到。初始化这个位置是头结点。说明是，并没有是当前最大的里的最大值。 LeetCode[368] Largest Divisible Subset Given a set of distinct positive integers,...

springDevBird 2019-08-14 14:59 评论0 收藏0
leetcode368. Largest Divisible Subset

摘要：题目要求假设有一组值唯一的正整数数组，找到元素最多的一个子数组，这个子数组中的任选两个元素都可以构成或。只要这个数字是前面数字的倍数，则构成的数组的长度则是之前数字构成最长子数组加一。题目要求 Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj)...

Honwhy 2019-08-16 13:57 评论0 收藏0
leetcode 416 Partition Equal Subset Sum

摘要：如果是奇数的话，那一定是不满足条件的，可以直接返回。如果是偶数，将除获得我们要求的一个子数组元素的和。如何暂存我们计算的中间结果呢声明一个长度为的布尔值数组。每个元素的布尔值代表着，数组中是否存在满足加和为的元素序列。题目详情 Given a non-empty array containing only positive integers, find if the array ca...

jsummer 2019-08-16 11:07 评论0 收藏0
leetcode416. Partition Equal Subset Sum

摘要：题目要求假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。而这里的问题等价于，有个物品，每个物品承重为，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。题目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

Caicloud 2019-08-16 15:10 评论0 收藏0