leetcode77. 组合python
2021/11/3 22:11:12
本文主要是介绍leetcode77. 组合python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
题解:
1.按照题目给出的示例,相同数字按照不同顺序的排列组合看作一个。
2.题目中示例1的搜索过程如下:
3.实现思路:
<1>设置一个nums数组,共有n+1个数字,从0-n
<2>设置一个used数组,n+1个数字,初始化为全0,记录nums[i]是否已经被搜索(统一设置为n+1个数字之后,搜索范围从1-n)
<3>res保存最终结果,combination记录当前搜索过程,depth记录当前搜索树深度。
<4>定义一个dfs函数,如果当前depth=k,说明找到一个k个数字的组合,将combination加入res并返回。否则i从idx到n开始搜索,如果对应的used[i]=0,说明对应的nums[i]没有被使用,加入combination,然后进入下一层搜索。下一层从i+1开始避免重复!
<5>回溯,将对应used重新设为0,从combination中删除对应数字。
class Solution(object): def combine(self, n, k): used = [0 for i in range(n+1)] nums = [0] for i in range(1,n+1): nums.append(i) res = [] depth = 0 def dfs(idx,used,depth,combination,res): if depth == k: res.append(combination[:]) return for i in range(idx,n+1): if used[i]==0: used[i]=1 combination.append(nums[i]) depth = depth+1 dfs(i+1,used,depth,combination,res) depth = depth-1 used[i]=0 combination.pop() dfs(1,used,depth,[],res) return res
结果通过,但是执行用时很长。
这篇关于leetcode77. 组合python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04Python外包有哪些常见的主要库-icode9专业技术文章分享
- 2024-10-02基于深度学习的钢铁缺陷检测系统(yolov8、注意力机制、PyQt5界面、Python)
- 2024-10-01怎么用python搭建一个系统-icode9专业技术文章分享
- 2024-09-30Python基础入门教程
- 2024-09-30获取参数学习:Python中的基础教程
- 2024-09-30Python编程基础详解
- 2024-09-29点击加载学习:Python编程基础教程
- 2024-09-29数据科学五大Python前端库:第二部分
- 2024-09-27使用python 将ETH账户的资产打散
- 2024-09-26Python编程基础