3

我正在从 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))
4

2 回答 2

2

您正在将字符添加到错误的列表中：您想要追加到 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)（所以你几乎应该总是尝试用 prepend（即 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) 
}
于 2013-08-17T11:14:03.743 回答
1

当您发现字符重复时，您将附加到错误的列表中。我摆弄的结果：

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))
于 2013-08-17T11:38:24.410 回答