logo
Redian新闻
>未名空间
>pets - 心有所宠
>
[活动]我和病果还有娃们的一天
avatar
[活动]我和病果还有娃们的一天# pets - 心有所宠
s*9
1 楼
Given an array of integers where each element points to the index of the
next element how would you detect if there is a cycle in this array?
Glassdoor上看来的，题目有点不清楚，我猜应该是指向自己就算结束吧，或者指向空
就结束。
O(n)的解法怎么做？
avatar
y*u
2 楼
讲昨天好了，周六，快8点起床，给猫娃们挖沙盆吃早饭，海海花花在台子上吃，黑黑
在台子下面吃，果果在笼子里吃。果吃饭的时候左脚弯曲，脚被撑地，俺把小脚丫翻过
来，用手托着，可以感觉到小脚丫还是有力气的。
然后俺去溜狗，俺只负责让辣椒吁吁便便大概15分钟就回家，然后辣椒吃早饭。
LD起床后再带辣椒出去走大圈，两个人去看鱼看漂亮妞不带我。
同时俺就自己冲凉洗漱，自己吃早饭，加点火腿在炒蛋里，还不错，吃的高兴把LD的那
份也吃掉了。然后俺就去给果果吃药打针，用HALO吹吹哄她开心给她按摩，很不成功，
果很生气，面对沙盆背对我，只好放弃。
俺就打开电脑，看“智者无敌”，努力猜测谁是白鸽，突然听到猫的“嘶嘶”声，以为
有猫打架，过去一看，黑黑冲着5米外的海海在生气。海海最近追求黑黑不成功，非常
落魄，只好跟着辣椒混。
然后俺就蹂躏海海花花，试图蹂躏小黑失败。这时候LD回来了，俺们就一起把果抱出笼
子扶着她并抬高右手，鼓励她用左手，左手仍然不受控制，但可以撑住用力。果依然很
生气，边骂骂咧咧边吃吹吹，辣椒过来打酱油被果扇了个大耳光。
12：30，俺去接上俺的挂名娃们，带他们去参加adotpion events, 一个娃淘气，我抓
了快20分钟才抓到，害我迟到。EVENTS上很多小朋友来抱猫猫，还有个好漂漂的美女义
工，俺很色的跟她套了半天近乎。
5点多回家，LD决定因为天很热，所以我们要吃火锅，吃的时候辣椒在边上很激动。
吃过晚饭，LD带辣椒出门，我喂猫。海海花花黑黑基本上都在睡觉，被饭香惊醒开吃。
果果也在睡觉，也被惊醒开吃，然后吃药，小妞心情不错，让我按摩了10几分钟。LD回
来，试图蹂躏果果，果非常愤怒，甚至用伤手反抗，LD很开心，认为这样有助于康复锻
炼，于是就牺牲自己的大粗手指头和果斗争。
结束。
照片有笼子里的果，果用伤手洗脸，果的小脚丫，
善良的花花
落魄的海海和辣椒，
生气地黑黑，
还有贞烈果对抗咸猪手
最后上几个我的挂名娃
avatar
a*y
3 楼
没看明白遮体什么意思，给个例子？
avatar
y*u
4 楼
继续
avatar
h*6
5 楼
A[i] = j, A[j]是A[i]的下一个元素。
可以把出现过的index都hash起来，然后每次读一个A[i],去找有没有出现过。遍历完了
都没有出现过的话就没有环。
avatar
y*u
6 楼
我带去的娃都很愤青，还有和小美女一起工作，心情会很好

【在 y*********u 的大作中提到】
: 继续
avatar
g*g
7 楼
或者做那个+1, +2的linked list找环，啥时候追上了就是环。

【在 h********6 的大作中提到】
: A[i] = j, A[j]是A[i]的下一个元素。
: 可以把出现过的index都hash起来，然后每次读一个A[i],去找有没有出现过。遍历完了
: 都没有出现过的话就没有环。
avatar
B*t
8 楼
大赞充实的一天啊！
辣椒跟猫猫都相处的很好啊！好像我们家Bogart怕猫的厉害。

