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

P01 (*) Find the last element of a list.

要求

找出list中的最后一个元素

方案

  • (1)List自带的last方法(废话)
1
def builtInLast[T](list: List[T]): T =list.last
  • (2)将list反转，之后取其head
1
def lastByReverse[T](list: List[T]): T = list.reverse.head
  • (3)递归
1
2
3
4
5
def lastRecursive[T](list: List[T]): T = list match {
    case e :: Nil  => e
    case _ :: tail => lastRecursive(tail)
    case _         => throw new NoSuchElementException
}

P02(*) Find the last but one element of a list

要求

找出list中倒数第二个元素

Example:

1
2
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5

方案

  • (1) reverse.tail.head
1
2
3
4
def builtInSolution1[T](list: List[T]): T = {
    if (list.isEmpty || list.size <= 1) throw new NoSuchElementException
    list.reverse.tail.head
}
  • (2) init.last
1
2
3
4
def builtInSolution2[T](list: List[T]): T = {
    if (list.isEmpty || list.size <= 1) throw new NoSuchElementException
    list.init.last
}
  • (3) 递归
1
2
3
4
5
def recursiveSolution[T](list: List[T]): T = list match {
    case e :: _ :: Nil => e
    case _ :: tail     => recursiveSolution(tail)
    case _             => throw new NoSuchElementException
}

P03(*) Find the Kth element of a list.

要求

获取list中第n(从零开始)个元素

方案

  • (1) list自带索引(废话)
1
2
3
4
def builtInSolution[T](n: Int, list: List[T]): T = {
    if (n < 0) throw new NoSuchElementException
    list(n)
}
  • (2) 递归
1
2
3
4
5
def recursiveSolution[T](n: Int, list: List[T]): T = (n, list) match {
    case (0, e :: _)    => e
    case (x, _ :: tail) => recursiveSolution(x - 1, tail)
    case (_, Nil)       => throw new NoSuchElementException
}

P04 (*) Find the number of elements of a list.

要求

计算list的长度

Example:

1
2
scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6

方案

  • (1) list.length(废话)
1
def buildInSolution[T](list: List[T]): Int = list.length
  • (2) 普通递归
1
2
3
4
def recursiveSolution[T](list: List[T]): Int = list match {
    case Nil       => 0
    case _ :: tail => 1 + recursiveSolution(tail)
}
  • (3) 尾递归
1
2
3
4
5
6
7
def lengthTailRecursive[T](list: List[T]): Int = {
    def lengthR(x: Int, list: List[T]): Int = list match {
        case Nil       => x
        case _ :: tail => lengthR(x + 1, tail)
    }
    return lengthR(0, list)
}
  • (4) foldLeft
1
2
def builtInSolution2[T](list: List[T]): Int =
    list.foldLeft(0)((c, head) => c + 1)
  • (5) 遍历list(没啥好说的)

P05 (*) Reverse a list.

要求

逆转一个list

Example:

1
2
scala> reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)

方案

  • (1) list.reverse(废话)
1
def builtInSolution[T](list: List[T]): List[T] = list.reverse
  • (2) 递归
1
2
3
4
def recursiveSolution[T](list: List[T]): List[T] = list match {
    case Nil       => List()
    case h :: tail => recursiveSolution(tail) ::: List(h)
}
  • (3) 尾递归
1
2
3
4
5
6
7
8
def reverseTailRecursive[T](list: List[T]): List[T] = {
    def recursiveR(ret: List[T], l: List[T]): List[T] = l match {
        case Nil       => ret
        case h :: tail => recursiveR(h :: ret, tail)
    }
    return recursiveR(Nil, list)
}
  • (4) foldLeft
1
2
def reverseFunctional[A](ls: List[A]): List[A] =
    ls.foldLeft(List[A]()) { (ret, head) => head :: ret }