空气床电面跪经

汐风悠远 发表于 2019-5-30 14:24
list之间的顺序的确是不确定的，这一点我特意和面试官确认过。Earth的那个list并不一定是第一个，只是当 ...

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

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

楼主这几个example没有跑出来么？

楼主这几个example没有跑出来么？
建个key = children, value = parent 这样按照LCA很容易啊

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

分数不够 看不到题 呜呜呜

谢谢分享。其实一个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;
  }

汐风悠远 发表于 2019-5-30 14:24
list之间的顺序的确是不确定的，这一点我特意和面试官确认过。Earth的那个list并不一定是第一个，只是当 ...

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