【在 y*********u 的大作中提到】
: 讲昨天好了，周六，快8点起床，给猫娃们挖沙盆吃早饭，海海花花在台子上吃，黑黑
: 在台子下面吃，果果在笼子里吃。果吃饭的时候左脚弯曲，脚被撑地，俺把小脚丫翻过
: 来，用手托着，可以感觉到小脚丫还是有力气的。
: 然后俺去溜狗，俺只负责让辣椒吁吁便便大概15分钟就回家，然后辣椒吃早饭。
: LD起床后再带辣椒出去走大圈，两个人去看鱼看漂亮妞不带我。
: 同时俺就自己冲凉洗漱，自己吃早饭，加点火腿在炒蛋里，还不错，吃的高兴把LD的那
: 份也吃掉了。然后俺就去给果果吃药打针，用HALO吹吹哄她开心给她按摩，很不成功，
: 果很生气，面对沙盆背对我，只好放弃。
: 俺就打开电脑，看“智者无敌”，努力猜测谁是白鸽，突然听到猫的“嘶嘶”声，以为
: 有猫打架，过去一看，黑黑冲着5米外的海海在生气。海海最近追求黑黑不成功，非常
avatar
l*c
9 楼
Yes, this is what I read and forgot.

【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
avatar
s*i
10 楼
第三张可爱
我也看了点智者无敌
avatar
a*y
11 楼
这个不就是hash这个index就行了吗？
bool FindCycle(int a[], int n)
{
std::map indexmap;
map::iterator it;
for (int i = 0; i < n;i++)
{
indexmap[i] = false;
}
indexmap[0] = true;
for (int i = 0; i < n; i++)
{
if( indexmap[a[i]])
return true;
else
indexmap[a[i]] = true;
}
return false;
}
avatar
f*n
12 楼
这标准的温馨家庭动物园
avatar
h*6
13 楼
这个题可以不用吧，有index的话就不用和linked list一样判断追没追上了

【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
avatar
s*M
14 楼
我佩服你的理由 里面
又多了一条
养了这么多家伙，还有勇气上木地板。。。。
avatar
g*g
15 楼
这就是空间和时间的取舍了。恐怕两者都得知道。

【在 h********6 的大作中提到】
: 这个题可以不用吧，有index的话就不用和linked list一样判断追没追上了
avatar
g*x
16 楼
果果看起来不错，继续加油！
avatar
h*6
17 楼
恩，的确

【在 g*****g 的大作中提到】
: 这就是空间和时间的取舍了。恐怕两者都得知道。
avatar
y*a
18 楼
果果加油，快点恢复
avatar
s*9
19 楼
这个有问题吧？
a[0] = 2
a[1] = 2
a[2] = null
没有cycle, 但是函数返回true。

