近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2398|回复: 5
收起左侧

Indeed OA Coding Test #6

[复制链接] |试试Instant~ |关注本帖
huangbow 发表于 2015-11-11 13:17:38 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Indeed - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
做的是OA Coding Test #6。
题目是球把一个node list中的全部node变成good node需要改变的node数目。说是list,其实就是一个array,每个位置就代表一个node,比如array[i]就表示第i个node。array[i]的值就表示它指向的node。node的数目在1到N之间,所以数组每个元素的值也在这个范围。


good node的定义是至少满足以下任意一点:
1.它是头节点(node 1)
2.它指向头节点
3.它指向一个good node

题目输入为: N, array
输出为:需要改变的node的数目
.鐣欏璁哄潧-涓浜-涓夊垎鍦
例如:
Input: N = 5, array = {1, 2, 3, 4, 5}. more info on 1point3acres.com
Output: 4. more info on 1point3acres.com

因为要改变2, 3, 4, 5。比如都去指向1,或者1<-2<-3<-4<-5, etc.




评分

3

查看全部评分

TR07 发表于 2015-12-4 12:39:47 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
多谢楼主,刚考到这题了。参考了网上union find的解法,顺利解决了。求过啊
回复 支持 反对

使用道具 举报

adampig 发表于 2016-2-4 14:44:13 | 显示全部楼层
关注一亩三分地微博:
Warald
完全不明白为什么筒子们都要用啥union find

  1. def findMinChange(arr):
  2.     if len(arr) <= 1:. more info on 1point3acres.com
  3.         return 0
  4.     i = 1
  5.     goodLookup = {0:True}
  6.     count = 0
  7.     while i < len(arr):
  8.         if i not in goodLookup:
  9.             result = recurCheck(i, arr, goodLookup, {}). 鍥磋鎴戜滑@1point 3 acres
  10.             if not result:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.                 count += 1
  12.         i += 1
  13.     return count

  14. def recurCheck(i, arr, goodLookup, loopLookup):
  15.     if i in loopLookup:
  16.         return False
  17.     if i in goodLookup:
  18.         return True.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.     loopLookup[i] = True
  20.     ret = recurCheck(arr[i] - 1, arr, goodLookup, loopLookup)
  21.     goodLookup[i] = True. 鍥磋鎴戜滑@1point 3 acres
  22.     return ret
复制代码
回复 支持 反对

使用道具 举报

zsz1990ustc 发表于 2016-2-16 13:03:22 | 显示全部楼层
还是觉得 union find 更直观更容易想些。转载一个解法,感觉很有启发:http://yuanhsh.iteye.com/blog/2200515
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-2-20 08:37:52 | 显示全部楼层
zsz1990ustc 发表于 2016-2-16 13:03
还是觉得 union find 更直观更容易想些。转载一个解法,感觉很有启发:http://yuanhsh.iteye.com/blog/2200 ...

下标为0 的那个node使用了吗
回复 支持 反对

使用道具 举报

zsz1990ustc 发表于 2016-2-24 02:01:21 | 显示全部楼层
haoxuango 发表于 2016-2-20 08:37
下标为0 的那个node使用了吗

用了啊,就是为0的那个不算进count。最后find parent不为0的那些是需要调节的。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-29 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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