День 4: Практический Smalltalk

Posted on May 13, 2022

Этот день целиком и полностью посвящен решению задач на Смолтоке.

Содержание

  • Подготовка;
  • Задача #1: Объединение K сортированных списков;
  • Задача #2: Наименьшее отсутствующее положительное число;
  • Задача #3: Поиск подстроки с конкатенацией всех слов.

Подготовка

  1. Открываем репозиторий для данного занятия и форкаем его в свой аккаунт.
  2. Качаем репозиторий в свой образ.
  3. Интересующие нас классы должны появиться в пакетах StClassRus-Day4 и StClassRus-Day4-Tests.

Задача #1: Объединение K сортированных списков

Источник: Leetcode

Постановка задачи

Вам дан массив K связанных списков, каждый из которых отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный и верните его.

Пример 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Пример 2

Input: lists = []
Output: []

Пример 3

Input: lists = [[]]
Output: []

Задача #2: Наименьшее отсутствующее положительное число

Источник: Leetcode

Постановка задачи

Вам дан неотсортированный массив чисел. Верните наименьшее отсутствующее положительное число.

Ваше решение должно иметь линейную сложность по времени и константную сложность по памяти.

Пример 1

Input: nums = [1,2,0]
Output: 3

Пример 2

Input: nums = [3,4,-1,1]
Output: 2

Пример 3

Input: nums = [7,8,9,11,12]
Output: 1

Задача #3: Поиск подстроки с конкатенацией всех слов

Источник: Leetcode

Постановка задачи

Вам дана стрoка s и массив строк words одинаковой длины. Верните все стартовые индексы таких подстрок в s, которые являются конкатенацией каждого слова из массива words ровно один раз и в любом порядке, без никаких дополнительных символов внутри.

Вы можете возвращать индексы в любом порядке.

Пример 1

Input: s = "barfoothefoobarman",
   words = ["foo","bar"]
Output: [0,9]

Пример 2

Input: s = "wordgoodgoodgoodbestword",
   words = ["word","good","best","word"]
Output: []

Пример 3

Input: s = "barfoofoobarthefoobarman",
   words = ["bar","foo","the"]
Output: [6,9,12]

Подсказка

Для наивного решения вам может понадобиться сообщение findStrig: и/или его частные формы. Такие сообщения поддерживают объекты класса String.

Вернуться к курсу