GG 电面 19 summer intern

EbyccoCheng 发表于 2018-11-3 07:53
第二个是用个二叉树做么

嗯嗯是的

三亩三分地 发表于 2018-11-3 12:27
请问楼主两轮背靠背每轮只做了一道题吗？

嗯每轮只做了一道题

楼主第二题怎么建树的？是类似于Trie的结构吗？
我的想法是先排序，这样把首位为0和1的分为两组，那么要找公共前缀长度为0的最大距离只需要找出每组里最长的字符串即可，然后在每一组里考虑公共前缀长为1的最大距离

LaSeineFirenze 发表于 2018-11-4 05:57
楼主第二题怎么建树的？是类似于Trie的结构吗？
我的想法是先排序，这样把首位为0和1的分为两组，那么要找 ...

我是从root往下，0在左边， 1在右边
001就是
    0
   /
0
  \
    1

找最大距离的时候 就从root开始做dp
如果当前node左右child长度和为最大 更新最大距离
否则返回最长的child的长度

楼主，没太明白你第二题的意思，是分别以0和1做为root建两个二叉树吗

gly612 发表于 2018-11-6 13:04
楼主，没太明白你第二题的意思，是分别以0和1做为root建两个二叉树吗

抱歉上面说的不太清楚 是从root下面开始分
如果树里有 001, 110, 111 则树如下：
     root
      / \
    0    1
   /        \
0           1
   \        /   \
    1     0     1