12
返回列表 发新帖
楼主: 汐风悠远
跳转到指定楼层
上一主题 下一主题
收起左侧

空气床电面跪经

🔗
foryou 2019-5-30 14:48:03 | 只看该作者
全局:
汐风悠远 发表于 2019-5-30 14:24
list之间的顺序的确是不确定的,这一点我特意和面试官确认过。Earth的那个list并不一定是第一个,只是当 ...

所以 我假设所有点都在一个tree中.
root的问题 我可以直接扫描tree 找到indegree为0的那个节点, 就是root. 或者通过拓扑排序来找到root都可以.

hashmap两个bfs扫没写过 听起来不错, 从两个target开始向上扫就可以了.
回复

使用道具 举报

🔗
sifangyou1 2019-6-1 02:13:22 | 只看该作者
全局:
楼主这几个example没有跑出来么?
回复

使用道具 举报

🔗
sifangyou1 2019-6-1 02:14:22 | 只看该作者
全局:
楼主这几个example没有跑出来么?
建个key = children, value = parent 这样按照LCA很容易啊

“在此基础上,给出两个region, 让找出包含这两个region的最小region,例如:
["Quebec", "New York"] -> "North America"
["Canada", "South America"] -> "Earth"
["Canada", "Quebec"] -> "Canada" (这是LZ特地跟小哥clarify的例子,一开始未给出) ”
回复

使用道具 举报

🔗
ggsddu 2019-6-9 07:07:02 | 只看该作者
全局:
分数不够 看不到题 呜呜呜
回复

使用道具 举报

🔗
sam003 2019-6-9 08:53:06 | 只看该作者
全局:
谢谢分享。其实一个Map就可以了哈

public String findSmallestRegion(List<List<String>> regions, String A, String B) {

    if (regions == null || regions.size() == 0) {
      return null;
    }

    Map<String, String> parentRegions = new HashMap<>();

    for (List<String> regs : regions) {
      String parent = regs.get(0);
      for (int i = 1; i < regs.size(); i++) {
        parentRegions.put(regs.get(i), parent);
      }
    }

    List<String> aParents = new ArrayList<>();

    while (A != null) {
      aParents.add(A);
      A = parentRegions.get(A);
    }

    while (B != null) {
      if (aParents.contains(B)) {
        return B;
      }
      B = parentRegions.get(B);
    }

    return null;
  }

评分

参与人数 2大米 +3 收起 理由
miao29 + 1 很有用的信息!
QueenYoYo + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
sam003 2019-6-9 08:55:31 | 只看该作者
全局:
汐风悠远 发表于 2019-5-30 14:24
list之间的顺序的确是不确定的,这一点我特意和面试官确认过。Earth的那个list并不一定是第一个,只是当 ...

其实list的顺序不重要,你建map<SubRegion, ParentRegion>时,其实关系就明白了, 毕竟一个region最多一个Parent。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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