回溯算法part5 | * 491.递增子序列 * 46.全排列 * 47.全排列 II

news/2024/11/7 12:42:19/

文章目录

  • 491.递增子序列
    • 思路
    • 思路代码
    • 官方题解
    • 代码
    • 困难
  • 46.全排列
    • 思路
    • 思路代码
    • 困难
  • 47.全排列 II
    • 思路
    • 思路代码
    • 困难
  • 今日收获


491.递增子序列

491.递增子序列

思路

同样有去重和树节点需求,但与之前的排列不同的是,这次子序列要和原题一致,所以不能采用排序和used数组的方式。
同树层选择map字典记录使用过的树,如果被使用过或者非递增,continue

if used[nums[i]]||(len(path)>0&&nums[i]<path[len(path)-1]){continue}

枚举子序列2的n次方,写入需要n,所以时间复杂度
O ( 2 n ∗ n ) O(2^n*n) O2nn

思路代码

func findSubsequences(nums []int) [][]int {res:=[][]int{}path:=[]int{}var backtrack func(startindex int)backtrack = func(startindex int){if len(path)>=2{temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)}used:=make(map[int]bool)for i:=startindex;i<len(nums);i++{if used[nums[i]]||(len(path)>0&&nums[i]<path[len(path)-1]){continue}used[nums[i]]=truepath = append(path,nums[i])backtrack(i+1)path=path[:len(path)-1]}}backtrack(0)return res
}

官方题解

思路相同,不止可以用哈希表去重,由于数的范围是有限的,也可以用数组来模拟字典。

代码

var (res [][]intpath  []int
)
func findSubsequences(nums []int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(nums))dfs(nums, 0)return res
}
func dfs(nums []int, start int) {if len(path) >= 2 {tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)}used := make(map[int]bool, len(nums))   // 初始化used字典,用以对同层元素去重for i := start; i < len(nums); i++ {if used[nums[i]] {   // 去重continue}if len(path) == 0 || nums[i] >= path[len(path)-1] {path = append(path, nums[i])used[nums[i]] = truedfs(nums, i+1)path = path[:len(path)-1]}}
}

困难

非递增序列取子集去重问题,字典记录每次递归的同树层元素。


46.全排列

46.全排列

思路

不同于组合问题,不需要startindex,但是需要记录已经选择的数,递归的时候从剩下的未选择的数中选。
时间复杂度On*n!

思路代码

func permute(nums []int) [][]int {res:=[][]int{}path:=[]int{}used:=make([]bool,len(nums))var backtrack func()backtrack = func(){if len(path)==len(nums){temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)return}for i:=0;i<len(nums);i++{if !used[i]{path=append(path,nums[i])used[i]=truebacktrack()used[i]=falsepath=path[:len(path)-1]}}}backtrack()return res}

困难

不需要记录startindex,每次都从头开始,但排列问题需要一个used数组,标记已经选择的元素。


47.全排列 II

47.全排列 II

思路

需要去重,和之前组合去重思路相同,used数组去重同树层数。

思路代码

func permuteUnique(nums []int) [][]int {res:=[][]int{}path:=[]int{}used:=make([]bool,len(nums))sort.Ints(nums)var backtrack func()backtrack = func(){if len(path)==len(nums){temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)}for i:=0;i<len(nums);i++{if i>0&&nums[i]==nums[i-1]&&!used[i-1]{continue}if !used[i]{used[i]=truepath=append(path,nums[i])backtrack()used[i]=falsepath=path[:len(path)-1]}}}backtrack()return res}

困难

used数组中的数i如果为true代表在递归过程中使用过,如果i-1为false代表在同树层遍历过程中使用过。


今日收获

非递增序列取子集去重问题,字典记录每次递归的同树层元素。
排列问题同样需要used数组:
used数组中的数i如果为true代表在递归过程中使用过,如果i-1为false代表在同树层遍历过程中使用过。


http://www.ppmy.cn/news/258514.html

相关文章

sftp://xxx: /nfs/xxt/dataset

sftp://128.8.84.221: /nfs/dubhe-minio-uat/dataset是什么意思 这是一个 SFTP 协议的地址&#xff0c;它指向一个 NFS 文件系统的挂载点。具体来说&#xff0c;这个地址指向 IP 地址为 128.8.84.221 的服务器上的一个名为 “dataset” 的目录&#xff0c;这个目录在文件系统中…

100天精通Golang(基础入门篇)——第3天:Go语言的执行原理及常用命令、编码规范和常用工具

&#x1f337; 博主 libin9iOak带您 Go to Golang Language.✨ &#x1f984; 个人主页——libin9iOak的博客&#x1f390; &#x1f433; 《面试题大全》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &#x1f30a; 《I…

ValueError: Object arrays cannot be loaded when allow_pickle=False

一、问题 使用numpy读取数据时出现错误&#xff0c;ValueError: Object arrays cannot be loaded when allow_pickleFalse。 查了一下numpy.load()函数 用法 numpy.load(file, mmap_modeNone, allow_pickLeFalse, fix_mportsTrue, encoding‘ASCII’) 参数 file&#xff1a;…

havc是什么意思_hvac是什么意思

“hvac”的意思是&#xff1a;abbr.高压交流电(HighVoltageAlternatingCurrent)1、读音&#xff1a;[,etʃviesi]2、相关短语&#xff1a;HVACSystem 空调系统;空调通风系统;暖通空调hvacdesign 暖通空调设计;空通设计;空调设计HVACsystems hvac系统;空调系统hvacpiping 暖通空…

涡轮增压扫地机器人_智能扫地机器人哪个牌子好

生活中是不是经常遇到这样的问题&#xff1a;工作累了&#xff0c;没心情打扫卫生&#xff0c;智能扫地机器人的出现&#xff0c;大大降低了打扫家务的时间&#xff0c;给人们留出更多的闲暇时间享受生活。那么智能扫地机器人哪个牌子好&#xff1f;选购智能扫地机器人应该注意…

扫地机器人什么牌子的好 费电吗_扫地机器人什么牌子好?让我来告诉你吧

扫地机器人什么牌子好&#xff1f;让我来告诉你吧 2019年02月28日 16:40作者&#xff1a;厂商投稿编辑&#xff1a;刘明鹏文章出处&#xff1a;厂商稿 分享 随着科技的发展&#xff0c;家具清洁设备也越来越智能&#xff0c;传统的人工清洁也由智能扫地机器人和吸尘器等替代&am…

无线智能洗地机什么牌子好、2023智能洗地机实用推荐

由于上班时间过长&#xff0c;上班族的闲暇时间自然不多&#xff0c;如果不想浪费仅剩无多的休息时间来搞卫生&#xff0c;只能寻求一款清理力强且耗时短效率高的产品&#xff0c;而洗地机便是不错的选择。智能洗地机不仅集齐吸拖洗功能一体&#xff0c;部分洗地机还拥有滚刷自…

如何评价 Facebook 发布的数字货币 Libra?

一句话总结&#xff1a;Libra 最大的亮点&#xff0c;在于它是 Facebook 做的。 随着数字货币市场的迅速发展&#xff0c;各类加密货币层出不穷。然而&#xff0c;在这个领域中&#xff0c;Facebook 所推出的 Libra 显得尤为引人关注。那么&#xff0c;Libra 到底有何特点&…