一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1494|回复: 5
收起左侧

Indeed OA Coding Test #6

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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的数目
. 1point 3acres 璁哄潧
例如: . From 1point 3acres bbs
Input: N = 5, array = {1, 2, 3, 4, 5}. more info on 1point3acres.com
Output: 4. from: 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
因为要改变2, 3, 4, 5。比如都去指向1,或者1<-2<-3<-4<-5, etc..鐣欏璁哄潧-涓浜-涓夊垎鍦

. From 1point 3acres bbs


评分

3

查看全部评分

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

使用道具 举报

adampig 发表于 2016-2-4 14:44:13 | 显示全部楼层
完全不明白为什么筒子们都要用啥union find

  1. def findMinChange(arr):
  2.     if len(arr) <= 1:
  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, {})
  10.             if not result:
  11.                 count += 1
  12.         i += 1
  13.     return count
  14. . from: 1point3acres.com/bbs
  15. def recurCheck(i, arr, goodLookup, loopLookup):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.     if i in loopLookup:.1point3acres缃
  17.         return False
    . visit 1point3acres.com for more.
  18.     if i in goodLookup:
  19.         return True
  20.     loopLookup[i] = True
  21.     ret = recurCheck(arr[i] - 1, arr, goodLookup, loopLookup)
  22.     goodLookup[i] = True
  23.     return ret
    . Waral 鍗氬鏈夋洿澶氭枃绔,
复制代码
回复 支持 反对

使用道具 举报

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使用了吗
.鏈枃鍘熷垱鑷1point3acres璁哄潧
用了啊,就是为0的那个不算进count。最后find parent不为0的那些是需要调节的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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