[TOC]
** 声明**
该系列文章来自：http://aperiodic.net/phil/scala/s-99/
大部分内容和原文相同,加入了部分自己的代码。
如有侵权，请及时联系本人。本人将立即删除相关内容。
P06 (*) Find out whether a list is a palindrome.
要求
判断一个list是不是回文
Example:
scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true
方案
- (1) 反转list之后和自身反转之前的元素顺序一致
def isPalindrome1[T](list: List[T]): Boolean =
list == list.reverse
P07 (**) Flatten a nested list structure.
要求
将一个内嵌N重list的list所有元素提取至一个新的list,新的list不能嵌套list结构
Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)
方案
- (1) 递归+List.flatMap
def flatten(list: List[Any]): List[Any] = list.flatMap {
case ls: List[_] => flatten(ls)
case e => List(e)
}
P08 (**) Eliminate consecutive duplicates of list elements.
要求
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
Example:
scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
方案
- (1) List.dropWhile + recursive
def compressRecursive[T](list: List[T]): List[T] = list match {
case Nil => Nil
case h :: tail => h :: compressRecursive(tail.dropWhile(e => e == h))
}
- (2) List.dropWhile + tail-recursive
def compressTailRecursive[T](list: List[T]): List[T] = {
def compressR(ret: List[T], ls: List[T]): List[T] = ls match {
case Nil => ret
case h :: tail => compressR(ret ::: List(h), ls.dropWhile(_ == h))
}
return compressR(Nil, list)
}
- (3) List.dropWhile + tail-recursive
def compressTailRecursive2[T](list: List[T]): List[T] = {
def compressR(ret: List[T], ls: List[T]): List[T] = ls match {
case Nil => ret.reverse
case h :: tail => compressR(h :: ret, ls.dropWhile(_ == h))
}
return compressR(Nil, list)
}
- (4) foldRight
def compressFunctional[A](ls: List[A]): List[A] =
ls.foldRight(List[A]()) { (h, r) =>
if (r.isEmpty || r.head != h)
h :: r
else
r
}
P09 (**) Pack consecutive duplicates of list elements into sublists.
要求
If a list contains repeated elements they should be placed in separate sublists.
Example:
scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
方案
- (1) span + 普通递归
def pack2[T](list: List[T]): List[List[T]] = list match {
case Nil => List(List())
case ls: List[T] => {
val (packed, tail) = ls.span(_ == ls.head)
if (tail == Nil)
List(packed)
else packed :: pack2(tail)
}
}
- (2) span + 尾递归
def pack[T](list: List[T]): List[List[T]] = {
def packR(ret: List[List[T]], ls: List[T]): List[List[T]] = ls match {
case Nil => ret
case head :: tail => {
val (l, r) = (head :: tail).span(_ == head)
packR(ret ::: List(l), r)
}
}
return packR(Nil, list)
}
P10 (*) Run-length encoding of a list.
要求
Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
Example:
scala> encode(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) map
def encode[T](list: List[T]): List[(Int, T)] =
pack(list).map(e => (e.length, e.head))
