В недавней статье мы рассматривали такую структура данных как стек. Если вы не знаете что такое стек, то обязательно перейдите по ссылке и почитайте, потому что сегодня мы разберем решение одной интересной задачи с сайта codeforces.com с использованием реализованного ранее нами стека. Вот условие задачи: В автобусе характеров есть n рядов сидений, в каждом по 2 места. В i-м ряду ширина обоих сидений равна w_i сантиметров. Все числа w_i различны. Изначально автобус пустой. На каждой из 2n остановок в автобус садится …
Метка: алгоритмы
Ранее мы рассмотрели сортировку “Пузырьком” и сортировку методом “Выбора”. В это статье коснемся еще одного метода упорядочения данных. Сортировка “Вставками” так же относится к элементарным сортировкам. Она чуть сложнее для понимания нежели две упомянутые выше, однако несмотря на аналогичную сложность алгоритма O(N^2), считается, что сортировка вставками работает эффективнее на небольших случайных массивах, а так же на частично упорядоченных массивах. На базе сортировки “Вставками” основан более быстрый метод сортировки “Шелла”. О нем мы поговорим в отдельной статье, сейчас же давайте разберемся …
Сегодня рассмотрим очередную задачу алгоритмического характера с сайта Codeforces. Не буду томить вас, поэтому сразу условие: Слава играет в свою любимую игру «Peace Lightning». Сейчас он играет на бомбардировщике на одной специфической карте. Более формально, карта представляет из себя клетчатое поле 1 × n, клетки которого пронумерованы от 1 до n, в каждой клетке может находиться один или несколько танков. Слава не знает количество танков и их расположение, так как летит очень высоко, но при этом он может сбросить бомбу в любую …
Рассмотрим простую задачу по поиску максимально длинной сбалансированной подстроки. Задача предоставлена сайтом codeforces.com. Использовать будем язык Java. Вот условие: Задана строка s, состоящая только из символов 0 и 1. Подстрока [l, r] в s — это строка slsl + 1sl + 2… sr, ее длина равна r - l + 1. Подстрока называется сбалансированной, если количество нулей (0) в ней совпадает с количеством единиц. Найдите длину наидлиннейшей сбалансированной подстроки s. Входные данные В первой строке записано одно целое число n (1 ≤ n ≤ 100000) — длина строки s. Вторая строка — строка s длиной ровно n. В s содержатся только символы 0 и 1. Выходные данные Если в s нет ни одной непустой сбалансированной подстроки, то выведите 0. Иначе выведите длину наидлиннейшей сбалансированной подстроки. Примеры входные …
Продолжаем знакомство с элементарными сортировками. На этот раз разберем алгоритм сортировки методом “Выбора”. Он немного сложнее сортировки пузырьком, но только для понимания и занимает 9 срок кода. Да, метрика количество строк кода вообще не гуд, но я все же упоминаю ее для подтверждения элементарности алгоритма. Итак, как работает сортировка методом “Выбора”? Обратим внимание на название алгоритма. Вообще наименование методов, алгоритмов, переменных отдельный вид искусства. Сортировка “Выбором”. Похоже, что алгоритм что-то выбирает, скажите вы. Да, отвечу я. Мы выбираем минимальный/максимальный элемент …