给定：aabcdddeabb => 预期：[(a,2),(b,1),(c,1),(d,3),(e,1),(a,1),(b,1)]在斯卡拉

Question

我对如何实现这个算法非常感兴趣。如果可能的话，很高兴看到有和没有递归的实现。我是该语言的新手，因此非常感谢您的帮助。我所能想出的就是这段代码，它没有进一步：

print(counterOccur("aabcdddeabb"))

def counterOccur(string: String) =
string.toCharArray.toList.map(char => {
  if (!char.charValue().equals(char.charValue() + 1)) (char, counter)
  else (char, counter + 1)
})

我意识到它甚至离真相还很远，我什至不知道还有什么可以用。

Answer 1

为了

str = "aabcdddeabb"

您可以提取正则表达式的匹配项

rgx = /(.)*/

获取数组

["aa", "b", "c", "ddd", "e", "a", "bb"]

然后将数组的每个元素映射到所需的字符串。¹

def counterOccur(str: String): List[(Char, Int)] = {
  """(.)*""".r
    .findAllIn(str)
    .map(m => (m.charAt(0), m.length)).toList
}

counterOccur("aabcdddeabb")
  #=> res0: List[(Char, Int)] = List((a,2), (b,1), (c,1), (d,3), (e,1), (a,1), (b,2))

正则表达式为，“匹配任意字符并将其保存到捕获组 1 ((.))，然后匹配捕获组 1 的内容零次或多次 (*)。

^{1. Scala代码由@Thefourthbird友情提供。}

Answer 2

第一个使用递归的解决方案。我从字符串中获取 Char by Char 并检查 Vector 中的最后一个元素是否与当前元素相同.如果元素相同，我会通过增加计数来更新最后一个元素（这是第一种情况）。如果最后一个元素不相同，我只需将新元素添加到 Vector（第二种情况）。当我从字符串中取出所有 Chars 时，我只是 return 结果。

  def counterOccur(string: String): Vector[(Char, Int)] = {
    @tailrec
    def loop(str: List[Char], result: Vector[(Char, Int)]): Vector[(Char, Int)] = {
      str match {
        case x :: xs if result.lastOption.exists(_._1.equals(x)) =>
          val count = result(result.size - 1)._2
          loop(xs, result.updated(result.size - 1, (x, count + 1)))
        case x :: xs =>
          loop(xs, result :+ (x, 1))
        case Nil => result
      }
    }

    loop(string.toList, Vector.empty[(Char, Int)])
  }

  println(counterOccur("aabcdddeabb"))

不使用递归的第二种解决方案。它的工作原理相同，但它使用的是 foldLeft 而不是递归。

  def counterOccur2(string: String): Vector[(Char, Int)] = {
    string.foldLeft(Vector.empty[(Char, Int)])((r, v) => {
      val lastElementIndex = r.size - 1
      if (r.lastOption.exists(lv => lv._1.equals(v))) {
        r.updated(lastElementIndex, (v, r(lastElementIndex)._2 + 1))
      } else {
        r :+ (v, 1)
      }
    })
  }

  println(counterOccur2("aabcdddeabb"))

Answer 3

这是一个使用 foldLeft 和自定义 State 案例的解决方案 class:

def countConsecutives[A](data: List[A]): List[(A, Int)] = {
  final case class State(currentElem: A, currentCount: Int, acc: List[(A, Int)]) {
    def result: List[(A, Int)] =
      ((currentElem -> currentCount) :: acc).reverse
    
    def nextState(newElem: A): State =
      if (newElem == currentElem)
        this.copy(currentCount = this.currentCount + 1)
      else
        State(
          currentElem = newElem,
          currentCount = 1,
          acc = (this.currentElem -> this.currentCount) :: this.acc
        )
  }
  object State {
    def initial(a: A): State =
      State(
        currentElem = a,
        currentCount = 1,
        acc = List.empty
      )
  }
  
  data match {
    case a :: tail =>
      tail.foldLeft(State.initial(a)) {
        case (state, newElem) =>
          state.nextState(newElem)
      }.result
    
    case Nil =>
      List.empty
  }
}

可以看到代码运行 here.

Answer 4

可以用很简单的foldLeft来积累。您也不需要 toCharArray 和 toList 因为字符串可以隐式转换为 Seq[Char]:

"aabcdddeabb".foldLeft(collection.mutable.ListBuffer[(Char,Int)]()){ (acc, elm) =>
   acc.lastOption match {
     case Some((c, i)) if c == elm => 
       acc.dropRightInPlace(1).addOne((elm, i+1))
     case _ => 
       acc.addOne((elm, 1))
   }
}

Answer 5

一种可能是使用unfold 方法。这个方法是为几种集合类型定义的，在这里我用它来生成一个 Iterator（记录在 here 版本 2.13.8）：

def spans[A](as: Seq[A]): Iterator[Seq[A]] =
  Iterator.unfold(as) {
    case head +: tail =>
      val (span, rest) = tail.span(_ == head)
      Some((head +: span, rest))
    case _ =>
      None
  }

unfold 从一个状态开始并应用一个函数 returns，或者：

None 如果我们想发出收集结束的信号
Some 包含我们要生成的集合的下一项和将提供给下一次迭代的“剩余”状态。

特别是在这个例子中，我们从一个名为 as 的 A 序列开始（它可以是一个字符序列）并且在每次迭代中：

如果至少有一项
- 我们分开头和尾
- 我们进一步将尾部拆分为最长的前缀，其中包含与头部和其余部分相等的项
- 我们return上面得到的头和前缀作为下一项
- 我们return集合的其余部分作为下一次迭代的状态
否则，我们 return None 因为没有什么可做的了

结果是一个相当灵活的函数，可用于将相同项目的跨度组合在一起。然后，您可以根据以下定义最初想要的功能：

def spanLengths[A](as: Seq[A]): Iterator[(A, Int)] =
  spans(as).map(a => a.head -> a.length)

这可能会变得更通用并提高其性能，但我希望这可以成为关于另一种可能方法的有用示例。虽然折叠集合是一种递归方法，但展开被称为 corecursive one (Wikipedia article).

您可以尝试使用此代码 here on Scastie。

给定：aabcdddeabb => 预期：[(a,2),(b,1),(c,1),(d,3),(e,1),(a,1),(b,1)]在斯卡拉

Given: aabcdddeabb => Expected: [(a,2),(b,1),(c,1),(d,3),(e,1),(a,1),(b,1)] in Scala

algorithm

scala