当前在线人数12303
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
贴个简单的面经
[版面:待字闺中][首篇作者:canoee] , 2015年09月05日13:34:00 ,1847次阅读,8次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
canoee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: canoee (熊猫), 信区: JobHunting
标  题: 贴个简单的面经
发信站: BBS 未名空间站 (Sat Sep  5 13:34:00 2015, 美东)

第一轮一小时面试,白板题:
Binary Tree 里有重复的值,只会出现当前点的右侧,怎么删掉

有几个解法:
1. O(nlgn) time, O(1) space,从每个点开始遍历右边,删掉重复点
2. O(n) time, O(n) space,建map
3. O(n) time, O(1) space,Morris Traversal

最好的解法自然是3,但还是紧张,第一反应是解法1
写完聊天的时候说有一个解法是线性时间,常量空间的时候突然想起来,感觉自己略蠢
--
┼ 我们的爱情像你路过的风景        ┼─┐你说爱像云要自在飘浮才美丽        
┼┐ 一直在进行脚步却从来不会为我而停┌┼─ 我终於相信分手的理由有时候很动听
─┼────      ──────┬   ┳                      ┬─┬─┼┬─  
  │ 给你的爱一直很安静       └┼  明明是三个人的电影     │      │  │  
  │     来交换你偶尔给的关心 ┏┼┐     我却始终不能有姓名      │┼─┘  
      ┶━━━          ━━━┻  ┼       ───────────┼┘      

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 71.]

 
ThinkU
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: ThinkU (每天想你多一丝), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sat Sep  5 13:46:44 2015, 美东)

morris只是省掉了stack, 你还是需要map
Binary Tree 里有重复的值,只会出现当前点的右侧 是指两个重复的值,一个在另一
个的右子树上吗?还是指重复的值,一个必然是另一个的右子节点?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
sxh53
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: sxh53 (三两七), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sun Sep  6 10:17:32 2015, 美东)

听描述像是右子树。


【 在 ThinkU (每天想你多一丝) 的大作中提到: 】
: morris只是省掉了stack, 你还是需要map
: Binary Tree 里有重复的值,只会出现当前点的右侧 是指两个重复的值,一个在另一
: 个的右子树上吗?还是指重复的值,一个必然是另一个的右子节点?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
canoee
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: canoee (熊猫), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sun Sep  6 12:11:38 2015, 美东)

可以有无数个duplicate,但是都只会出现在右边,对于左边是严格大于的

【 在 ThinkU (每天想你多一丝) 的大作中提到: 】
: morris只是省掉了stack, 你还是需要map
: Binary Tree 里有重复的值,只会出现当前点的右侧 是指两个重复的值,一个在另一
: 个的右子树上吗?还是指重复的值,一个必然是另一个的右子节点?



--
┼ 我们的爱情像你路过的风景        ┼─┐你说爱像云要自在飘浮才美丽        
┼┐ 一直在进行脚步却从来不会为我而停┌┼─ 我终於相信分手的理由有时候很动听
─┼────      ──────┬   ┳                      ┬─┬─┼┬─  
  │ 给你的爱一直很安静       └┼  明明是三个人的电影     │      │  │  
  │     来交换你偶尔给的关心 ┏┼┐     我却始终不能有姓名      │┼─┘  
      ┶━━━          ━━━┻  ┼       ───────────┼┘      

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
ThinkU
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: ThinkU (每天想你多一丝), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sun Sep  6 13:13:31 2015, 美东)

删除节点你怎么做到O(1)?
【 在 canoee (熊猫) 的大作中提到: 】
: 可以有无数个duplicate,但是都只会出现在右边,对于左边是严格大于的



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
lalala123321
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: lalala123321 (), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Mon Sep  7 12:00:01 2015, 美东)

请问这个binary tree是类似于BST吗?就是说是不是左子树的值都小于root的值,有字
数的值都大于等于root的值,如果是的话就比较简
public void deleteDuplicate(TreeNode root){
        if(root == null){
            return;
        }
        deleteDuplicate(root.left);
        while(root.right != null && root.right.val == root.val){
            root.right = root.right.right;
        }
        deleteDuplicate(root.right);
    }
求指正
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
vvNN
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: vvNN (vvNN), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sun Sep 13 01:37:10 2015, 美东)

如果balanced的话,time logn, space logn,

同意否?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
icefish
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: icefish (哆拉A梦), 信区: JobHunting
标  题: Re: 贴个简单的面经
发信站: BBS 未名空间站 (Sun Sep 13 02:49:44 2015, 美东)

看着挺讨巧的,坐等解答


【 在 lalala123321 () 的大作中提到: 】
: 请问这个binary tree是类似于BST吗?就是说是不是左子树的值都小于root的值,有字
: 数的值都大于等于root的值,如果是的话就比较简
: public void deleteDuplicate(TreeNode root){
:         if(root == null){
:             return;
:         }
:         deleteDuplicate(root.left);
:         while(root.right != null && root.right.val == root.val){
:             root.right = root.right.right;
:         }
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996