成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Subset 子集

hzc / 2497人閱讀

摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸?？臻g思路這道題可以轉(zhuǎn)化為一個(gè)類似二叉樹的深度優(yōu)先搜索。另外需要先排序以滿足題目要求。新的集合要一個(gè)新的，防止修改引用。

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.
深度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(N) 遞歸棧空間

思路

這道題可以轉(zhuǎn)化為一個(gè)類似二叉樹的深度優(yōu)先搜索。二叉樹的根是個(gè)空集，它的左子節(jié)點(diǎn)是加上第一個(gè)元素產(chǎn)生的集合，右子節(jié)點(diǎn)不加上第一個(gè)元素所產(chǎn)生的集合。以此類推，左子節(jié)點(diǎn)的左子節(jié)點(diǎn)是加上第二個(gè)元素，左子節(jié)點(diǎn)的右子節(jié)點(diǎn)是不加上第二個(gè)元素。而解就是這個(gè)二叉樹所有的路徑，我們要做的就是根據(jù)加，或者不加下一元素，來產(chǎn)生一個(gè)新的集合，然后繼續(xù)遞歸直到終點(diǎn)。另外需要先排序以滿足題目要求。

注意

這里要先排序，不然過不了leetcode，但實(shí)際上是不用的

如果遞歸之前先將空集加入結(jié)果，那么遞歸盡頭就不需要再加一次空集。反之則需要。

LinkedList在這里效率要高于ArrayList。

新的集合要new一個(gè)新的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;
        // 不加入當(dāng)前元素產(chǎn)生的集合，然后繼續(xù)遞歸
        helper(S, index+1, res, tmp);
        List tmp2 = new ArrayList(tmp);
        tmp2.add(S[index]);
        res.add(tmp2);
        // 加入當(dāng)前元素產(chǎn)生的集合，然后繼續(xù)遞歸
        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.
深度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(N) 遞歸棧空間

思路

思路和上題一樣，區(qū)別在于如果有重復(fù)的只能加一次。好在我們已經(jīng)先將數(shù)組排序（數(shù)組中有重復(fù)一般都可以用排序解決），所以重復(fù)元素是相鄰的，我們?yōu)榱吮ＷC重復(fù)元素只加一次，要把這些重復(fù)的元素在同一段邏輯中一起處理，而不是在遞歸中處理，不然就太麻煩了。所以我們可以先統(tǒng)計(jì)好重復(fù)的有n個(gè)，然后分別在集合中加上0個(gè)，1個(gè)，2個(gè)...n個(gè)，然后再分別遞歸。

代碼 
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;
        //跳過重復(fù)元素，重復(fù)元素的個(gè)數(shù)根據(jù)index和oldIndex可以得到
        while(index < nums.length - 1 && nums[index] == nums[index+1]) index++;
        helper(nums, res, tmp, index + 1);
        //依次在集合中加入1個(gè)、2個(gè)...重復(fù)的元素
        for(int i = oldIndex; i <= index; i++){
            List tmp2 = new ArrayList(tmp);
            //這里需要一個(gè)循環(huán)保證這次加的元素個(gè)數(shù)
            for(int j = i; j <= index; j++){
                tmp2.add(nums[index]);
            }
            res.add(tmp2);
            helper(nums, res, tmp2, index + 1);
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64448.html

相關(guān)文章

  • 每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（Set）

    摘要：一集合是什么與它相關(guān)數(shù)學(xué)概念有哪些解題集合定義集合是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)。集合中的元素稱為成員，集合最重要的兩個(gè)特點(diǎn)集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習(xí)題，五一放假結(jié)束，該收拾好狀態(tài)啦。 下面是之前分享的鏈接： ...

    silvertheo 評論0 收藏0

  • Leetcode[368] Largest Divisible Subset

    摘要：讓數(shù)組從小到大排序。因?yàn)槿绻粋€(gè)數(shù)能被加到這個(gè)中的話，說明這個(gè)數(shù)能被這個(gè)中的最大的數(shù)整除。同樣可以用一個(gè)數(shù)組來記錄之前搜索過的。，表示的是我們搜索的路徑是從到。初始化這個(gè)位置是頭結(jié)點(diǎn)。說明是，并沒有是當(dāng)前最大的里的最大值。 LeetCode[368] Largest Divisible Subset Given a set of distinct positive integers,...

    springDevBird 評論0 收藏0

  • leetcode368. Largest Divisible Subset

    摘要：題目要求假設(shè)有一組值唯一的正整數(shù)數(shù)組，找到元素最多的一個(gè)子數(shù)組，這個(gè)子數(shù)組中的任選兩個(gè)元素都可以構(gòu)成或。只要這個(gè)數(shù)字是前面數(shù)字的倍數(shù)，則構(gòu)成的數(shù)組的長度則是之前數(shù)字構(gòu)成最長子數(shù)組加一。 題目要求 Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj)...

    Honwhy 評論0 收藏0

  • leetcode 416 Partition Equal Subset Sum

    摘要：如果是奇數(shù)的話，那一定是不滿足條件的，可以直接返回。如果是偶數(shù)，將除獲得我們要求的一個(gè)子數(shù)組元素的和。如何暫存我們計(jì)算的中間結(jié)果呢聲明一個(gè)長度為的布爾值數(shù)組。每個(gè)元素的布爾值代表著，數(shù)組中是否存在滿足加和為的元素序列。 題目詳情 Given a non-empty array containing only positive integers, find if the array ca...

    jsummer 評論0 收藏0

  • leetcode416. Partition Equal Subset Sum

    摘要：題目要求假設(shè)有一個(gè)全為正整數(shù)的非空數(shù)組，將其中的數(shù)字分為兩部分，確保兩部分?jǐn)?shù)字的和相等。而這里的問題等價(jià)于，有個(gè)物品，每個(gè)物品承重為，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。 題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

    Caicloud 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<