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

[树/链表/图] 讨论个看到过多次的面经题

全局:

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

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

x
## Cooking Process, Workflow (graph 先找 head ,根据 head 找 path 的)

题目是排 workflow, 会给你一个 array of paired strings,比如

```
input:

[
[wash,chop],
  [cook,serve],
  [chop,cook]
]


output:

[[job1],[job2,job3],[job4,job5]]

其中只要是在一个[]里的 就说明可以同时进行这几个工作,但是job1 肯定是在job2 job3前面的
```

这里顺序代表 process 进行的顺序,比如 wash 要在 chop 前,cook 要在 serve 前,要你 return 一个满足顺序的 workflow

我的想法是,先记录每个head(indegree为0的),然后从每个head进行dfs,如果一个节点曾经被访问过,他的层数应该取最深的那层。最后按照层数输出这些节点。想过用bfs,但是因为要取最深那层 反而好像不方便

上一篇:周赛吐槽疗伤炫技休息室 - 9/12/2020
下一篇:140 word break ii time complexity
推荐
 楼主| Smilenceyu 2020-9-14 08:31:26 来自APP | 只看该作者
全局:
anonydieyoung 发表于 2020-09-13 17:03:53
谁告诉你拓扑排序不能分层?自己再把拓扑看一遍吧。
怎么戾气这么重。。
回复

使用道具 举报

全局:
Smilenceyu 发表于 2020-09-13 16:04:52
拓扑排序只能告诉一条总路径,并不能分层输出
谁告诉你拓扑排序不能分层?自己再把拓扑看一遍吧。
回复

使用道具 举报

推荐
qldx 2020-9-14 09:06:56 | 只看该作者
全局:
这个没关系,可以用bfs来进行,一层一层的更新
  1.    
  2. def findOrder(self, numCourses, prerequisites):
  3.         """
  4.         :type numCourses: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: List[int]
  7.         """
  8.         indegree = dict()#每个课程依赖于哪些课程
  9.         outdegree = dict()#每个课程决定哪些课程
  10.         for i,j in prerequisites:
  11.             if i not in indegree:
  12.                 indegree[i] = set()#{2:{1}}
  13.             indegree[i].add(j)
  14.             if j not in outdegree:
  15.                 outdegree[j] = set()# {1:{2}}
  16.             outdegree[j].add(i)

  17.         res = []
  18.         level = [i for i in range(numCourses) if i not in indegree]
  19.         res = [[i for i in range(numCourses) if i not in indegree]]
  20.         while level:
  21.             newlevel = []
  22.             for i in level:
  23.                 if i in outdegree:
  24.                     for j in outdegree[i]:
  25.                         indegree[j].remove(i)
  26.                         if len(indegree[j])==0:
  27.                             newlevel.append(j)
  28.             level = newlevel
  29.             res.append(level)
  30.         return res
复制代码
回复

使用道具 举报

本楼:
全局:
拓扑排序?
回复

使用道具 举报

🔗
 楼主| Smilenceyu 2020-9-14 07:04:52 | 只看该作者
全局:

拓扑排序只能告诉一条总路径,并不能分层输出
回复

使用道具 举报

🔗
qldx 2020-9-14 08:25:14 | 只看该作者
全局:
题目没看懂,一个[]里既可以同时进行,但又要求按照顺序是啥意思?比如这个例子,返回的是什么?是要求返回一个可行的顺序么,比如这题就是wash-chop-cook-serve?
回复

使用道具 举报

🔗
 楼主| Smilenceyu 2020-9-14 08:41:56 | 只看该作者
全局:
qldx 发表于 2020-9-14 08:25
题目没看懂,一个[]里既可以同时进行,但又要求按照顺序是啥意思?比如这个例子,返回的是什么?是要求返回 ...

不是的,是说每个[]是同时进行的,比如5之前需要3, 5之前也需要2, 2之前需要1

那么可以是 [ [1],  [2,3], [5] ]

而不能是 [ [1, 3], [2,5] ]
回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
🔗
qldx 2020-9-14 08:50:04 | 只看该作者
全局:
Smilenceyu 发表于 2020-9-14 08:41
不是的,是说每个[]是同时进行的,比如5之前需要3, 5之前也需要2, 2之前需要1

那么可以是 [ [1],  [ ...

那如果是说有先后顺序的必须要先满足前面的,没有任何先决条件的都可以同时进行的话,那不就是210. Course Schedule II的普通拓扑排序了么?
回复

使用道具 举报

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

本版积分规则

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