一亩三分地论坛

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

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

请教pocket gems高频题ternary expression to bt的recursion写法

[复制链接] |试试Instant~ |关注本帖
yuxrose 发表于 2015-4-19 06:50:37 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
这题好几个人报过面经, 请戳这个
http://www.1point3acres.com/bbs/ ... mp;highlight=pocket
和这里
http://www.1point3acres.com/bbs/ ... t=pocket&page=1

我写了个用stack的,但我觉得用recursion更intuitive一点,但怎么写也写不对,因为需要一个integer track现在在string的哪个位置了,但java的int是pass by value, 所以总是track不对,有小伙伴愿意交流一下这个题的写法吗?
放上我这个错的写法
public static Node recursive(String s){
        int current = 0;
        return helper(s, current);
    }. From 1point 3acres bbs
   
    public static Node helper(String s, int current){
        if(current >= s.length()){
            return null;
        }
. 1point3acres.com/bbs        Node node = new Node(s.charAt(current));
        current = current + 2;
        if(s.charAt(current - 1) == '?'){.1point3acres缃
            node.left = helper(s, current);
        }
        current = current + 2;
        if(s.charAt(current - 1) == ':'){
            node.right = helper(s, current);
        }
        return node;
    }

还请大家指教!

ryuichist 发表于 2015-4-19 07:15:51 | 显示全部楼层
昨天才面了他们的1面,可以加个好友一起讨论下,扣扣10805529
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 07:23:52 | 显示全部楼层
ryuichist 发表于 2015-4-19 07:15
昨天才面了他们的1面,可以加个好友一起讨论下,扣扣10805529

不用QQ啊。。。有微信吗?

补充内容 (2015-4-19 07:26):
想起来你是那个面过L的大牛。。。天。。。赶快去加微信。这题有啥想法吗?
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-19 07:33:02 | 显示全部楼层
yuxrose 发表于 2015-4-19 07:23
不用QQ啊。。。有微信吗?
. From 1point 3acres bbs
补充内容 (2015-4-19 07:26):

哈哈好像是加过微信,YUXROSE,你微信名字是什么,忘记啦
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-4-19 08:19:30 | 显示全部楼层
这个是我当时的答案。很顺利的写出来了,但是不知道为什么还是挂了。面试官说有O(N)的解法
        public charNode parseTenary(String s){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return parseHelp(s,0,s.length()-1);
        }. 鍥磋鎴戜滑@1point 3 acres
        public charNode parseHelp(String s,int i,int j){
                if(i==j)
                        return new charNode(s.charAt(i));
                charNode root=new charNode(s.charAt(i));
                LinkedList<Integer> stack=new LinkedList<Integer>();
                int move=i;
                int mark=0;
                while(move<=j){
                        if(s.charAt(move)=='?')
                                stack.push(move);
                        else if(s.charAt(move)==':'){. 鍥磋鎴戜滑@1point 3 acres
                                mark=stack.pop();
                                if(stack.isEmpty()){
                                        break;-google 1point3acres
                                }
                        }. more info on 1point3acres.com
                        move++;       
                }
                root.left=parseHelp(s,mark+1,move-1);
                root.right=parseHelp(s,move+1,j);
                return root;
        }
祝你好运!!!
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-4-19 08:38:09 | 显示全部楼层
问了 招满了。。。无耻
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 08:46:29 | 显示全部楼层
yabay91 发表于 2015-4-19 08:19
这个是我当时的答案。很顺利的写出来了,但是不知道为什么还是挂了。面试官说有O(N)的解法
        public charNo ...

非常感谢!!也祝你早日拿到大offer!
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 08:57:40 | 显示全部楼层
nathanwong 发表于 2015-4-19 08:38
问了 招满了。。。无耻

全职也招满了是吗?那为啥不告诉我们。。还面个嘛劲儿啊。。。我们面试也有很多时间成本的。。。还得请假。
回复 支持 反对

使用道具 举报

chm34 发表于 2015-4-19 09:39:29 | 显示全部楼层
我用递归写的,time complexity O(nlogn), space O(1). 时间复杂度高是因为要查找String的分割点,这个每次都要O(N),不知道有么有什么优化?
  1. public static TreeNode solve(String s)
  2.         { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.                 if(s==null || s.length()==0) return null;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.                 if(s.length()==1)
  5.                         return new TreeNode(s.charAt(0));. more info on 1point3acres.com
  6.                 int flag=0; int mid=0;
  7.                 for(int i=2;i<=s.length()-1;i++)
  8.                 {
  9.                         if(s.charAt(i)=='?')
  10.                                 flag++;
  11.                         else if(s.charAt(i)==':')
  12.                         {
  13.                                 if(flag==0)
  14.                                 {
  15.                                         mid=i; break;
  16.                                 }
  17.                                 else flag--;
  18.                         }
  19.                 }
  20.                 TreeNode head=new TreeNode(s.charAt(0));
  21.                 TreeNode temp_left=solve(s.substring(2,mid));. 鍥磋鎴戜滑@1point 3 acres
  22.                 TreeNode temp_right=solve(s.substring(mid+1,s.length()));
  23.                 head.left=temp_left;
  24.                 head.right=temp_right;
  25.                 return head;
  26.         }
复制代码
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-19 11:20:01 | 显示全部楼层
这个题和serialize tree  差不多吧,pre oder build tree 就好了吧,因为一定是full tree, 所以只要注意代表这个字母有两个孩子,:代表没孩子就好了吧。自己想的,不知道对不对。

补充内容 (2015-4-19 11:21):
注意?代表这个字母有两个孩子,:代表没孩子
回复 支持 反对

使用道具 举报

wm_thu 发表于 2015-4-21 03:03:15 | 显示全部楼层
O(n)的思路是:
首先遍历一遍整个字符串,借助stack找出所有的?:匹配,存到一个hashmap里,key是?的index,value是:的index。这一趟是O(n)的。
然后再遍历一遍,建树。这时要递归,不过每个字符都只访问过一次,所以总的时间也是O(n)。
因此总时间O(n)。

补充内容 (2015-4-21 03:04):
由于用了hashmap,所以空间也是O(n)
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-4-22 14:39:55 | 显示全部楼层
yuxrose 发表于 2015-4-19 08:57
全职也招满了是吗?那为啥不告诉我们。。还面个嘛劲儿啊。。。我们面试也有很多时间成本的。。。还得请假 ...

我觉得一就是宣传公司 而是培训面试官,你看看之前有的人post的面经 无理由悲剧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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