【在 a*******y 的大作中提到】
: 这个不就是hash这个index就行了吗？
: bool FindCycle(int a[], int n)
: {
: std::map indexmap;
: map::iterator it;
: for (int i = 0; i < n;i++)
: {
: indexmap[i] = false;
: }
: indexmap[0] = true;
avatar
w*o
20 楼
照片太美了，美猫+美女，太养眼了。辣妈的文字也一如既往的逗~~
avatar
p*2
21 楼

感觉你访问每一个点的时候，把内容变成负数，这样你再次访问的时候就知道有环了。

【在 s*****9 的大作中提到】
: 这个有问题吧？
: a[0] = 2
: a[1] = 2
: a[2] = null
: 没有cycle, 但是函数返回true。
avatar
y*u
22 楼
哈，是Laminate，俺们就是为了辣椒铺的，现在后悔没把楼上也铺上，想再铺都不知道
怎么安置猫猫们

【在 s******M 的大作中提到】
: 我佩服你的理由 里面
: 又多了一条
: 养了这么多家伙，还有勇气上木地板。。。。
avatar
m*d
23 楼
数组的问题是可能有子数组是循环。比如[null，2，3，null，5，4，6]。所以必须每
一个都遍历到。判断的时候也要考虑可能是子数组循环。
avatar
y*u
24 楼
大佬本性太善良

【在 B****t 的大作中提到】
: 大赞充实的一天啊！
: 辣椒跟猫猫都相处的很好啊！好像我们家Bogart怕猫的厉害。
avatar
a*y
25 楼
how do you store NULL in an int array?
avatar
y*u
26 楼
多谢！

【在 g****x 的大作中提到】
: 果果看起来不错，继续加油！
avatar
m*d
27 楼
例如不存在的index: -1或者大于数组长度的值。
关键在于这个和linked list那题有小的不同。
avatar
y*u
28 楼
多谢！

【在 y*********a 的大作中提到】
: 果果加油，快点恢复
avatar
f*s
29 楼

如果一个元素自己指向自己,也是个环吧?比如a[2]=2,上面这个算法就查不出来了.

【在 a*******y 的大作中提到】
: 这个不就是hash这个index就行了吗？
: bool FindCycle(int a[], int n)
: {
: std::map indexmap;
: map::iterator it;
: for (int i = 0; i < n;i++)
: {
: indexmap[i] = false;
: }
: indexmap[0] = true;
avatar
b*i
30 楼
记得更新啊。

【在 y*********u 的大作中提到】
: 讲昨天好了，周六，快8点起床，给猫娃们挖沙盆吃早饭，海海花花在台子上吃，黑黑
: 在台子下面吃，果果在笼子里吃。果吃饭的时候左脚弯曲，脚被撑地，俺把小脚丫翻过
: 来，用手托着，可以感觉到小脚丫还是有力气的。
: 然后俺去溜狗，俺只负责让辣椒吁吁便便大概15分钟就回家，然后辣椒吃早饭。
: LD起床后再带辣椒出去走大圈，两个人去看鱼看漂亮妞不带我。
: 同时俺就自己冲凉洗漱，自己吃早饭，加点火腿在炒蛋里，还不错，吃的高兴把LD的那
: 份也吃掉了。然后俺就去给果果吃药打针，用HALO吹吹哄她开心给她按摩，很不成功，
: 果很生气，面对沙盆背对我，只好放弃。
: 俺就打开电脑，看“智者无敌”，努力猜测谁是白鸽，突然听到猫的“嘶嘶”声，以为
: 有猫打架，过去一看，黑黑冲着5米外的海海在生气。海海最近追求黑黑不成功，非常
avatar
p*3
31 楼

为什么这个不需要额外空间？

【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
avatar
A*e
32 楼
娃果然很愤青，美女果然很美女。

【在 y*********u 的大作中提到】
: 继续
avatar
k*t
33 楼
两个指针(slow, fast)就够啦，判断list有无loop也不需要额外空间。贴了个代码，比
较ugly, 凑合着看吧
bool hasLoop(int arr[], int len){

int slow = 0;
int fast = 0;
int cur = 0;
while(cur < len)
{
if(arr[slow] != -1)
{
slow = arr[slow];
}
else
{
++slow;
fast = slow;
cur = slow;
continue;
}

int i = 0;
while(i < 2 && arr[fast] != -1)
{
fast = arr[fast];
++i;
}
if(i < 2)
{
++fast;
slow = fast;
cur = fast;
}
else
{
if(fast == slow){
return true;
}
}
}
return false;
}

【在 p*****3 的大作中提到】
:
: 为什么这个不需要额外空间？
avatar
r*l
34 楼
好大的一家子～～～总算一次看全了。。。
bless果果早点出笼啊～～
avatar
r*h
35 楼
我的想法是，用两个set
一个来记录当前路径上出现过的元素（判断当前元素是否在环上）
一个记录所有访问过的元素（防止重复判断）
O(N)空间O(N)时间
bool hasRing(int A[], int N){
unordered_set s, visited;
for(int i=0; iif(visited.find(i) == visited.end()){
int curr = i;
while(curr>=0 && currif(s.find(curr) != s.end()){
return true;
}
s.insert(curr);
visited.insert(curr);
curr = A[curr];
}
s.clear();
}
}
return false;
}
其他想法我也考虑了一下
如果每个节点都用追赶法判断是否有环的话，时间复杂度变成O(N^2)
另外把访问过的节点设置成-1是不可行的
比如说下面的例子
1->2->3->4->5->END
6->7->3->4->5->END
实际上并没有环，但是第二次访问到3的时候发现节点的next是-1
avatar
t*u
36 楼
这阵子忙
果果复查了吗？结果如何？
avatar
Y*f
37 楼
这个就是有向图（这里每个节点只有一条始发边）的环问题。一个visit数组，一个
visitStack数组（回溯的时候要重置），进行dfs就可以了。

【在 s*****9 的大作中提到】
: Given an array of integers where each element points to the index of the
: next element how would you detect if there is a cycle in this array?
: Glassdoor上看来的，题目有点不清楚，我猜应该是指向自己就算结束吧，或者指向空
: 就结束。
: O(n)的解法怎么做？
avatar
b*m
38 楼
为啥娃儿们好像都胖了？
avatar
x*0
39 楼
mark
avatar
A*R
40 楼
照片好看，写得也幽默，美美养眼，赞！
Bless 果果早日痊愈！
avatar
c*p
41 楼
哦，以前看到这道题，但依然不知道怎么作。。。
avatar
w*u
42 楼
祝福果果早日痊愈！
avatar
w*z
43 楼
我觉得得先把边界条件都define了
avatar
N*y
44 楼
为啥天热要吃火锅呢？
海海是我的菜。
avatar
a*a
45 楼
如果数组是well formed. 就是for any 0<=i断有没有duplicated entry就行？如果没有，一定有circle.
avatar
j*u
46 楼
果果加油！
avatar
y*u
47 楼
多谢大家，刚才和vet通了电话，说那些刺激反映也可能是上臂带动的deep pain
response,不能太乐观。另外叫我继续按摩和伸展，每天5－10分钟就可以了，我觉得我
前几天操的太厉害了，希望没什么副作用。
avatar
j*n
48 楼
真好呀，果果！

【在 y*********u 的大作中提到】
: 讲昨天好了，周六，快8点起床，给猫娃们挖沙盆吃早饭，海海花花在台子上吃，黑黑
: 在台子下面吃，果果在笼子里吃。果吃饭的时候左脚弯曲，脚被撑地，俺把小脚丫翻过
: 来，用手托着，可以感觉到小脚丫还是有力气的。
: 然后俺去溜狗，俺只负责让辣椒吁吁便便大概15分钟就回家，然后辣椒吃早饭。
: LD起床后再带辣椒出去走大圈，两个人去看鱼看漂亮妞不带我。
: 同时俺就自己冲凉洗漱，自己吃早饭，加点火腿在炒蛋里，还不错，吃的高兴把LD的那
: 份也吃掉了。然后俺就去给果果吃药打针，用HALO吹吹哄她开心给她按摩，很不成功，
: 果很生气，面对沙盆背对我，只好放弃。
: 俺就打开电脑，看“智者无敌”，努力猜测谁是白鸽，突然听到猫的“嘶嘶”声，以为
: 有猫打架，过去一看，黑黑冲着5米外的海海在生气。海海最近追求黑黑不成功，非常
avatar
l*e
49 楼
加油，果果和辣妈辣爸。

【在 y*********u 的大作中提到】
: 多谢大家，刚才和vet通了电话，说那些刺激反映也可能是上臂带动的deep pain
: response,不能太乐观。另外叫我继续按摩和伸展，每天5－10分钟就可以了，我觉得我
: 前几天操的太厉害了，希望没什么副作用。
avatar
Z*i
50 楼
好多猫猫啊。。。。
我刚刚摸我foster的小猫时候还感叹，这么好的小猫还没人领。。。看来到处都不容易
啊
avatar
t*e
51 楼
这一天充实的！

【在 y*********u 的大作中提到】
: 讲昨天好了，周六，快8点起床，给猫娃们挖沙盆吃早饭，海海花花在台子上吃，黑黑
: 在台子下面吃，果果在笼子里吃。果吃饭的时候左脚弯曲，脚被撑地，俺把小脚丫翻过
: 来，用手托着，可以感觉到小脚丫还是有力气的。
: 然后俺去溜狗，俺只负责让辣椒吁吁便便大概15分钟就回家，然后辣椒吃早饭。
: LD起床后再带辣椒出去走大圈，两个人去看鱼看漂亮妞不带我。
: 同时俺就自己冲凉洗漱，自己吃早饭，加点火腿在炒蛋里，还不错，吃的高兴把LD的那
: 份也吃掉了。然后俺就去给果果吃药打针，用HALO吹吹哄她开心给她按摩，很不成功，
: 果很生气，面对沙盆背对我，只好放弃。
: 俺就打开电脑，看“智者无敌”，努力猜测谁是白鸽，突然听到猫的“嘶嘶”声，以为
: 有猫打架，过去一看，黑黑冲着5米外的海海在生气。海海最近追求黑黑不成功，非常
相关阅读
今天被四月给惹毛了！于是。。[合集] 3 + 1[合集] 跳蚤药能停了么？[合集] 新猫妈请教猫猫尿尿问题(有pp)新人携俩猫宝报到为嘛奥利奥从早到晚目不转睛地盯着我看50个包子求祝福猫吃饭的时候总是泪流满面求宽恕petplan的申请表格需要签字么？眼睛奇痒无比，求助怎么办？纠结阿Ultimate dog tease帮朋友问：养兔子去哪买兔草便宜？（张老三请进~）大家慢点灌再问一下猫bb的问题各位猫奴觉得养猫的最幸福时刻是什么？森林之王100002发现有些猫主人连小猫几周都说不清，无语！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。