Рассмотрим простую задачу по поиску максимально длинной сбалансированной подстроки. Задача предоставлена сайтом 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. Иначе выведите длину наидлиннейшей сбалансированной подстроки. Примеры входные …
Рубрика: Code
Продолжаем знакомство с элементарными сортировками. На этот раз разберем алгоритм сортировки методом “Выбора”. Он немного сложнее сортировки пузырьком, но только для понимания и занимает 9 срок кода. Да, метрика количество строк кода вообще не гуд, но я все же упоминаю ее для подтверждения элементарности алгоритма. Итак, как работает сортировка методом “Выбора”? Обратим внимание на название алгоритма. Вообще наименование методов, алгоритмов, переменных отдельный вид искусства. Сортировка “Выбором”. Похоже, что алгоритм что-то выбирает, скажите вы. Да, отвечу я. Мы выбираем минимальный/максимальный элемент …
Эта статья посвящена разбору задачи про игру в настольный теннис. Придумаем алгоритм для ее решения и напишем его на языке Java. Отмечу, что чистота кода в решении и принципы ООП принесены в жертву внятности и понятности алгоритма человеческому глазу как ни парадоксально, ведь как завещал дядя Боб чистота кода подразумевает написание исходного кода программ на человекопонятном языке. Ну да ладно, немного отошли от темы. Задача взята с одного из соревновательных раундов codeforces.com. Вашему внимание условие задачи: К теннисному столу выстроилась …
В 90% случаях, проходя интервью на должность разработчика в любой компании, вас попросят написать алгоритм сортировки. Поэтому можно сказать, что хорошего программиста от плохого отличает умение здесь и сейчас написать алгоритм сортировки (но это не точно). Как не парадоксально, многие синьоры сходу не напишут вам ту или иную сортировку, ведь в современных языка программирования в Java в том числе, уже реализованы методы сортировки, причем метод sort() работает таким образом, что анализирует объем данных для сортировки и выбирает на основании наиболее …
Как оценить скорость и сложность алгоритма? Принято брать за основную метрику оценки зависимость между необходимым количеством шагов алгоритма до достижения результата и размером данных, над которым этот алгоритм работает. Рассмотрим на простом примере. Сравним алгоритмы линейного и двоичного поиска. Пусть размер массива равен 100. Тогда нетрудно догадаться, что для поиска элемента линейным алгоритмом понадобится 50 шагов в худшем случае. При работе же двоичного поиска максимальное количество шагов будет равно 7. Пусть теперь размер массива 10 000. Линейный поиск справится за 5000 …