[Leetcode][python]Subsets/Subsets II/子集/子集 II

布满荆棘的人生 2022-06-07 12:19 330阅读 0赞

Subsets

题目大意

给定一个由不同数字组成的集合,罗列出该集合的所有子集。

解题思路

见下方代码

代码

纯思路

参考:
https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html
举个例子,集合[1]有[[],[1]]两个子集,当向其中添加一个元素时,[1,2]有[[],[1],[2],[1,2]]四个子集,可以看出来,在新添加一个元素的时候,是在原来子集的基础上,添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的,要先把所有元素都排序。

  1. class Solution(object):
  2. def subsets(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: List[List[int]]
  6. """
  7. result = [[]]
  8. for num in sorted(nums):
  9. result += [item + [num] for item in result]
  10. return result

沿用排列题DFS

  1. class Solution(object):
  2. def subsets(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: List[List[int]]
  6. """
  7. self.result = []
  8. nums.sort()
  9. for i in range(0, len(nums)+1):
  10. self.k = i
  11. self.combineHelper(0, [], nums)
  12. return self.result
  13. def combineHelper(self, length, temp, list_num):
  14. if length == self.k:
  15. self.result.append(temp[:]) # 需要用切片浅复制出一个新数组
  16. return
  17. for i, num in enumerate(list_num):
  18. temp.append(num)
  19. self.combineHelper(length+1, temp, list_num[i+1:])
  20. temp.pop()

Subsets II

题目大意

给定一个由不同数字组成的集合,罗列出该集合的所有子集。
有重复

解题思路

和上一题相同,问题在于如果有重复则会生成多余的子集。
参考:https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html
现在举个例子,集合[1]有[[],[1]]两个子集,当向其中添加一个元素时,[1,2]有[[],[1],[2],[1,2]]四个子集,可以看出来,在新添加一个元素的时候,是在原来子集的基础上,添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的,要先把所有元素都排序。

代码

沿用排列题DFS

  1. class Solution(object):
  2. def subsetsWithDup(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: List[List[int]]
  6. """
  7. result = [[]]
  8. nums.sort() # sort()直接修改原数组,sorted()返回排序后的数组,不修改原数组
  9. temp_size = 0
  10. for i in range(len(nums)):
  11. start = temp_size if i >= 1 and nums[i] == nums[i - 1] else 0
  12. temp_size = len(result) # 每次取到result最后一位,也就是从start一直到最后一位
  13. for j in range(start, temp_size):
  14. result.append(result[j] + [nums[i]])
  15. print result
  16. return result

总结

纯思路做法显然效率更高,此题标签还有位运算做法,有空。

发表评论

表情:
评论列表 (有 0 条评论,330人围观)

还没有评论,来说两句吧...

相关阅读

    相关 90. 子集 II

    90. 子集 II 给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。返回的解集中,子集可以按 任