99 задач по Scala с решениями
На основе статьи S-99: Ninety-Nine Scala Problems
Часть 1. Задачи 1 – 28
Задача 1
Найдите последний элемент списка
1 2 |
scala> last(List(1, 1, 2, 3, 5, 8)) res0: Int = 8 |
Задача 2
Найдите предпоследний элемент списка
1 2 |
scala> penultimate(List(1, 1, 2, 3, 5, 8)) res0: Int = 5 |
Задача 3
Найдите k-ый элемент списка
1 2 |
scala> nth(2, List(1, 1, 2, 3, 5, 8)) res0: Int = 2 |
Задача 4
Найдите количество элементов списка
1 2 |
scala> length(List(1, 1, 2, 3, 5, 8)) res0: Int = 6 |
Задача 5
Переверните список
1 2 |
scala> reverse(List(1, 1, 2, 3, 5, 8)) res0: List[Int] = List(8, 5, 3, 2, 1, 1) |
Задача 6
Определите, является ли список палиндромом
1 2 |
scala> isPalindrome(List(1, 2, 3, 2, 1)) res0: Boolean = true |
1 2 |
scala> isPalindrome(List(1, 2, 3, 2, 3)) res0: Boolean = false |
Задача 7
Преобразуйте многомерный список в одномерный
1 2 |
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8)))) res0: List[Any] = List(1, 1, 2, 3, 5, 8) |
Задача 8
Замените серии одинаковых элементов списка на одиночный элемент
1 2 |
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) |
Задача 9
Замените серию одинаковых элементов на список из этих элементов
1 2 |
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)) |
Задача 10
Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии.
1 2 |
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)) |
Задача 11
Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии, но если серия состоит из одного элемента, то оставьте элемент без замены на кортеж.
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)) |
Задача 12
Дан список из кортежей вида (‘a, k). Получите список, полученный преобразований кортежей в серию элементов a указанной длины k.
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) |
Задача 13
Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии
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)) |
Задача 14
Продублируйте каждый элемент в списке
1 2 |
scala> duplicate(List('a, 'b, 'c, 'c, 'd)) res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd) |
Задача 15
Продублируйте каждый элемент в списке данное количество раз
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) |
Задача 16
Удалите каждый n-ый элемент из списка
1 2 |
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) |
Задача 17
Разделите список на две части (длина первой части задана)
1 2 |
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)) |
Задача 18
Дан список и два индекса k и p. Получите фрагмент из списка с k-ого по p-ый (не включая p-ый)
1 2 |
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) res0: List[Symbol] = List('d, 'e, 'f, 'g) |
Задача 19
Осуществите циклический сдвиг элементов списка на данное количество символов.
1 2 3 4 5 |
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) |
Задача 20
Удалите k-ый элемент списка. Функция должна вернуть новый список и удаленный элемент
1 2 |
scala> removeAt(1, List('a, 'b, 'c, 'd)) res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b) |
Задача 21
Вставьте элемент на указанное место в списке
1 2 |
scala> insertAt('new, 1, List('a, 'b, 'c, 'd)) res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd) |
Задача 22
Создайте список с элементами по заданному диапазону
1 2 |
scala> range(4, 9) res0: List[Int] = List(4, 5, 6, 7, 8, 9) |
Задача 23
Дан список. Выберите из него k элементов в случайном порядке без повторов.
1 2 |
scala> randomSelect(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h)) res0: List[Symbol] = List('e, 'd, 'a) |
Задача 24
Выберите k различных случайных чисел из чисел 1, 2, … , n
1 2 |
scala> lotto(6, 49) res0: List[Int] = List(23, 1, 17, 33, 21, 37) |
Задача 25
Получите случайную перестановку элементов данного списка
1 2 |
scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f)) res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f) |
Задача 26
Получите всевозможные наборы k различных чисел, выбранные случайным образом из чисел 1, 2, …, n. Порядок чисел в наборе не важен.
1 2 |
scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f)) res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ... |
Задача 27
Сгруппируйте элементы множества в непересекающиеся подмножества
1 2 |
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")) res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ... |
Задача 28
Дан двумерный список (список, элементами которого являются списки). Выполните сортировку списка по длине вложенных списков.
1 2 |
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))) res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l)) |
Решения
Задача 1
// 1 способ
def lastBuiltin[A](ls: List[A]): A = ls.last
// 2 способ
def lastRecursive[A](ls: List[A]): A = ls match {
case h :: Nil => h
case _ :: tail => lastRecursive(tail)
case _ => throw new NoSuchElementException
}
Задача 2
// 1 способ
def penultimateBuiltin[A](ls: List[A]): A =
if (ls.isEmpty) throw new NoSuchElementException
else ls.init.last
// 2 способ
def penultimateRecursive[A](ls: List[A]): A = ls match {
case h :: _ :: Nil => h
case _ :: tail => penultimateRecursive(tail)
case _ => throw new NoSuchElementException
}
Задача 3
// 1 способ
def nthBuiltin[A](n: Int, ls: List[A]): A =
if (n >= 0) ls(n)
else throw new NoSuchElementException
// 2 способ
def nthRecursive[A](n: Int, ls: List[A]): A = (n, ls) match {
case (0, h :: _ ) => h
case (n, _ :: tail) => nthRecursive(n – 1, tail)
case (_, Nil) => throw new NoSuchElementException
}
Задача 4
// 1 способ
def lengthBuiltin[A](ls: List[A]): Int = ls.length
// 2 способ
def lengthRecursive[A](ls: List[A]): Int = ls match {
case Nil => 0
case _ :: tail => 1 + lengthRecursive(tail)
}
// 3 способ
def lengthTailRecursive[A](ls: List[A]): Int = {
def lengthR(result: Int, curList: List[A]): Int = curList match {
case Nil => result
case _ :: tail => lengthR(result + 1, tail)
}
lengthR(0, ls)
}
// 4 способ
def lengthFunctional[A](ls: List[A]): Int = ls.foldLeft(0) { (c, _) => c + 1 }
Задача 5
// 1 способ
def reverseBuiltin[A](ls: List[A]): List[A] = ls.reverse
// 2 способ O(n^2)
def reverseRecursive[A](ls: List[A]): List[A] = ls match {
case Nil => Nil
case h :: tail => reverseRecursive(tail) ::: List(h)
}
// 3 способ
def reverseTailRecursive[A](ls: List[A]): List[A] = {
def reverseR(result: List[A], curList: List[A]): List[A] = curList match {
case Nil => result
case h :: tail => reverseR(h :: result, tail)
}
reverseR(Nil, ls)
}
// 4 способ
def reverseFunctional[A](ls: List[A]): List[A] =
ls.foldLeft(List[A]()) { (r, h) => h :: r }
Задача 6
// 1 способ
def isPalindrome[A](ls: List[A]): Boolean = ls == ls.reverse
// 2 способ
1 2 3 4 5 |
def isPalindrome[A](l: List[A]):Boolean = l match { case Nil => true case List(a) => true case list => (list.head == list.last && isPalindrome(list.tail.init)) } |
Задача 7
def flatten(ls: List[Any]): List[Any] = ls flatMap {
case ms: List[_] => flatten(ms)
case e => List(e)
}
Задача 8
// 1 способ
def compressRecursive[A](ls: List[A]): List[A] = ls match {
case Nil => Nil
case h :: tail => h :: compressRecursive(tail.dropWhile(_ == h))
}
// 2 способ
def compressTailRecursive[A](ls: List[A]): List[A] = {
def compressR(result: List[A], curList: List[A]): List[A] = curList match {
case h :: tail => compressR(h :: result, tail.dropWhile(_ == h))
case Nil => result.reverse
}
compressR(Nil, ls)
}
// 3 способ
def compressFunctional[A](ls: List[A]): List[A] =
ls.foldRight(List[A]()) { (h, r) =>
if (r.isEmpty || r.head != h) h :: r
else r
}
Задача 9
def pack[A](ls: List[A]): List[List[A]] = {
if (ls.isEmpty) List(List())
else {
val (packed, next) = ls span { _ == ls.head }
if (next == Nil) List(packed)
else packed :: pack(next)
}
}
Задача 10
import P09.pack
def encode[A](ls: List[A]): List[(Int, A)] =
pack(ls) map { e => (e.length, e.head) }
Задача 11
// 1 способ
import P10.encode
def encodeModified[A](ls: List[A]): List[Any] =
encode(ls) map { t => if (t._1 == 1) t._2 else t }
// 2 способ
def encodeModified2[A](ls: List[A]): List[Either[A, (Int, A)]] =
encode(ls) map { t => if (t._1 == 1) Left(t._2) else Right(t) }
Задача 12
def decode[A](ls: List[(Int, A)]): List[A] =
ls flatMap { e => List.make(e._1, e._2) }
Задача 13
def encodeDirect[A](ls: List[A]): List[(Int, A)] =
if (ls.isEmpty) Nil
else {
val (packed, next) = ls span { _ == ls.head }
(packed.length, packed.head) :: encodeDirect(next)
}
Задача 14
// 1 способ
1 |
def duplicate[A](ls: List[A]): List[A] = ls flatMap { e => List(e, e) } |
// 2 способ
1 2 3 4 |
def dubl(l: List[Int]): List[Int] = l match { case Nil => Nil case h :: t => h :: h :: dubl(t) } |
Задача 15
1 |
def dublN(n: Int, l: List[Int]): List[Int] = l.flatMap(e => List.fill(n)(e)) |
Задача 16
// 1 способ
1 2 3 |
def dropN(n: Int, l: List[Int]): List[Int] = { l.zipWithIndex.filter(pair => (1 + pair._2) % n != 0).map(_._1) } |
// 2 способ
def dropRecursive[A](n: Int, ls: List[A]): List[A] = {
def dropR(c: Int, curList: List[A]): List[A] = (c, curList) match {
case (_, Nil) => Nil
case (1, _ :: tail) => dropR(n, tail)
case (_, h :: tail) => h :: dropR(c – 1, tail)
}
dropR(n, ls)
}
// 3 способ
def dropTailRecursive[A](n: Int, ls: List[A]): List[A] = {
def dropR(c: Int, curList: List[A], result: List[A]): List[A] = (c, curList) match {
case (_, Nil) => result.reverse
case (1, _ :: tail) => dropR(n, tail, result)
case (_, h :: tail) => dropR(c – 1, tail, h :: result)
}
dropR(n, ls, Nil)
}
Задача 17
// 1 способ
def splitBuiltin[A](n: Int, ls: List[A]): (List[A], List[A]) = ls.splitAt(n)
// 2 способ
def splitRecursive[A](n: Int, ls: List[A]): (List[A], List[A]) = (n, ls) match {
case (_, Nil) => (Nil, Nil)
case (0, list) => (Nil, list)
case (n, h :: tail) => {
val (pre, post) = splitRecursive(n – 1, tail)
(h :: pre, post)
}
}
// 3 способ
def splitTailRecursive[A](n: Int, ls: List[A]): (List[A], List[A]) = {
def splitR(curN: Int, curL: List[A], pre: List[A]): (List[A], List[A]) =
(curN, curL) match {
case (_, Nil) => (pre.reverse, Nil)
case (0, list) => (pre.reverse, list)
case (n, h :: tail) => splitR(n – 1, tail, h :: pre)
}
splitR(n, ls, Nil)
}
//4 способ
def splitFunctional[A](n: Int, ls: List[A]): (List[A], List[A]) =
(ls.take(n), ls.drop(n))
Задача 18
// 1 способ
def sliceBuiltin[A](start: Int, end: Int, ls: List[A]): List[A] =
ls.slice(start, end)
// 2 способ
def sliceRecursive[A](start: Int, end: Int, ls: List[A]): List[A] =
(start, end, ls) match {
case (_, _, Nil) => Nil
case (_, e, _) if e <= 0 => Nil
case (s, e, h :: tail) if s <= 0 => h :: sliceRecursive(0, e – 1, tail)
case (s, e, h :: tail) => sliceRecursive(s – 1, e – 1, tail)
}
// 3 способ
def sliceTailRecursive[A](start: Int, end: Int, ls: List[A]): List[A] = {
def sliceR(count: Int, curList: List[A], result: List[A]): List[A] =
(count, curList) match {
case (_, Nil) => result.reverse
case (c, h :: tail) if end <= c => result.reverse
case (c, h :: tail) if start <= c => sliceR(c + 1, tail, h :: result)
case (c, _ :: tail) => sliceR(c + 1, tail, result)
}
sliceR(0, ls, Nil)
}
//4 способ
def sliceTailRecursive2[A](start: Int, end: Int, ls: List[A]): List[A] = {
def sliceR(count: Int, curList: List[A], result: List[A]): List[A] = {
if (curList.isEmpty || count >= end) result.reverse
else sliceR(count + 1, curList.tail,
if (count >= start) curList.head :: result
else result)
}
sliceR(0, ls, Nil)
}
//5 способ
def sliceFunctional[A](s: Int, e: Int, ls: List[A]): List[A] =
ls drop s take (e – (s max 0))
Задача 19
def rotate[A](n: Int, ls: List[A]): List[A] = {
val nBounded = if (ls.isEmpty) 0 else n % ls.length
if (nBounded < 0) rotate(nBounded + ls.length, ls)
else (ls drop nBounded) ::: (ls take nBounded)
}
Задача 20
// 1 способ
1 2 3 4 5 6 7 8 |
def removeAt(index: Int, l: List[Int]): (List[Int], Any) = { if (index > l.length - 1) (l, Nil) else ( l.take(index) ::: l.drop(index + 1), l(index) ) } |
// 2 способ
def removeAt[A](n: Int, ls: List[A]): (List[A], A) = 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
}
// 3 способ
def removeAt2[A](n: Int, ls: List[A]): (List[A], A) =
if (n < 0) throw new NoSuchElementException
else (n, ls) match {
case (_, Nil) => throw new NoSuchElementException
case (0, h :: tail) => (tail, h)
case (_, h :: tail) => {
val (t, e) = removeAt(n – 1, ls.tail)
(ls.head :: t, e)
}
}
Задача 21
// 1 способ
1 2 3 |
def insertN(element: Int, index: Int, l: List[Int]): List[Int] = { l.take(index) ::: List(element) ::: l.drop(index) } |
// 2 способ
1 2 3 4 5 6 7 8 9 |
def insertN(element: Int, index: Int, l: List[Int]): List[Int] = { def ins(k: Int, l: List[Int]): List[Int] = (k, l) match { case (0, _) => List(element) ::: l case (k, h :: tail) => h :: ins(k - 1, tail) case (k, Nil) => l } ins(index, l) } |
// 3 способ
def insertN[A](e: A, n: Int, ls: List[A]): List[A] = ls.splitAt(n) match {
case (pre, post) => pre ::: e :: post
}
Задача 22
// 1 способ
1 2 3 4 |
def range(left: Int, right: Int): List[Int] = (left, right) match { case (x, y) if x > y => Nil case (x, y) if x <= y => x :: range(x + 1, y) } |
// 2 способ
def rangeBuiltin(start: Int, end: Int): List[Int] = List.range(start, end + 1)
// 3 способ
def rangeRecursive(start: Int, end: Int): List[Int] =
if (end < start) Nil
else start :: rangeRecursive(start + 1, end)
// 4 способ
def rangeTailRecursive(start: Int, end: Int): List[Int] = {
def rangeR(end: Int, result: List[Int]): List[Int] = {
if (end < start) result
else rangeR(end – 1, end :: result)
}
rangeR(end, Nil)
}
//5 способ
def unfoldRight[A, B](s: B)(f: B => Option[(A, B)]): List[A] =
f(s) match {
case None => Nil
case Some((r, n)) => r :: unfoldRight(n)(f)
}
def rangeFunctional(start: Int, end: Int): List[Int] =
unfoldRight(start) { n =>
if (n > end) None
else Some((n, n + 1))
}
Задача 23
// 1 способ
def randomSelect1[A](n: Int, ls: List[A]): List[A] =
if (n <= 0) Nil
else {
val (rest, e) = removeAt((new util.Random).nextInt(ls.length), ls)
e :: randomSelect1(n – 1, rest)
}
// 2 способ
def randomSelect[A](n: Int, ls: List[A]): List[A] = {
def randomSelectR(n: Int, ls: List[A], r: util.Random): List[A] =
if (n <= 0) Nil
else {
val (rest, e) = removeAt(r.nextInt(ls.length), ls)
e :: randomSelectR(n – 1, rest, r)
}
randomSelectR(n, ls, new util.Random)
}
Задача 24
import P23.randomSelect
def lotto(count: Int, max: Int): List[Int] =
randomSelect(count, List.range(1, max + 1))
Задача 25
// 1 способ
import P23.randomSelect
def randomPermute1[A](ls: List[A]): List[A] = randomSelect(ls.length, ls)
// 2 способ
def randomPermute[A](ls: List[A]): List[A] = {
val rand = new util.Random
val a = ls.toArray
for (i <- a.length – 1 to 1 by -1) {
val i1 = rand.nextInt(i + 1)
val t = a(i)
a.update(i, a(i1))
a.update(i1, t)
}
a.toList
}
Задача 26
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n – 1, sl.tail) map {sl.head :: _}
}
Задача 27
import P26.combinations
def group3[A](ls: List[A]): List[List[List[A]]] =
for {
a <- combinations(2, ls)
noA = ls — a
b <- combinations(3, noA)
} yield List(a, b, noA — b)
def group[A](ns: List[Int], ls: List[A]): List[List[List[A]]] = ns match {
case Nil => List(Nil)
case n :: ns => combinations(n, ls) flatMap { c =>
group(ns, ls — c) map {c :: _}
}
}
Задача 28
import P10.encode
def lsort[A](ls: List[List[A]]): List[List[A]] =
ls sort { _.length < _.length }
def lsortFreq[A](ls: List[List[A]]): List[List[A]] = {
val freqs = Map(encode(ls map { _.length } sort { _ < _ }) map { _.swap }:_*)
ls sort { (e1, e2) => freqs(e1.length) < freqs(e2.length) }
}