查看: 452|回复: 6
收起左侧

[树/链表/图] Graph类题目求解答

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
这道题大家会考虑怎么做呢,有没有什么类似的Leetcode题目推荐。。我感觉是bfs+backtracking,但是具体没想清楚!回答加米加米
B4606347-2296-47E3-A478-DF5BED23176E.jpg

评分

参与人数 1大米 +5 收起 理由
14417335 + 5 给你点个赞!

查看全部评分


上一篇:95% 的算法都是基于这 6 种算法思想 【请赏大米】
下一篇:刷200+题自我总结
lyyc 2022-8-12 06:30:11 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (206)
 
 
0% (1)    👎
AndreaYl 发表于 2022-8-11 18:23
感谢🙏!(今天加米到上限了,明天跟你补上)但我还有一个问题题目说可能会有多个长度相同的List, ...

不用,在更新的时候自定义比较就行,如果长度不一样选长的,长度一样选字典序小的
回复

使用道具 举报

coolwenwen 2022-8-12 05:49:50 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (56)
 
 
1% (1)    👎
我想用dfs加memo。memo里记录的是这首歌后头最多可以跟多少首。

补充内容 (2022-08-12 05:58 +08:00):
抱歉没有想太明白。如果是要list的话,可能需要一个queue把所有的path的存起来,然后不断地增长这里头每一个path的两端,用memo的话可以减少重复搜索。我自己先写写看。

评分

参与人数 1大米 +1 收起 理由
AndreaYl + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| AndreaYl 2022-8-12 05:55:43 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
coolwenwen 发表于 2022-08-11 14:49:50
我想用dfs加memo。memo里记录的是这首歌后头最多可以跟多少首。
这个题目最后需要返回最长的list不是长度,那在我们找到最长的长度之后怎么得到最长的list呢,小白求教
回复

使用道具 举报

lyyc 2022-8-12 06:00:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (206)
 
 
0% (1)    👎
这是个NP困难问题所以只能暴力。用回溯遍历整张图,开一个list记录当前的歌单,再搞一个全局变量记录最长的,如果当前歌单比已经记录的长则更新。
回复

使用道具 举报

 楼主| AndreaYl 2022-8-12 06:23:40 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
lyyc 发表于 2022-08-11 15:00:22
这是个NP困难问题所以只能暴力。用回溯遍历整张图,开一个list记录当前的歌单,再搞一个全局变量记录最长的,如果当前歌单比已经记录的长则更新。
感谢🙏!(今天加米到上限了,明天跟你补上)但我还有一个问题题目说可能会有多个长度相同的List,按照题目给的判断规则选择某个,那这样的话是只能先记下所有的最长,然后再筛选一遍吗?
回复

使用道具 举报

nanoice 2022-8-12 06:56:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (5217)
 
 
17% (1126)    👎
请问这道题在哪能做,我有兴趣做一下这道题
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表