Subsets 系列 Leetcode解題記錄

gityuan 發布于2019-08-14 14:41 / 3418人閱讀

摘要：寫這個系列是因為紀念一下去年的今天，就是年的月號，刷題第一天，今天是一周年紀念日。排除，就是返回一空的。復雜度分析算法課講過，這個復雜度是指數次，能實現出來就行了，沒法優化。復雜度分析不分析了，反正指數次。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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