Рубрики

Определите все узлы «прародитель» каждого узла на карте

Приведенные во входных данных, которые имеют отношения между человеком и их детьми, для всех людей в этих данных, идентифицировать бабушку и дедушку всех людей во входных данных.

Input: A map of all the people and their children
Map[String, Set[String]]

Output: A map of all people and their grandparents
Map[String, Set[String]]

Example:
Input 
Map(A -> Set(B,C), B -> Set(D, C), C -> Set(E))

Output:
Map(D -> Set(A), C -> Set(A), E -> Set(A, B)) 

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.

Здесь мы перебираем каждый узел в Map и выясняем прародителя каждого дочернего элемента.

Идея состоит в том, чтобы использовать рекурсию. Но это может быть решено и без рекурсии.

Давайте сначала посмотрим на решение Без рекурсии:

Решение 1 (без рекурсии):

Здесь мы должны использовать Mutable Scala Map. Ниже приведен код Scala.

val input = Map("A" -> Set("B","C"), "B" -> Set("D", "C"), "C" -> Set("E"))
val output: scala.collection.mutable.Map[String, Set[String]]
  = scala.collection.mutable.Map()

  input.map(node => node._2.map(child =>
    input.get(child).map(grandchildren =>
      grandchildren.map{grandchild =>
        if(output.keys.exists(_ == grandchild)) {
          output.put(grandchild, output.get(grandchild).get ++ Set(node._1))
        } else {
          output.put(grandchild, Set(node._1))
        }
      }
    )
  ))

Здесь мы перебираем каждый узел карты и выясняем внуков каждого ребенка в узле. Это поможет нам в создании карты с отношениями дедушка и дедушка.

Решение 2 (с рекурсией):

Здесь мы можем использовать Неизменяемую Карту Scala, так как мы используем Рекурсию.

val input = Map("A" -> Set("B","C"), "B" -> Set("D", "C"), "C" -> Set("E"))
val output = findGrandparents(input)

  def findGrandparents(family: Map[String, Set[String]]): Map[String, Set[String]] = {
    family.foldLeft(Map[String, Set[String]]()){
      case (grandParents, oneFamily) => {
        val grandChildren: Set[String] = oneFamily._2.flatMap(member => family.get(member)).flatten
        val res =  grandChildren.map(child => {
          grandParents.get(child) match {
            case None =>(child -> Set(oneFamily._1))
            case Some(x) => (child -> (x + oneFamily._1))
          }
        }).toMap
        grandParents ++ res
      }

Эта статья предоставлена Химаншу Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Определите все узлы «прародитель» каждого узла на карте

0.00 (0%) 0 votes