problem11-15

Mar 15, 2017 | 99-problems-in-scala

声明
该系列文章来自：http://aperiodic.net/phil/scala/s-99/
大部分内容和原文相同,加入了部分自己的代码。
如有侵权，请及时联系本人。本人将立即删除相关内容。

P11 (*) Modified run-length encoding.

要求

Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms.

Example:

1 2	scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))

方案

(1) P10中返回的List元素类型是二元组(count,element),对list执行map判断 t._1是否为1

1 2	def encodeModified[T](list: List[T]): List[Any] = encode(list).map(e => if (e._1 == 1) e._2 else e)

P12 (**) Decode a run-length encoded list.

要求

Given a run-length code list generated as specified in problem P10, construct its uncompressed version.

Example:

1 2	scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))) res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

方案

(1) List.fill + flatMap

1 2	def decode[T](list: List[(Int, T)]): List[T] = list.flatMap(e => List.fill(e._1)(e._2))

P13 (**) Run-length encoding of a list (direct solution).

要求

Implement the so-called run-length encoding data compression method directly. I.e. don’t use other methods you’ve written (like P09’s pack); do all the work directly.

Example:

1 2	scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

方案

(1) span + 递归

def encodeDirect[T](list: List[T]): List[(Int, T)] = {
    if (list == Nil)
        return List()
    else {
        val (packed, tail) = list.span(_ == list.head)
        return (packed.length, packed.head) :: encodeDirect(tail)
    }
}

P14 (*) Duplicate the elements of a list.

要求

Example:

1 2	scala> duplicate(List('a, 'b, 'c, 'c, 'd)) res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)

方案

1
2
3

def duplicate[T](list: List[T]): List[T] = {
    list.flatMap { e => List(e, e) }
}

P15 (**) Duplicate the elements of a list a given number of times.

要求

Example:

1 2	scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd)) res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

方案

1
2
3

def duplicateN[T](n: Int, list: List[T]): List[T] = {
    list.flatMap { e => List.fill(n)(e) }
}

scala