【python-leetcode-子集类型】子集
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【python-leetcode-子集类型】子集,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1905字,纯文字阅读大概需要3分钟。
内容图文
![【python-leetcode-子集类型】子集](/upload/InfoBanner/zyjiaocheng/640/bebdc74a96594f7c8c2f8cd7208eb2a1.jpg)
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
由于是子集的第一题,暂时还没有套路。
方法一:直接看过程,假设我们现在有一个存储结果的数组res=[[]],nums=[1,2,3]
第一步:res=[[]]
第二步:res=[[],[1]]
第三步:res=[[],[2],[1],[1,2]]
第四步:res=[[],[3],[2],[2,3],[1],[1,3],[1,2,3]]
也就是说每次取出res中里面的一维数组,然后将当前nums中的数加进去,再和原来的res相加即可
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res=[[]] for num in nums: res=res+[tmp+[num] for tmp in res] return res
方法二:python中自带的库
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): for tmp in itertools.combinations(nums, i): res.append(tmp) return res
会单独再写一篇记录一下itertools的用法
方法三:回溯,解决子集这种问题的话一般就是这种方法了。不过不好理解。
回溯法的核心就是试错,碰到不符合要求的就返回。
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: global res res=[] self.helper(0,[],nums) return res def helper(self,i,tmp,nums): res.append(tmp) for j in range(i,len(nums)): self.helper(j+1,tmp+[nums[j]],nums)
其中的核心是遍历的下标以及将tmp带入到递归中。
输出:[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
捋一捋过程吧:
首先是res=[]
执行helper(0,[],[1,2,3])
然后res=[[]]
这里有个for j in range(0,3)
执行helper(1,[]+[1],[1,2,3])
然后res=[[],[1]]
这里有个for j in range(1,3)
执行helper(2,[1]+[2],[1,2,3])
然后res=[[],[1],[1,2]]
依次类推之后我们就有[[],[1],[1,2],[1,2,3]]
此时,别忘了我们还有for循环中没有循环完
for j in range(0,3)
for j in range(1,3)
for j in range(2,3)
与子集有关的题目还有:
参考:
作者:powcai
链接:https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/
来源:力扣(LeetCode)
内容总结
以上是互联网集市为您收集整理的【python-leetcode-子集类型】子集全部内容,希望文章能够帮你解决【python-leetcode-子集类型】子集所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。