Subsets 系列 Leetcode解題記錄

gityuan 發(fā)布于2019-08-14 14:41 / 3413人閱讀

摘要：寫這個(gè)系列是因?yàn)榧o(jì)念一下去年的今天，就是年的月號(hào)，刷題第一天，今天是一周年紀(jì)念日。排除，就是返回一空的。復(fù)雜度分析算法課講過，這個(gè)復(fù)雜度是指數(shù)次，能實(shí)現(xiàn)出來就行了，沒法優(yōu)化。復(fù)雜度分析不分析了，反正指數(shù)次。

Subsets

寫這個(gè)系列是因?yàn)榧o(jì)念一下去年的今天，就是2015年的9月14號(hào)，刷題第一天，今天是一周年紀(jì)念日。當(dāng)時(shí)只敢做easy還得抄答案的我想啥時(shí)候能做上medium啊，事到如今，感覺都不是啥障礙了，這道題也已經(jīng)做了第四遍了，抽出來的DFS遞歸模板放在這里總結(jié)一下。
這題內(nèi)容就是就是給個(gè)數(shù)組，里面的數(shù)字都是獨(dú)一無二的，把它所有的子集都輸出出來。

解決思路

題目中給了個(gè)例子，比如[1,2,3]，第一次抽出1，然后在1的基礎(chǔ)上加2，再加3。加完之后再往回返，去掉3，再去掉2，發(fā)現(xiàn)可以加3，形成[1,3]，再到2，以此類推。
思路很容易，但是寫的時(shí)候需要用到遞歸的手法，這個(gè)還是需要點(diǎn)兒思維過程的，推薦用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;
        //這個(gè)就是用來搜集每個(gè)子集的。
        List list = new ArrayList<>();
        dfs(result, list, 0, nums);
        return result;
    }
    public void dfs(List> result, List list, int start, int[] nums){
        //先把當(dāng)前的子集加上，這里添加的語法我命名為『照相法』
        result.add(new ArrayList<>(list));
        //注意這里要從start位置開始循環(huán)，否則就是stackoverflow
        for(int i = start; i < nums.length; i++){
            //添加start位置的數(shù)字
            list.add(nums[i]);
            //開始遞歸，比如把1加上去之后，就穩(wěn)住1，找后面比如2.
            dfs(result, list, i+1, nums);
            //backtrack，就是把之前加上的去掉，相當(dāng)于往回走，比如之前加到1，2，3
            //就把3去掉，然后再找。
            list.remove(list.size()-1);
        }
    }
}

復(fù)雜度分析

算法課講過，這個(gè)復(fù)雜度是指數(shù)次，能實(shí)現(xiàn)出來就行了，沒法優(yōu)化。

最后再說兩句

這題就是模板，DFS的模板，就是一個(gè)容器來回抓，容器的容器每次把這個(gè)容器記錄下來。還有遞歸的debug就是人工模仿IDE，一步一步走。

Subsets II

稍有不同，就是數(shù)組里面的數(shù)字可能有重復(fù)，同時(shí)要求子集輸出不能用重復(fù)的元素，一個(gè)非常典型的follow up。

解決思路

重點(diǎn)在于判斷重復(fù)數(shù)字，把重復(fù)的情況跳過去。模板還是一樣的。

code

public class SubsetsII {
    public List> subsetsWithDup(int[] nums) {
        List> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        //這里就需要排序了，給以后跳過重復(fù)數(shù)字埋下伏筆
        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++){
            //關(guān)鍵就在這一句，每次循環(huán)起始的數(shù)字不能和之前重復(fù)。
            if(i > start && nums[i] == nums[i-1]) continue;
            list.add(nums[i]);
            dfs(result, list, i+1, nums);
            list.remove(list.size()-1);
        }
    }
}

復(fù)雜度分析

不分析了，反正指數(shù)次。

最后再說兩句

這里注意用好模板，循環(huán)的時(shí)候把起始的start寫成了0，直接就爆了。