谷歌ng vo

johnnya

请问下楼主，Facebook的好友推荐怎么做的啊，是直接brute force嘛

lllxin37

第一题想法，输入是forest和set

// forest contains root nodes on trees;
// toRemove cotains the node object to be deleted from forest
// use dfs to through all children nodes, if anything match, remove the subtree, also remove the node from Set
// the only concern is how HashSet checks contains on TreeNode. It depends on hashcode method
public List<TreeNode> delNodes(List<TreeNode> forest, Set<TreeNode> toRemove) {
List<TreeNode> ret = new ArrayList<>();
for (TreeNode curRoot : forest) {
if (toRemove.contains(curRoot)) {
toRemove.remove(curRoot);
continue;
}
ret.add(curRoot);
}
// use preorder to remove all nodes. It's possible that after below,
// toRemove not empty.
// for example if we have 3 is 5's children. And both 5, 3 in toRemove set.
// preorder will remove 5 first. Not touch 3.
for (TreeNode curRoot : ret) {
preorder(curRoot, toRemove);
}
return ret;
}
private TreeNode preorder(TreeNode cur, Set<TreeNode> toRemove()) {
if (cur == null) return null;
if (toRemove.contains(cur)) {
toRemove.remove(cur);
return null;
}
List<TreeNode> newChildren = new ArrayList<>();
for (TreeNode child : cur.children) {
TreeNode tmp = preorder(child, toRemove());
if (tmp == null) continue;
newChildren.add(tmp);
}
cur.children = newChildren;
return cur;
}

复制代码

salinghang17

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

salinghang17

最后一道题应该就是一个 Union Find 吧，请问一下给的是一维坐标还是二维坐标呀

kashimoto

请问最后一题 “Then, that router shuts down, and can no longer send or receive messages.” 这个条件有被用到吗，还是followup里面用到了的

fangzheng

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fangzheng

lllxin37 发表于 2021-5-20 19:10
第一题想法，输入是forest和set

[mw_shl_code=java,true]// forest contains root nodes on trees;

请问层主，这边为什么每次删完一个node要在set里同时删除哇，已加米！

lllxin37

fangzheng 发表于 2021-5-24 18:29
请问层主，这边为什么每次删完一个node要在set里同时删除哇，已加米！

没有啥特殊原因，就是顺手写的。唯一的好处就是如果set已经为空，就不用继续forest的遍历。当然这个判断条件我没写进codes...

多谢加米！

Lookielooky

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fangzheng

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式