斯卡拉 - 检查如果对象存在列表内

我的情况下，类如下：

这是个好办法：

case class Person(id:Int, name:String, friends:List[Person] = Nil)

我已经使用这个代码写的？使用尾递归并在尾列表上追加另一个列表？如果不是，最好的办法是什么？

来源

2016-11-08 placplacboom

想想当你有朋友的朋友时会发生什么：'eve - > [john，anne]，anne - > [peter，lois]，peter - > [eve，bob，russ]' – maasg

它会循环整个列表。我可以在第一个朋友找到一个朋友之后停下来。如果我正在寻找“彼得”，我可以在安妮名单上找到他之后停下来 – placplacboom

由于没有确保你确实拥有一棵树（而不是带有周期的图），所以你应该从附加列表中删除重复项。一旦你完成了这个工作，你的算法只是在你的树上实现一个宽度优先的搜索，你不会做得更好。 –

我结束了下面的实现基本上尾递归BFS：

@tailrec 
def find(id: Int, level: List[Person], visited: Set[Person] = Set.empty): Option[Person] = 
    if (level.isEmpty) None 
    else { 
    // Try to find person on this level 
    val found = level.find(_.id == id).filterNot(visited.contains) 
    if (found.isDefined) found 
    else find(
     id, 
     // Next level construction 
     level.flatMap(_.friends).distinct, 
     // Keep track of visited to handle cycles 
     visited ++ level 
    ) 
    }

UPDATE：另外，我建议你通过名添加通话，才能玩弄更多的测试用例：

class Person(val id: Int, val name: String, friends: => List[Person]) { 

    def friendList = friends 

    override def toString = name 
} 

object Person { 

    def apply(id: Int, name: String, friends: => List[Person] = Nil) = new Person(id, name, friends) 
}

在这种情况下，你可以从注释组成例如：

val john = Person(1, "john") 
val russ = Person(2, "russ") 
val bob = Person(3, "bob") 
val lois = Person(5, "lois") 

lazy val `eve friends` = List(john, anne) 
lazy val `peter friends` = List(eve, bob, russ) 
lazy val `anne friends` = List(peter, lois) 

val eve = Person(7, "eve", `eve friends`) 
val peter = Person(8, "peter", `peter friends`) 
val anne: Person = Person(6, "anne", `anne friends`) 

println(find(8, List(eve, peter, lois))) // result: Some(peter)

来源

2016-11-08 15:35:06 tkachuko

斯卡拉 - 检查如果对象存在列表内

回答

相关问题