leetcode-90. Subsets II

lijinke666 發布于2019-07-30 17:22 / 3255人閱讀

摘要：題目描述注意題目解讀找出所有的子集。思路確定子集的來源，遍歷原始列表，每一個元素都往已有的子集列表里邊添加，同時添加到已有的子集中去，產生新的子集。類似于動態規劃思想，依賴于之前的東西產生現在的東西。

題目描述

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

注意

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[[2],[1],[1,2,2],[2,2],[1,2],[]]

題目解讀：
找出所有的子集。
思路：

確定子集的來源， 遍歷原始列表，每一個元素都往已有的子集列表里邊添加，同時添加到已有的子集中去，產生新的子集。
類似于動態規劃思想，依賴于之前的東西產生現在的東西。

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, S):
        res = [[]]
        S.sort()
        for i in range(len(S)):
            if i==0 or S[i]!=S[i-1]:
                l=len(res)
            for j in range(len(res)-l,len(res)):
                res.append(res[j]+[S[i]])
        return res


if __name__=="__main__":
    st=Solution()
    S=[1,2,2]
    S=[0]
    result=st.subsetsWithDup(S)

云服務器 GPU云服務器 Subsets II quartus ii ii6

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/42182.html

leetcode90. Subsets II

摘要：題目要求可以先參考關于的這篇博客再看接下來的內容。思路一鏈表的形式我們可以通過例子，，，來說明。在遞歸中我們會將起始下標后的值依次加入當前結果集，并將結果集加入結果集數組中。如果遇到重復的數字，則繼續遍歷下一個數字，直至遍歷結束。題目要求 Given a collection of integers that might contain duplicates, nums, retur...

PascalXie 2019-08-15 10:48 評論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
【LC總結】回溯 (Subsets I II/Permutation I II/Combinatio

摘要：不同數包含重復數為的時候，表示在外層的循環正在被使用，所以當前循環遇到為一定要跳過。對當前循環要添加的數組，在添加當前元素后進行遞歸，遞歸之后要將當前元素的使用標記改為，表示已經使用和遞歸完畢，然后再將這個元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

tuomao 2019-08-14 15:53 評論0 收藏0
Subsets 系列 Leetcode解題記錄

摘要：寫這個系列是因為紀念一下去年的今天，就是年的月號，刷題第一天，今天是一周年紀念日。排除，就是返回一空的。復雜度分析算法課講過，這個復雜度是指數次，能實現出來就行了，沒法優化。復雜度分析不分析了，反正指數次。 Subsets 寫這個系列是因為紀念一下去年的今天，就是2015年的9月14號，刷題第一天，今天是一周年紀念日。當時只敢做easy還得抄答案的我想啥時候能做上medium啊，事到如...

gityuan 2019-08-14 14:41 評論0 收藏0
[Leetcode] Subset 子集

摘要：深度優先搜索復雜度時間空間遞歸?？臻g思路這道題可以轉化為一個類似二叉樹的深度優先搜索。另外需要先排序以滿足題目要求。新的集合要一個新的，防止修改引用。 Subset I Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in n...

hzc 2019-08-14 12:23 評論0 收藏0