[TOC]

** 聲明**
該系列文章來自：http://aperiodic.net/phil/scala/s-99/
大部分內(nèi)容和原文相同,加入了部分自己的代碼。
如有侵權，請及時聯(lián)系本人。本人將立即刪除相關內(nèi)容。

P16 (**) Drop every Nth element from a list.

要求

Example:

scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)

方案

• (1) 遞歸

def drop[T](n: Int, list: List[T]): List[T] = {
    def dropR(x: Int, ls: List[T]): List[T] = (x, ls) match {
        case (_, Nil)          => Nil
        case (1, head :: tail) => dropR(n, tail)
        case (_, head :: tail) => head :: dropR(x - 1, tail)
    }
    dropR(n, list)
}

P17 (*) Split a list into two parts.

要求

The length of the first part is given. Use a Tuple for your result.

Example:

scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))

方案

• (1) take(n) + drop(n)

def split[T](x: Int, list: List[T]): (List[T], List[T]) = (list.take(x), list.drop(x))

• (2) take(n) + drop(n) == splitAt(n)

def split2[T](x: Int, list: List[T]): (List[T], List[T]) = list.splitAt(x)

• (3) 普通遞歸

def splitRecursive[T](x: Int, list: List[T]): (List[T], List[T]) =(x, list) match {
        case (_, Nil) => (Nil, Nil)
        case (0, ls)  => (Nil, ls)
        case (n, head :: tail) => {
            val (pre, post) = splitRecursive(n - 1, tail)
            return (head :: pre, post)
        }
    }

P18 (**) Extract a slice from a list.

要求

Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.

Example:

scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)

方案

• (1) List內(nèi)置slice(廢話)

def slice[T](from: Int, to: Int, list: List[T]): List[T] = 
    list.slice(from, to)

• (2) take + drop (實際上，內(nèi)置slice就是這么實現(xiàn)的)

def slice2[T](from: Int, to: Int, list: List[T]): List[T] = 
    list.drop(from).take(to - from)

P19 (**) Rotate a list N places to the left.

要求

Examples:

scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)

scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

方案

• (1) drop + take

def rotate[T](index: Int, list: List[T]): List[T] = {
    if (index < 0) {
        val i = list.length + index
        list.drop(i) ::: list.take(i)
    } else {
        list.drop(index) ::: list.take(index)
    }
}

def rotate2[T](index: Int, list: List[T]): List[T] = index match {
    case i if i < 0 => {
        val i = list.length + index
        list.drop(i) ::: list.take(i)
    }
    case _ => list.drop(index) ::: list.take(index)
}

P20 (*) Remove the Kth element from a list.

要求

Return the list and the removed element in a Tuple. Elements are numbered from 0.

Example:

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

方案

• (1) aplitAt

def removeAt[T](index: Int, list: List[T]): (List[T], T) = {
    if (index < 0) throw new NoSuchElementException
    val (prev, tail) = list.splitAt(index + 1)
    (prev.init ::: tail, prev.last)
}

另一寫法:

def removeAt2[T](n: Int, ls: List[T]): (List[T], T) = ls.splitAt(n) match {
    case (Nil, _) if n < 0 => throw new NoSuchElementException
    case (pre, e :: post)  => (pre ::: post, e)
    case (pre, Nil)        => throw new NoSuchElementException
}

• (2) 遞歸(這個寫的很惡心)

def removeAt3[T](index: Int, list: List[T]): (List[T], T) = {
    if (index < 0) throw new NoSuchElementException

    (index, list) match {
        case (_, Nil)          => throw new NoSuchElementException
        case (0, head :: tail) => (tail, head)
        case (i, head :: tail) => (head :: removeAt3(i - 1, tail)._1, removeAt3(i - 1, tail)._2)
    }
}

• (3) 遞歸

def removeAt4[T](index: Int, list: List[T]): (List[T], T) = {
    if (index < 0) throw new NoSuchElementException

    (index, list) match {
        case (_, Nil)          => throw new NoSuchElementException
        case (0, head :: tail) => (tail, head)
        case (_, head :: tail) => {
            val (prev, e) = removeAt4(index - 1, tail)
            (list.head :: prev, e)
        }
    }
}