📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1123| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 542. 01 matrix 和 733. floor fill 有什么区别 (给看猫猫,求帮助)

全局:

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

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

x

想请教一下,为什么floor fill bfs 和 dfs都可以用, 但01 matrix bfs却是最好方案?
为什么需要在01 matrix保存中间状态(是否看过这个cell),而floor fill不需要呐?

上一篇:leetcode1040:请问面试有人遇见过侧重考constructive algorithms/构造算法的情况吗?
下一篇:刷题心得
推荐
argumentt 2024-9-27 14:18:45 | 只看该作者
全局:
找最短距离要用bfs,因为dfs可能会走错方向,worst case时间复杂度是指数级
遍历全图既可以bfs也可以dfs,因为方向无所谓,两种时间复杂度一样

不改节点状态的时候,需要记录走过的路径
改变节点状态的时候,节点状态隐含了走过的路径这一信息,不需要额外再记录
回复

使用道具 举报

🔗
ygmm 2024-10-14 11:52:24 | 只看该作者
全局:
看题目要求。如果733 是求最短时间能完成,可能也得使用BFS。
回复

使用道具 举报

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

本版积分规则

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