斯卡拉P08 - 包

Question

我正在從P08的99包裝問題問題，我認爲我這樣做是正確的，但是我認爲我不知道斯卡拉的語法有什麼問題..

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（您目前正在使用的列表），而不是一個。頭（包含您找到的第一個相等字符的列表）。

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) 
} 

Answer 2

如果您發現該字符在重複你追加到一個錯誤的列表。我擺弄周圍的結果是：

object P08SO extends App { 
    // this method packs by adding to the beginning of the result and at the end it uses reverse 
    def pack1[A](inputList: List[A]): List[List[A]] = { 
    @tailrec 
    def checkNext(result: List[List[A]], prev: A, input: List[A]): List[List[A]] = 
     if (input.isEmpty) result 
     else 
     checkNext(
      if (input.head == prev) (input.head :: result.head) :: result.tail 
      else List(input.head) :: result, 
      input.head, input.tail) 

    if (inputList.isEmpty) Nil 
    else checkNext(List(List(inputList.head)), inputList.head, inputList.tail).reverse 
    } 

    // packs directly in right order 
    // but IMO there's a quite significant performance cost (last and init have to iterate through entire list) 
    def pack2[A](inputList: List[A]): List[List[A]] = { 
    @tailrec 
    def checkNext(result: List[List[A]], prev: A, input: List[A]): List[List[A]] = 
     if (input.isEmpty) result 
     else 
     checkNext(
      if (input.head == prev) result.init ::: List(input.head :: result.last) 
      else result ::: List(List(input.head)), 
      input.head, input.tail) 

    if (inputList.isEmpty) Nil 
    else checkNext(List(List(inputList.head)), inputList.head, inputList.tail) 
    } 

    List[(String, List[Any])](
    "empty" -> List(), 
    "one string" -> List("str"), 
    "ints" -> List(0, 0, 0, 1, 1, 2, 3, 4, 4, 4, 4, 5, 6), 
    "chars" -> "abbbcdeeffff".toList 
).foreach(
    testVal => { 
     println(s"pack1 - ${testVal._1}: ${pack1(testVal._2)}") 
     println(s"pack2 - ${testVal._1}: ${pack2(testVal._2)}") 
    } 
) 
} 

輸出：

pack1 - empty: List() 
pack2 - empty: List() 
pack1 - one string: List(List(str)) 
pack2 - one string: List(List(str)) 
pack1 - ints: List(List(0, 0, 0), List(1, 1), List(2), List(3), List(4, 4, 4, 4), List(5), List(6)) 
pack2 - ints: List(List(0, 0, 0), List(1, 1), List(2), List(3), List(4, 4, 4, 4), List(5), List(6)) 
pack1 - chars: List(List(a), List(b, b, b), List(c), List(d), List(e, e), List(f, f, f, f)) 
pack2 - chars: List(List(a), List(b, b, b), List(c), List(d), List(e, e), List(f, f, f, f))