Subsets 系列 Leetcode解题记录

gityuan 发布于2019-08-14 14:41 / 3376人阅读

摘要：写这个系列是因为纪念一下去年的今天，就是年的月号，刷题第一天，今天是一周年纪念日。排除，就是返回一空的。复杂度分析算法课讲过，这个复杂度是指数次，能实现出来就行了，没法优化。复杂度分析不分析了，反正指数次。

Subsets

写这个系列是因为纪念一下去年的今天，就是2015年的9月14号，刷题第一天，今天是一周年纪念日。当时只敢做easy还得抄答案的我想啥时候能做上medium啊，事到如今，感觉都不是啥障碍了，这道题也已经做了第四遍了，抽出来的DFS递归模板放在这里总结一下。
这题内容就是就是给个数组，里面的数字都是独一无二的，把它所有的子集都输出出来。

解决思路

题目中给了个例子，比如[1,2,3]，第一次抽出1，然后在1的基础上加2，再加3。加完之后再往回返，去掉3，再去掉2，发现可以加3，形成[1,3]，再到2，以此类推。
思路很容易，但是写的时候需要用到递归的手法，这个还是需要点儿思维过程的，推荐用IDE的debug功能一步一步走走看。

code

public class Subsets {
    public List> subsets(int[] nums) {
        //先把输出的东西摆上去。
        List> result = new ArrayList<>();
        //排除corner case，就是返回一空的。
        if(nums == null || nums.length == 0) return result;
        //这个就是用来搜集每个子集的。
        List list = new ArrayList<>();
        dfs(result, list, 0, nums);
        return result;
    }
    public void dfs(List> result, List list, int start, int[] nums){
        //先把当前的子集加上，这里添加的语法我命名为『照相法』
        result.add(new ArrayList<>(list));
        //注意这里要从start位置开始循环，否则就是stackoverflow
        for(int i = start; i < nums.length; i++){
            //添加start位置的数字
            list.add(nums[i]);
            //开始递归，比如把1加上去之后，就稳住1，找后面比如2.
            dfs(result, list, i+1, nums);
            //backtrack，就是把之前加上的去掉，相当于往回走，比如之前加到1，2，3
            //就把3去掉，然后再找。
            list.remove(list.size()-1);
        }
    }
}

复杂度分析

算法课讲过，这个复杂度是指数次，能实现出来就行了，没法优化。

最后再说两句

这题就是模板，DFS的模板，就是一个容器来回抓，容器的容器每次把这个容器记录下来。还有递归的debug就是人工模仿IDE，一步一步走。

Subsets II

稍有不同，就是数组里面的数字可能有重复，同时要求子集输出不能用重复的元素，一个非常典型的follow up。

解决思路

重点在于判断重复数字，把重复的情况跳过去。模板还是一样的。

code

public class SubsetsII {
    public List> subsetsWithDup(int[] nums) {
        List> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        //这里就需要排序了，给以后跳过重复数字埋下伏笔
        Arrays.sort(nums);
        //剩下都是一样的
        List list = new ArrayList<>();
        dfs(result, list, 0, nums);
        return result;
    }
    public void dfs(List> result, List list, int start, int[] nums){
        result.add(new ArrayList<>(list));
        for(int i = start; i < nums.length; i++){
            //关键就在这一句，每次循环起始的数字不能和之前重复。
            if(i > start && nums[i] == nums[i-1]) continue;
            list.add(nums[i]);
            dfs(result, list, i+1, nums);
            list.remove(list.size()-1);
        }
    }
}

复杂度分析

不分析了，反正指数次。

最后再说两句

这里注意用好模板，循环的时候把起始的start写成了0，直接就爆了。

GPU云服务器云服务器 Subsets 解题思路 LeetCode LeetCode_String

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

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

LeetCode 关于回溯问题的看法

摘要：回溯算法在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。回溯算法( BackTrack )在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。使用回溯算法解题的一般步骤使用回溯算法解题的一般步骤：针对所给问题得出一般的解空间用回溯搜索方法搜索解空间使用深度优先去搜索所有解并包含适当的剪枝操作 LeetCode 使用回溯算法的题目主要有 36 题，...

ASCH 2019-08-15 13:43 评论0 收藏0
[Leetcode - Dynamic Programming] Partition Equal S

摘要：背包问题假设有个宝石，只有一个容量为的背包，且第个宝石所对应的重量和价值为和求装哪些宝石可以获得最大的价值收益思路我们将个宝石进行编号，寻找的状态和状态转移方程。我们用表示将前个宝石装到剩余容量为的背包中，那么久很容易得到状态转移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

qpal 2019-08-14 16:41 评论0 收藏0
每周一练之数据结构与算法（Set）

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

silvertheo 2019-08-23 17:17 评论0 收藏0
[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
leetcode78. Subsets

摘要：题目要求类似的题目有可以参考这篇博客可以参考这篇博客思路一递归还是利用递归的方式，在前一种情况的基础上遍历下一轮的组合情况。题目要求 Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subset...

Rocko 2019-08-15 10:43 评论0 收藏0