Приветствую всех, кто интересуется алгоритмическим программированием. В этой подборке мы собрали задачи разного уровня сложности из надежных источников. Материал поможет вам отточить навыки написания чистого кода, потренировать логику и оценить свой текущий уровень подготовки.
Что было раньше:
В предыдущей части мы решили:
- Counting sheep... (Подсчет овец...)
- get character from ASCII Value (извлечение символа из значения ASCII)
- The First Non Repeated Character In A String (Первый неповторяющийся символ в строке)
- Dead Ants (Мертвые муравьи)
- The Clockwise Spiral (Спираль по часовой стрелке)
Решение новых задач:
Задача 1
Платформа: CodeWars
Название задачи: Easy SQL: Rounding Decimals (Простой SQL: округление десятичных знаков)
Ссылка на задачу: https://www.codewars.com/kata/594a6133704e4daf5d00003d
Сложность: 8 kyu
Уже решили (На момент написания статьи): 15 547 из 42 443
Тэги: Fundamentals, SQL
Оригинальное описание задачи:
Given the following table `decimals`:
decimals table schema
id (PK, int)
number1 (float)
number2 (float)
Return a table with two columns (`number1`, `number2`), the value in `number1` should be rounded down to the previous integer and the value in `number2` should be rounded up to the next integer.
Пояснение задачи:
Задача состоит в том, чтобы по таблице `decimals`, содержащей два числовых поля `number1` и `number2`, создать новую таблицу, где:
- Значение в поле `number1` округляется вниз до ближайшего целого числа (floor);
- Значение в поле `number2` округляется вверх до ближайшего целого числа (ceiling).
Пример исходной таблицы:
| id | number1 | number2 |
|----|---------|---------|
| 1 | 3.7 | 2.3 |
| 2 | 1.9 | 5.6 |
После выполнения запроса должна получиться таблица следующего вида:
| number1 | number2 |
|---------|---------|
| 3 | 3 |
| 1 | 6 |
Пояснение к решению:
1. Для получения значения, округленного вниз, используется функция округления вниз (floor), которая возвращает ближайшее целое число меньшее или равное числу.
Например, floor(3.7) = 3, floor(1.9) = 1.
2. Для получения значения, округленного вверх, используется функция округления вверх (ceil), которая возвращает ближайшее целое число большее или равное числу.
Например, ceil(2.3) = 3, ceil(5.6) = 6.
Таким образом, задача сводится к применению функций округления к каждому полю таблицы и формированию новой таблицы с результатами.
Задача 2
Платформа: CodeWars
Название задачи: Exclamation marks series #1: Remove an exclamation mark from the end of string (Серия уроков по восклицательным знакам №1: Удалите восклицательный знак из конца строки.)
Ссылка на задачу: https://www.codewars.com/kata/57fae964d80daa229d000126
Сложность: 8 kyu
Уже решили (На момент написания статьи): 35 298 из 120 833
Тэги: Fundamentals, Strings
Оригинальное описание задачи:
Description:
Remove an exclamation mark from the end of a string.
For a beginner kata, you can assume that the input data is always a string, no need to verify it.
Examples
"Hi!" ---> "Hi"
"Hi!!!" ---> "Hi!!"
"!Hi" ---> "!Hi"
"!Hi!" ---> "!Hi"
"Hi! Hi!" ---> "Hi! Hi"
"Hi" ---> "Hi"
Пояснение задачи:
Задача состоит в том, чтобы убрать восклицательный знак (`!`), стоящий в конце строки.
Примеры:
- Исходная строка "Hi!" → результат "Hi"
- Исходная строка "Hi!!!" → результат "Hi!!"
- Исходная строка "!Hi" → результат "!Hi"
- Исходная строка "!Hi!"` → результат "!Hi"
- Исходная строка "Hi! Hi!" → результат "Hi! Hi"
- Исходная строка "Hi" → результат `"Hi"`
Пояснение:
Алгоритм решения прост:
1. Проверяем последний символ строки.
2. Если это восклицательный знак (`!`), удаляем его.
3. Если восклицательного знака нет, возвращаем исходную строку без изменений.
Таким образом, задача сводится к проверке наличия последнего символа и его удаления, если это нужно.
Задача 3
Платформа: CodeWars
Название задачи: Lost number in number sequence (Потерянное число в числовой последовательности)
Ссылка на задачу: https://www.codewars.com/kata/595aa94353e43a8746000120
Сложность: 7 kyu
Уже решили (На момент написания статьи): 11 660 из 40 799
Тэги: Arrays, Algorithms
Оригинальное описание задачи:
An ordered sequence of numbers from 1 to N is given. One number might have deleted from it, then the remaining numbers were mixed. Find the number that was deleted.
Example:
- The starting array sequence is `[1,2,3,4,5,6,7,8,9]`
- The mixed array with one deleted number is `[3,2,4,6,7,8,1,9]`
- Your function should return the int `5`.
If no number was deleted from the starting array, your function should return the int `0`.
Note: N may be 1 or less (in the latter case, the first array will be `[]`).
Пояснение задачи:
Задача состоит в следующем:
Дана упорядоченная последовательность чисел от 1 до N, из которой случайно удалили одно число, после чего оставшиеся числа перемешали.
Необходимо восстановить и вернуть удалённое число.
Если исходная последовательность не была изменена (то есть, удаление не производилось), нужно вернуть специальный маркер (например, число 0 или специальное значение типа `None`, если используется соответствующий тип данных).
Примеры:
- Исходный массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Перемешанный массив с удалённым элементом: [3, 2, 4, 6, 7, 8, 1, 9]
- Результат: 5
- Исходный массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Перемешанный массив без изменений: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Результат: 0 (или `None` в случае использования типов `Option` в Rust) Ограничения:
- Размер входного массива может быть от 1 до произвольного значения N.
- Элементы массива представляют собой натуральные числа от 1 до N включительно.
- Из массива гарантированно удалён ровно один элемент.
Дополнительное замечание:
При реализации важно учитывать возможность пустого массива (N=1 или меньше), где изначально входной массив будет пустым (`[]`).
Задача 4
Платформа: CodeWars
Название задачи: Data compression using run-length encoding (Сжатие данных с использованием кодирования длин серий)
Ссылка на задачу: https://www.codewars.com/kata/578bf2d8daa01a4ee8000046
Сложность: 6 kyu
Уже решили (На момент написания статьи): 2 290 из 8 410
Тэги: Algorithms
Оригинальное описание задачи:
Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data are stored as a single data value and count.
A simple form of RLE would encode the string "AAABBBCCCD" as "3A3B3C1D" meaning, first there are `3 A`, then `3 B`, then `3 C` and last there is `1 D`.
Your task is to write a RLE encoder and decoder using this technique. The texts to encode will always consist of only uppercase characters, no numbers.
Пояснение задачи:
Задача состоит в реализации алгоритма сжатия данных методом run-length encoding (RLE) — простого метода без потерь, применяемого для уменьшения размера последовательностей одинаковых символов.
Описание задачи:
Необходимо написать код, выполняющий следующие функции:
1. Кодировщик (encoder): Преобразует строку, состоящую исключительно из заглавных букв, в её RLE-кодировку. То есть, исходная строка преобразуется в последовательность пар «количество символов» + «символ».
Например:
Вход: "AAABBBCCCD"
Выход: "3A3B3C1D"
2.Декодировщик (decoder): Восстанавливает исходную строку из RLE-кода обратно в исходный вид. Например:
Вход: "3A3B3C1D”
Выход: "AAABBBCCCD"
Примеры Кодировщик:
| Вход | Выход |
|--------------|----------------|
| "AAABBBCCCD" | "3A3B3C1D" |
| "AAAA" | "4A" |
| "ABC" | "1A1B1C" |
Декодировщик:
| Вход | Выход |
|--------------|----------------|
| "3A3B3C1D" | "AAABBBCCCD" |
| "4A" | "AAAA" |
| "1A1B1C" | "ABC" |
Дополнительные замечания
- Входные данные всегда будут состоять только из заглавных букв.
- Длина входной строки может быть любой, от пустой до достаточно длинной.
- Строка может содержать повторяющиеся символы подряд.
- При декодировании длина строки должна точно соответствовать количеству символов и их количеству, указанным в кодировке.
Подход к решению:
Для решения задачи используется простой подход:
1. Для кодирования:
- Идем по строке слева направо, подсчитывая количество подряд идущих одинаковых символов.
- Записываем количество и символ в результирующую строку.
2. Для декодирования:
- Разделяем строку на пары «количество-символ».
- Собираем строку, используя каждую пару.
Задача 5
Платформа: CodeWars
Название задачи: Surjection Count (Количество суръекций)
Ссылка на задачу: https://www.codewars.com/kata/6a92adf37a5942e596d3e89f
Сложность: 6 kyu
Уже решили (На момент написания статьи): 137 из 440
Тэги: Combinatorics
Оригинальное описание задачи:
Notation and definition
- Let `[n]` be a set of all positive integers up to and including `n`, for all positive integers `n`.
- A function `f: X → Y` is considered surjective, if all elements in the codomain `Y` are paired up with at least one element from the domain `X`.
Task
Given the inputs `n` and `k`, find the number of surjections for `f: [n]→[k]`.
Examples
surjections(3, 2) -> 6
surjections(6, 2) -> 62
surjections(5, 3) -> 150
Constraints `1 ≤ k ≤ n ≤ 300`
Good luck!
Пояснение задачи:
Задача состоит в подсчёте количества всех возможных сюръективных (взаимно однозначных) отображений множества натуральных чисел от 1 до n в множество целых чисел от 1 до k.
Основные определения и обозначения:
- Множество [n] = {1, 2, ..., n} — это множество первых n положительных целых чисел.
- Отображение f : X → Y называется сюръективным (или «на»), если каждый элемент множества Y является образом хотя бы одного элемента из множества X.
Требования задачи:
Даны два числа n и k, где 1 ≤ k ≤ n ≤ 300.
Необходимо найти количество различных сюръективных функций f: [n] → [k].
Примеры:
- Для n=3 и k=2 существует 6 различных сюръективных отображений, например:
- f(1)=1, f(2)=1, f(3)=2
- f(1)=1, f(2)=2, f(3)=2
- f(1)=2, f(2)=1, f(3)=2
- и ещё три варианта.
- Для n=6 и k=2 количество таких отображений равно 62.
- Для n=5 и k=3 количество отображений составляет 150.
Ограничения: - 1 ≤ k ≤ n ≤ 300
Решение:
Для решения задачи эффективно использовать формулу Стирлинга второго рода, позволяющую посчитать количество разбиений множества из n элементов на k непустых подмножеств, умноженное на факториал k (количество способов упорядочить эти подмножества). Это даёт точное количество сюръективных отображений.
Заключение:
Платформа: CodeWars
Название задачи: Easy SQL: Rounding Decimals (Простой SQL: округление десятичных знаков)
Ссылка на задачу: https://www.codewars.com/kata/594a6133704e4daf5d00003d
Сложность: 8 kyu
Уже решили (На момент написания статьи): 15 547 из 42 443
Тэги: Fundamentals, SQL
Оригинальное описание задачи:
Given the following table `decimals`:
decimals table schema
id (PK, int)
number1 (float)
number2 (float)
Return a table with two columns (`number1`, `number2`), the value in `number1` should be rounded down to the previous integer and the value in `number2` should be rounded up to the next integer.
Пояснение задачи:
Задача состоит в том, чтобы по таблице `decimals`, содержащей два числовых поля `number1` и `number2`, создать новую таблицу, где:
- Значение в поле `number1` округляется вниз до ближайшего целого числа (floor);
- Значение в поле `number2` округляется вверх до ближайшего целого числа (ceiling).
Пример исходной таблицы:
| id | number1 | number2 |
|----|---------|---------|
| 1 | 3.7 | 2.3 |
| 2 | 1.9 | 5.6 |
После выполнения запроса должна получиться таблица следующего вида:
| number1 | number2 |
|---------|---------|
| 3 | 3 |
| 1 | 6 |
Пояснение к решению:
1. Для получения значения, округленного вниз, используется функция округления вниз (floor), которая возвращает ближайшее целое число меньшее или равное числу.
Например, floor(3.7) = 3, floor(1.9) = 1.
2. Для получения значения, округленного вверх, используется функция округления вверх (ceil), которая возвращает ближайшее целое число большее или равное числу.
Например, ceil(2.3) = 3, ceil(5.6) = 6.
Таким образом, задача сводится к применению функций округления к каждому полю таблицы и формированию новой таблицы с результатами.
Платформа: CodeWars
Название задачи: Exclamation marks series #1: Remove an exclamation mark from the end of string (Серия уроков по восклицательным знакам №1: Удалите восклицательный знак из конца строки.)
Ссылка на задачу: https://www.codewars.com/kata/57fae964d80daa229d000126
Сложность: 8 kyu
Уже решили (На момент написания статьи): 35 298 из 120 833
Тэги: Fundamentals, Strings
Оригинальное описание задачи:
Description:
Remove an exclamation mark from the end of a string.
For a beginner kata, you can assume that the input data is always a string, no need to verify it.
Examples
"Hi!" ---> "Hi"
"Hi!!!" ---> "Hi!!"
"!Hi" ---> "!Hi"
"!Hi!" ---> "!Hi"
"Hi! Hi!" ---> "Hi! Hi"
"Hi" ---> "Hi"
Пояснение задачи:
Задача состоит в том, чтобы убрать восклицательный знак (`!`), стоящий в конце строки.
Примеры:
- Исходная строка "Hi!" → результат "Hi"
- Исходная строка "Hi!!!" → результат "Hi!!"
- Исходная строка "!Hi" → результат "!Hi"
- Исходная строка "!Hi!"` → результат "!Hi"
- Исходная строка "Hi! Hi!" → результат "Hi! Hi"
- Исходная строка "Hi" → результат `"Hi"`
Пояснение:
Алгоритм решения прост:
1. Проверяем последний символ строки.
2. Если это восклицательный знак (`!`), удаляем его.
3. Если восклицательного знака нет, возвращаем исходную строку без изменений.
Таким образом, задача сводится к проверке наличия последнего символа и его удаления, если это нужно.
Платформа: CodeWars
Название задачи: Lost number in number sequence (Потерянное число в числовой последовательности)
Ссылка на задачу: https://www.codewars.com/kata/595aa94353e43a8746000120
Сложность: 7 kyu
Уже решили (На момент написания статьи): 11 660 из 40 799
Тэги: Arrays, Algorithms
Оригинальное описание задачи:
An ordered sequence of numbers from 1 to N is given. One number might have deleted from it, then the remaining numbers were mixed. Find the number that was deleted.
Example:
- The starting array sequence is `[1,2,3,4,5,6,7,8,9]`
- The mixed array with one deleted number is `[3,2,4,6,7,8,1,9]`
- Your function should return the int `5`.
If no number was deleted from the starting array, your function should return the int `0`.
Note: N may be 1 or less (in the latter case, the first array will be `[]`).
Пояснение задачи:
Задача состоит в следующем:
Дана упорядоченная последовательность чисел от 1 до N, из которой случайно удалили одно число, после чего оставшиеся числа перемешали.
Необходимо восстановить и вернуть удалённое число.
Если исходная последовательность не была изменена (то есть, удаление не производилось), нужно вернуть специальный маркер (например, число 0 или специальное значение типа `None`, если используется соответствующий тип данных).
Примеры:
- Исходный массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Перемешанный массив с удалённым элементом: [3, 2, 4, 6, 7, 8, 1, 9]
- Результат: 5
- Исходный массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Перемешанный массив без изменений: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Результат: 0 (или `None` в случае использования типов `Option` в Rust) Ограничения:
- Размер входного массива может быть от 1 до произвольного значения N.
- Элементы массива представляют собой натуральные числа от 1 до N включительно.
- Из массива гарантированно удалён ровно один элемент.
Дополнительное замечание:
При реализации важно учитывать возможность пустого массива (N=1 или меньше), где изначально входной массив будет пустым (`[]`).
Платформа: CodeWars
Название задачи: Data compression using run-length encoding (Сжатие данных с использованием кодирования длин серий)
Ссылка на задачу: https://www.codewars.com/kata/578bf2d8daa01a4ee8000046
Сложность: 6 kyu
Уже решили (На момент написания статьи): 2 290 из 8 410
Тэги: Algorithms
Оригинальное описание задачи:
Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data are stored as a single data value and count.
A simple form of RLE would encode the string "AAABBBCCCD" as "3A3B3C1D" meaning, first there are `3 A`, then `3 B`, then `3 C` and last there is `1 D`.
Your task is to write a RLE encoder and decoder using this technique. The texts to encode will always consist of only uppercase characters, no numbers.
Пояснение задачи:
Задача состоит в реализации алгоритма сжатия данных методом run-length encoding (RLE) — простого метода без потерь, применяемого для уменьшения размера последовательностей одинаковых символов.
Описание задачи:
Необходимо написать код, выполняющий следующие функции:
1. Кодировщик (encoder): Преобразует строку, состоящую исключительно из заглавных букв, в её RLE-кодировку. То есть, исходная строка преобразуется в последовательность пар «количество символов» + «символ».
Например:
Вход: "AAABBBCCCD"
Выход: "3A3B3C1D"
2.Декодировщик (decoder): Восстанавливает исходную строку из RLE-кода обратно в исходный вид. Например:
Вход: "3A3B3C1D”
Выход: "AAABBBCCCD"
Примеры Кодировщик:
| Вход | Выход |
|--------------|----------------|
| "AAABBBCCCD" | "3A3B3C1D" |
| "AAAA" | "4A" |
| "ABC" | "1A1B1C" |
Декодировщик:
| Вход | Выход |
|--------------|----------------|
| "3A3B3C1D" | "AAABBBCCCD" |
| "4A" | "AAAA" |
| "1A1B1C" | "ABC" |
Дополнительные замечания
- Входные данные всегда будут состоять только из заглавных букв.
- Длина входной строки может быть любой, от пустой до достаточно длинной.
- Строка может содержать повторяющиеся символы подряд.
- При декодировании длина строки должна точно соответствовать количеству символов и их количеству, указанным в кодировке.
Подход к решению:
Для решения задачи используется простой подход:
1. Для кодирования:
- Идем по строке слева направо, подсчитывая количество подряд идущих одинаковых символов.
- Записываем количество и символ в результирующую строку.
2. Для декодирования:
- Разделяем строку на пары «количество-символ».
- Собираем строку, используя каждую пару.
Платформа: CodeWars
Название задачи: Surjection Count (Количество суръекций)
Ссылка на задачу: https://www.codewars.com/kata/6a92adf37a5942e596d3e89f
Сложность: 6 kyu
Уже решили (На момент написания статьи): 137 из 440
Тэги: Combinatorics
Оригинальное описание задачи:
Notation and definition
- Let `[n]` be a set of all positive integers up to and including `n`, for all positive integers `n`.
- A function `f: X → Y` is considered surjective, if all elements in the codomain `Y` are paired up with at least one element from the domain `X`.
Task
Given the inputs `n` and `k`, find the number of surjections for `f: [n]→[k]`.
Examples
surjections(3, 2) -> 6
surjections(6, 2) -> 62
surjections(5, 3) -> 150
Constraints `1 ≤ k ≤ n ≤ 300`
Good luck!
Пояснение задачи:
Задача состоит в подсчёте количества всех возможных сюръективных (взаимно однозначных) отображений множества натуральных чисел от 1 до n в множество целых чисел от 1 до k.
Основные определения и обозначения:
- Множество [n] = {1, 2, ..., n} — это множество первых n положительных целых чисел.
- Отображение f : X → Y называется сюръективным (или «на»), если каждый элемент множества Y является образом хотя бы одного элемента из множества X.
Требования задачи:
Даны два числа n и k, где 1 ≤ k ≤ n ≤ 300.
Необходимо найти количество различных сюръективных функций f: [n] → [k].
Примеры:
- Для n=3 и k=2 существует 6 различных сюръективных отображений, например:
- f(1)=1, f(2)=1, f(3)=2
- f(1)=1, f(2)=2, f(3)=2
- f(1)=2, f(2)=1, f(3)=2
- и ещё три варианта.
- Для n=6 и k=2 количество таких отображений равно 62.
- Для n=5 и k=3 количество отображений составляет 150.
Ограничения: - 1 ≤ k ≤ n ≤ 300
Решение:
Для решения задачи эффективно использовать формулу Стирлинга второго рода, позволяющую посчитать количество разбиений множества из n элементов на k непустых подмножеств, умноженное на факториал k (количество способов упорядочить эти подмножества). Это даёт точное количество сюръективных отображений.
На этом всё! Надеюсь, статья была для вас полезной и интересной. Спасибо, что дочитали до конца! Буду рад пообщаться в комментариях: делитесь своими мыслями, предлагайте решения и давайте обсуждать алгоритмы в дружеской атмосфере. До скорой встречи!
Вступайте в нашу телеграмм-группу Инфостарт