亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Subset 子集

hzc / 2531人閱讀

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

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ù)雜度

時間 O(NlogN) 空間 O(N) 遞歸?？臻g

思路

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

注意

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

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

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;
        // 不加入當(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ù)雜度

時間 O(NlogN) 空間 O(N) 遞歸?？臻g

思路

思路和上題一樣，區(qū)別在于如果有重復(fù)的只能加一次。好在我們已經(jīng)先將數(shù)組排序（數(shù)組中有重復(fù)一般都可以用排序解決），所以重復(fù)元素是相鄰的，我們?yōu)榱吮ＷC重復(fù)元素只加一次，要把這些重復(fù)的元素在同一段邏輯中一起處理，而不是在遞歸中處理，不然就太麻煩了。所以我們可以先統(tǒng)計好重復(fù)的有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;
        //跳過重復(fù)元素，重復(fù)元素的個數(shù)根據(jù)index和oldIndex可以得到
        while(index < nums.length - 1 && nums[index] == nums[index+1]) index++;
        helper(nums, res, tmp, index + 1);
        //依次在集合中加入1個、2個...重復(fù)的元素
        for(int i = oldIndex; i <= index; i++){
            List tmp2 = new ArrayList(tmp);
            //這里需要一個循環(huán)保證這次加的元素個數(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://www.ezyhdfw.cn/yun/64448.html

相關(guān)文章

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

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

    silvertheo 評論0 收藏0

  • Leetcode[368] Largest Divisible Subset

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

    springDevBird 評論0 收藏0

  • leetcode368. Largest Divisible Subset

    摘要：題目要求假設(shè)有一組值唯一的正整數(shù)數(shù)組，找到元素最多的一個子數(shù)組，這個子數(shù)組中的任選兩個元素都可以構(gòu)成或。只要這個數(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ù)，將除獲得我們要求的一個子數(shù)組元素的和。如何暫存我們計算的中間結(jié)果呢聲明一個長度為的布爾值數(shù)組。每個元素的布爾值代表著，數(shù)組中是否存在滿足加和為的元素序列。 題目詳情 Given a non-empty array containing only positive integers, find if the array ca...

    jsummer 評論0 收藏0

  • leetcode416. Partition Equal Subset Sum

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

    Caicloud 評論0 收藏0

發(fā)表評論

0條評論

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