problem16-20

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

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内置slice(废话)

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

• (2) take + drop (实际上，内置slice就是这么实现的)

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)
        }
    }
}