一亩三分地论坛

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

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

[算法题] G家面经求指导

[复制链接] |试试Instant~ |关注本帖
一回头的温柔 发表于 2016-2-11 12:21:17 | 显示全部楼层 |阅读模式

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

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

x
给出一个迭代器,迭代器里存了很多个类R的实例, 类R里只有两个参数,都是String类型,分别代表Parent 和 Child,child只有一个Parent,Parent 可以有任意数量child
按所给示例输出所有的层级关系

eg:
A
  B1.1point3acres缃�
  B2
    C1
    C2
  B3
    D1
    D2
在面经里看到说用tree+哈希表,还是不太明白,有会写的仔细说一下思路吧。
stellari 发表于 2016-2-12 01:50:10 | 显示全部楼层
题目的要求其实就是”给定树中每一条边,打印这棵树”。

所谓“tree+哈希表”的意思是先在内存中用指针(或引用)的连接方式把这棵树表示出来。为此需要写一个类
class StringTreeNode {
  String str;
  StringTreeNode parent;
  ArrayList<StringTreeNode> children;
  ...
}
每遍历R中的一条边,就检查Parent和Child所代表的StringTreeNode是否都已经被创建过了,如果有任一者未创建的话则先创建之,然后把二者连接在一起。检查的方法则是通过查询一个HashMap<String, StringTreeNode>来完成,该HashMap中存放的是“目前为止已经遇到过的String”。

树建立好以后,从root开始DFS就能够打印出树的内容。对于有Parent节点的树来说,找root应该不难。

不过,这道题的题目并没有说所有的R一定只形成一棵树,所以有可能会存在多个root。这种情况要先跟面试官沟通清楚。
回复 支持 反对

使用道具 举报

dondon91 发表于 2016-4-1 12:34:02 | 显示全部楼层
stellari 发表于 2016-2-11 11:50
题目的要求其实就是”给定树中每一条边,打印这棵树”。

所谓“tree+哈希表”的意思是先在内存中用指针 ...

不用建立树的,虽然树比较直观,但是其实你只要HashMap<String, ArrayList<String>> 就可以表示出来树的关系了;
原因是: 这个跟treenode不太一样,每个node content就只有一个string变量,换句话说两个不同的treenode不能有相同的string;
所以给了任何一个node,用hashmap查一下就知道他的children都有啥了,不用tree里面的pointer (不好意思我主要用c++)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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