<abbr id="mgmwe"></abbr>

<strike id="mgmwe"></strike>

<fieldset id="mgmwe"></fieldset>

[Leetcode] Subset 子集

hzc 發布于2019-08-14 12:23 / 2487人閱讀

摘要：深度優先搜索復雜度時間空間遞歸棧空間思路這道題可以轉化為一個類似二叉樹的深度優先搜索。另外需要先排序以滿足題目要求。新的集合要一個新的，防止修改引用。

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);
        }
    }
}

GPU云服務器云服務器 Subset 子集 LeetCode LeetCode_String

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

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