一亩三分地论坛

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

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

狗狗电面 面经

[复制链接] |试试Instant~ |关注本帖
stonetao 发表于 2016-7-23 03:05:42 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
. more info on 1point3acres.com
1.leetcode 26 https://leetcode.com/problems/re ... -from-sorted-array/
2. 删除树中一些node,然后求剩下所有的tree的root
Badger96 发表于 2016-7-23 14:36:02 | 显示全部楼层
试做一下第二题,假定要删除的节点数值在int[] vals里,有错误的话欢迎交流:

public ArrayList<TreeNode> removeNodes(TreeNode root, int[] vals) {
    ArrayList<TreeNode> res = new ArrayList<>();
    if (vals == null || vals.length == 0) {
        res.add(root);
        return res;
    }
    HashSet<Ingeter> hash = new HashSet<>();
    for (int i = 0; i < vals.length; i++) {
        hash.add(vals[i]);. 1point3acres.com/bbs
    }
    root = helper(res, hash, root);
    if (root != null) {. visit 1point3acres.com for more.
        res.add(root); //小corner case,当最后的root没被删除时,要把它也放结果
    }
    return res;. 鍥磋鎴戜滑@1point 3 acres
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public TreeNode helper(ArrayList<TreeNode> res, HashSet<Integer> hash, TreeNode root) {
    if (root == null) {
        return root;. more info on 1point3acres.com
    }
    root.left = helper(res, hash, root.left);
    root.right = helper(res, hash, root.right);
    if (hash.contains(root.val)) { //当root是要被删除的节点时. 1point3acres.com/bbs
        if (root.left != null) {
            res.add(root.left); //非空左子树进结果
        }
        if (root.right != null) {
            res.add(root.right); //非空右子树进结果
        }
        return null; //这样就把root节点删除了,并已把它非空左右子树存进了结果
    }
    return root;
}

. 鍥磋鎴戜滑@1point 3 acres
回复 支持 1 反对 0

使用道具 举报

youto 发表于 2016-7-23 04:00:04 | 显示全部楼层
第二题能举个例子说明一下吗?如何删,是有什么要求吗?
回复 支持 反对

使用道具 举报

 楼主| stonetao 发表于 2016-7-23 05:31:26 | 显示全部楼层
youto 发表于 2016-7-23 04:00. visit 1point3acres.com for more.
第二题能举个例子说明一下吗?如何删,是有什么要求吗?

        1
    /       \
   2        3
/     \    /   \. Waral 鍗氬鏈夋洿澶氭枃绔,
4     5   6    7


删除 2 and 6     会得到 3 个 tree  4, 5 and 1-3-7 返回[4,5,1] 太不好画tree 结构了 见谅
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-23 07:12:09 | 显示全部楼层
楼主上来就做题吗?
回复 支持 反对

使用道具 举报

 楼主| stonetao 发表于 2016-7-23 07:32:09 | 显示全部楼层
mkcing 发表于 2016-7-23 07:12
楼主上来就做题吗?

是的,什么也没说就做题了。
回复 支持 反对

使用道具 举报

dhldxy 发表于 2016-7-23 08:14:27 | 显示全部楼层
第二题能再讲一下吗?就deleteNode.left, deleteNode.right?
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-23 13:03:11 | 显示全部楼层
第二题没想到好的方法 LZ能分享一下丝路吗? thanks
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-23 13:42:18 | 显示全部楼层
刚想到o(n) 依次搜寻的方法 写完晚点贴上来
回复 支持 反对

使用道具 举报

 楼主| stonetao 发表于 2016-7-24 04:09:15 | 显示全部楼层
Badger96 发表于 2016-7-23 14:36.1point3acres缃
试做一下第二题,假定要删除的节点数值在int[] vals里,有错误的话欢迎交流:

. 1point 3acres 璁哄潧public ArrayList removeN ...

和我写得差不多,就是这个意思。
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-23 11:54:10 | 显示全部楼层
维护一个hashset,存放新产生的root,如果后续发现要删除的node在hashset中,就从hashset里remove这个node,替换为node的child 大概这样么
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-9-27 03:17:55 | 显示全部楼层
个人认为也可以修改node的结构,保存一个deleted 的 boolean 变量,在完成删除操作以后用dfs 如果 访问到deleted = true的node那么它的左右child均会成为新的root, 前提 left != null right != null. 用一个list储存所有这样的新root. 如果真的要删除的话在dfs过程中存完新root后把该节点设为null就行了。。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-10-3 09:20:27 | 显示全部楼层
第二题。。关键在哪里 是我没把握住吗?
难道不是后序遍历,遇到就删,把左右节点放到结果力去,用返回值用来重置父节点的左右节点
就是2楼写的那样。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 21:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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