Scala，P08 - 包

Question

我正在做 99 个问题中 P08 的打包问题，我认为我做对了，但是我认为我不知道 Scala 的语法有问题..

def pack(list: List[Char]): List[List[Char]] = {
  @tailrec 
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char] ): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev==l.head) List(a.head:::List(l.head)) else a:::List(List(l.head))       
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List(list.head)), list.head, list.tail)
}

编辑:对不起大家，是的，它编译得很好，但它没有做它应该做的，而是合并了所有东西，我不明白为什么。它应该将附近的相等字母分组到 char 列表中，例如:

pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) =>

List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), 
     List('e, 'e, 'e, 'e))

Answer 1

您将字符添加到错误的列表中:您想要添加到 a.last(您当前正在处理的列表)，而不是 a.head(其中包含您找到的第一个相等字符的列表)。

def pack(list: List[Char]): List[List[Char]] = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char] ): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev==l.head) a.init:+(a.last:+l.head) // a.last contains the list you are currently adding to,
                                                           // a.init's list are all completed
                else a:+List(l.head) // start a new list of character
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List(list.head)), list.head, list.tail)
}

请注意，这段代码的性能很糟糕，因为追加是 O(n)(所以你几乎应该总是尝试用前置(O(1)) 替换它(至少在循环中))。

更好的方法是先反转输入列表，然后将元素添加到结果列表中:

def pack(list: List[Char]): List[List[Char]] = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char]): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev == l.head) ((l.head::a.head)::a.tail) else List(l.head)::a
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List[Char](list.last)), list.last, list.init.reverse) 
}

或更惯用的:

def pack(list: List[Char]) = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char]): List[List[Char]] = l match {
    case Nil => a
    case h::tail if h == prev => checkNext((h::a.head)::a.tail,h,tail)
    case h::tail => checkNext(List(h)::a,h,tail)
  }
  checkNext(List(List[Char](list.last)), list.last, list.init.reverse) 
}