3

一部が複数回繰り返される要素のリストが与えられた場合、タプルを含む新しいリストを作成する必要があります。各タプルには、要素が1行で繰り返される回数と要素自体が含まれます。

たとえば、与えられた

println(func(List()))              // should be empty list
println(func(List(1, 1)))          // (2,1) <- 1 is repeated 2 times
println(func(List(1, 1, 2, 1)))    // (2,1)(1,2)(1,1)

これは、現時点での私の最善の試みです。私は非常に基本的なものが欠けていると感じています、私が何を理解するのを手伝ってください

  def func[X](xs: List[X]): List[(Int, X)] = xs match {
    case Nil => Nil
    case y :: ys   => ys match {
      case Nil     => (1, y) :: Nil
      case z :: zs => if (y != z) (ys.prefixLength(_ == ys.head), y) :: func(ys) 
                      else func(ys)
    }
  }

問題が何であるかを分析した後、私が再帰的に呼び出す時点では、要素の数を把握するのに十分な情報がないように思われfunc(ys)ますys。を扱っているとしましょうList(1,1,1,2)。わかりました、そうです、 yです1、zです1、そして(1::(2::Nil))ですzs。上記の私の論理に従うと、1が2回見られたという事実は、次の呼び出しで失われます。

問題は、私が問題について正しい方法で考えていないことかもしれません。私が念頭に置いているのは、「この要素が前の要素と同じではないことがわかるまでリストに沿って進み、その時点で、要素の出現回数を数えてタプルにする」ということです。

上記のシナリオ（私のコード）では、問題は、数字が実際に同じである場合（1,1）、すでに数字を見たという事実がどこにも反映されていないことを認識しています。しかし、タプルを作成する準備がまだできていないので、どこでこれを行うことができますか？

この質問に答える際には、ケースの構造に固執してください。この問題に対処するための他のより良い、よりクリーンな方法があるかもしれないことを私は理解しています、私はここで私が間違っていることをよりよく理解したいと思います

4

4 に答える 4

8

あなたは正しい方向に進んでいます。問題は、ここで結果リストを段階的に作成することはできないということです。再帰呼び出しから取得したリストから先頭を削除し、新しいペアを追加する必要があるか、最後のペアのカウントを増やす必要があるかを確認する必要があります。 1：

def func[X](xs: List[X]): List[(Int, X)] = xs match {
  case Nil => Nil
  case y :: ys => func(ys) match {
    case (c, `y`) :: rest => (c + 1, y) :: rest
    case             rest => (    1, y) :: rest
  }
}

ネストされた一致パターンのバッククォートに注意してください。yこれは、という名前の新しい変数を定義することを避けるために必要yです。

于 2013-01-27T20:07:09.850 に答える
2

以下を使用したより簡単な解決策は次のspanとおりです。

def runLength[T](xs: List[T]): List[(Int, T)] = xs match {
  case Nil => List()
  case x :: l => {
    val (front, back) = l.span(_ == x)
    (front.length + 1, x) :: runLength(back)
  }
}
于 2015-03-14T00:08:36.527 に答える
1

それは確かにランレングスエンコーディングです。

これは簡単ですが、一般的ですが、試みます...

package rrs.scribble

object RLE {
  def rle[T](tSeq: List[T]): List[(Int, T)] = {
    def doRLE(seqT: List[T], rle: List[(Int, T)]): List[(Int, T)] =
      seqT match {
        case t :: moreT if t == rle.head._2 => doRLE(moreT, (rle.head._1 + 1, t) :: rle.tail)
        case t :: moreT => doRLE(moreT, (1, t) :: rle)
        case Nil => rle
      }

    if (tSeq.isEmpty)
      List.empty[(Int, T)]
    else
      doRLE(tSeq, List((0, tSeq.head))).reverse
  }
}

REPLでは：

scala> import rrs.scribble.RLE._
import rrs.scribble.RLE._

scala> rle(List(1, 1, 2, 1))
res0: List[(Int, Int)] = List((2,1), (1,2), (1,1))
于 2013-01-27T20:24:19.393 に答える
-1

これはランレングスエンコーディングと呼ばれます。99のScala問題の問題10をチェックしてください（解決策については問題番号をクリックしてください）。

于 2013-01-27T19:33:00.063 に答える