99 задач по Scala с решениями. Задачи 1-28

99 задач по Scala с решениямиscala

На основе статьи S-99: Ninety-Nine Scala Problems

Часть 1. Задачи 1 - 28

Задача 1

Найдите последний элемент списка

Задача 2

Найдите предпоследний элемент списка

Задача 3

Найдите k-ый элемент списка

Задача 4

Найдите количество элементов списка

Задача 5

Переверните список

Задача 6

Определите, является ли список палиндромом

Задача 7

Преобразуйте многомерный список в одномерный

Задача 8

Замените серии одинаковых элементов списка на одиночный элемент

Задача 9

Замените серию одинаковых элементов на список из этих элементов

Задача 10

Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии.

Задача 11

Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии, но если серия состоит из одного элемента, то оставьте элемент без замены на кортеж.

Задача 12

Дан список из кортежей вида ('a, k). Получите список, полученный преобразований кортежей в серию элементов a указанной длины k.

Задача 13

Дан список. Замените серию одинаковых элементов на кортеж из элемента серии и длину серии

Задача 14

Продублируйте каждый элемент в списке

Задача 15

Продублируйте каждый элемент в списке данное количество раз

Задача 16

Удалите каждый n-ый элемент из списка

Задача 17

Разделите список на две части (длина первой части задана)

Задача 18

Дан список и два индекса k и p. Получите фрагмент из списка с k-ого по p-ый (не включая p-ый)

Задача 19

Осуществите циклический сдвиг элементов списка на данное количество символов.

Задача 20

Удалите k-ый элемент  списка. Функция должна вернуть новый список и удаленный элемент

Задача 21

Вставьте элемент на указанное место в списке

Задача 22

Создайте список с элементами по заданному диапазону

Задача 23

Дан список. Выберите из него k элементов в случайном порядке без повторов.

Задача 24

Выберите k различных случайных чисел из чисел 1, 2, ... , n

Задача 25

Получите случайную перестановку элементов данного списка

Задача 26

Получите всевозможные наборы k различных чисел, выбранные случайным образом из чисел 1, 2, ..., n. Порядок чисел в наборе не важен.

Задача 27

Сгруппируйте элементы множества в непересекающиеся подмножества

Задача 28

Дан двумерный список (список, элементами которого являются списки). Выполните сортировку списка по длине вложенных списков.

 

Решения

Задача 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 способ

Задача 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 способ

// 2 способ

Задача 15

Задача 16

// 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  способ

// 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 способ

// 2 способ

// 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  способ

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

 

Добавить комментарий