找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3146|回复: 8
收起左侧

[基础刷题题目讨论] [google面试题]Max Cycle Length的解法

[复制链接]
发表于 11-30-2014 04:27 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-1-2014 01:21 AM 编辑

[Google面试题]Max Cycle Length
http://www.meetqun.com/forum.php ... &tid=931&fromuid=12
(出处: 美国米群网 - 海外华人留学生最大面试求职社交平台 - 计算机 商科 面试 面经 内推 刷题 算法 职场 绿卡 家庭 休闲)

这个题刚看到感觉不难,然后看了两个回帖子,感觉多少都有点问题。第二个java的代码,应该基本是对的,但是复杂度是O(n^2)的并非O(n)……
题目好像没说太清楚,感觉需要考虑:
如果数组元素不在[0..n - 1]我们认为是断裂,即无法走到下一个节点。
如果没有断裂,一定有圈。

如何找到圈?
其实这种图叫做function graph,即每个节点出度为1。到了x后就要走到f(x)去。这种图的特点是,每个强连通分支,最多只有一个圈。
其实我们需要两个东西:一个显然标记哪些节点到没到过,第二个这次经过了哪些节点。之所以要考虑本次,是因为我们可能走到了之前走过的节点,而那些节点可能根本不是一个圈(当然有断裂),比如1->2->3->4, 然后5->2,虽然我们从5开始也能走到2,但是并没有圈。 而且即使有圈我们也不用考虑。 比如1->2->3->4->2, 和5->2。 因为之前已经找到2->3->4->2这样一个圈,所以5->2即使发现圈也没用。
所以:
(1) 我们只要走到一个走过的节点或者断裂,就可以停止本次找寻
(2) 结束时如果停止的节点时本轮里经过的,我们就找到一个圈。 比如1->2->3->4->2 。


那么如何统一用一个东西既标记是不是本轮,又标记历史? (当然用两个bool数组或者hashset之类都可以)。可以用时间戳。时间从0开始,没走过的节点时间戳都设置为-1。时间戳不断累加,每轮第一个节点i,记录下来时间戳ts。最终结束时,我们的节点x的时间戳满足ts[x] >= ts,就是本轮经过的,否则就是之前经过的。如果是本轮第二次经过ts[x],因为时间戳不断自递增, 当前时间戳now与之前ts[x]的差就是圈的长度。
于是可以得到,复杂度为O(n),(因为每个节点至多访问1次),且很短很美观的代码:
  1. int maxCycle(vector<int> &a) {
  2. int n = a.size(), answer = 0, now = 0;
  3. vector<int> ts(n, - 1);
  4.         for (int i = 0; i < n; ++i) {
  5.                 if (ts[i] < 0) {
  6.                         int x;
  7.                         for (x = i;(x >= 0) && (x < n) && (ts[x] < 0); ts[x] = now++, x = a[x])
  8.                         ;
  9.                         if ((x >= 0) && (x < n) && (ts[x] >= ts[i])) {
  10.                                 answer = max(answer, now - ts[x]);
  11.                         }
  12.                 }
  13.                
  14.         }
  15.         return answer;
  16. }
复制代码



本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

0

主题

0

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 11-30-2014 08:22 PM | 显示全部楼层
赞这句精髓 ”我们只要走到一个走过的节点或者断裂,就可以停止本次找寻“
这个当前时间戳+本轮开始时间戳也是极好的,要不然还要很麻烦地去数圈大小,容易出错

补充内容 (11-30-2014 08:51 PM):
2楼2b, 请忽略2楼的第2句话
 楼主| 发表于 11-30-2014 08:23 PM | 显示全部楼层
lambdai 发表于 11-30-2014 08:22 PM
赞这句精髓 ”我们只要走到一个走过的节点或者断裂,就可以停止本次找寻“
这个当前时间戳+本轮开始时间戳 ...

时减法吧。。。
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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