时间戳

首页 > 解决方案 > 获取任何节点的顶级父节点

algorithm - 获取任何节点的顶级父节点

问题描述

鉴于问题末尾的格式，获取给定项目的顶级名称的最佳方法是什么？顶级名称是 parentId = 1 的名称。

def getTopLevel(name: String): String = {
    // Environment(150) -> Environment(150) - since its parentId is 1
    // Assassination -> Security - since Assassination(12) -> Terrorism(10) -> Security(2)
}

这是我目前的方法，但有更好的方法吗？

未映射=类别.大小

循环遍历此列表，直到仍有未映射的项目。
- 为顶层构建一个 Map(Int, String)。
- 构建一个 Map(Int, Int) - 将一个 id 映射到顶级 id。
- 跟踪未映射的项目

一旦循环退出，我可以使用两个地图来完成工作。

[
    {
        "name": "Destination Overview",
        "id": 1,
        "parentId": null
    },
    {
        "name": "Environment",
        "id": 150,
        "parentId": 1
    },
    {
        "name": "Security",
        "id": 2,
        "parentId": 1
    },
    {
        "name": "Armed Conflict",
        "id": 10223,
        "parentId": 2
    },
    {
        "name": "Civil Unrest",
        "id": 21,
        "parentId": 2
    },
    {
        "name": "Terrorism",
        "id": 10,
        "parentId": 2
    },
    {
        "name": "Assassination",
        "id": 12,
        "parentId": 10
    }
]

标签： algorithmscaladata-structurestree

解决方案

这实际上是两个问题。

  1. 将 Json 解析为 Scala 集合和
  2. 使用该集合将项目追溯到最高父级

对于第一个问题，您可以使用play-json。第二部分可以用尾递归函数处理。这是解决这两个问题的完整程序：

import play.api.libs.json.{Json, Reads}

case class Node(name: String, id: Int, parentId: Option[Int])
object JsonParentFinder {
  def main(args: Array[String]): Unit = {
    val s =
      """
        |[
        |    {
        |        "name": "Destination Overview",
        |        "id": 1,
        |        "parentId": null
        |    },
        |    {
        |        "name": "Environment",
        |        "id": 150,
        |        "parentId": 1
        |    },
        // rest of the json
        |]
        |""".stripMargin

    implicit val NodeReads : Reads[Node] =Json.reads[Node]
    val r = Json.parse(s).as[Seq[Node]]
      .map(x => x.id -> x).toMap

    println(getTopLevelNode(150, r))
    println(getTopLevelNode(12, r))
  }

  def getTopLevelNode(itemId : Int, nodes: Map[Int, Node], path : List[Node] = List.empty[Node]) : List[Node] = {
    if(nodes(itemId).id == 1)
      nodes(itemId) +: path  
    else
      getTopLevelNode(nodes(nodes(itemId).parentId.get).id, nodes, nodes(itemId) +: path)
  }
}

输出将是：

List(Node(Destination Overview,1,None), Node(Environment,150,Some(1)))
List(Node(Destination Overview,1,None), Node(Security,2,Some(1)), Node(Terrorism,10,Some(2)), Node(Assassination,12,Some(10)))

几点注意事项：

  • 我还没有实现全面的错误处理逻辑。隐含的假设是唯一的项目parentId==None是根节点。nodes(itemId).parentId.get可能导致失败。
  • 此外，在创建地图时，假设所有项目都有唯一的 ID。
  • 另一个假设是所有节点最终都有到根节点的路径。如果不是这种情况，这将失败。但是通过添加更多停止条件来解决这些情况应该很简单。
  • 我将项目添加到累加器列表（path此处命名），因为 Scala 列表上的前置操作需要固定时间。您可以只reverse使用结果列表或使用其他数据结构Vector来有效地构建路径。

推荐阅读