Ранее мы рассмотрели сортировку “Пузырьком” и сортировку методом “Выбора”. В это статье коснемся еще одного метода упорядочения данных. Сортировка “Вставками” так же относится к элементарным сортировкам. Она чуть сложнее для понимания нежели две упомянутые выше, однако несмотря на аналогичную сложность алгоритма O(N^2), считается, что сортировка вставками работает эффективнее на небольших случайных массивах, а так же на частично упорядоченных массивах. На базе сортировки “Вставками” основан более быстрый метод сортировки “Шелла”. О нем мы поговорим в отдельной статье, сейчас же давайте разберемся …
Метка: java
Сегодня рассмотрим очередную задачу алгоритмического характера с сайта Codeforces. Не буду томить вас, поэтому сразу условие: Слава играет в свою любимую игру «Peace Lightning». Сейчас он играет на бомбардировщике на одной специфической карте. Более формально, карта представляет из себя клетчатое поле 1 × n, клетки которого пронумерованы от 1 до n, в каждой клетке может находиться один или несколько танков. Слава не знает количество танков и их расположение, так как летит очень высоко, но при этом он может сбросить бомбу в любую …
Любое современное приложение работает с разного рода данными. Получает их, обрабатывает, анализирует, хранит. Сами же эти данные тоже должны где-то хранится. Так вот, данные хранятся в специальных базах данных, управляемых разного рода СУБД (Системами Управления Базами Данных), а JDBC (Java DataBase Connectivity) – Java API для взаимодействия с СУБД. Из некоторых важных характеристик JDBC API стоит отметить, то что он абстрактный (абстрагирует разработчика от нюансов конкретной СУДБ). При этом сам разработчик может использовать специфические детали СУБД. Как JDBC взаимодействует с …
Тема коллекций в Java настолько обширна и многогранна, что в рамках одной статьи описать их работу проблематично и неэффективно. Поэтому сегодня мы сделаем легкое прикосновение к теме коллекций в Java. Если говорить конкретно, то мы коснемся следующих тем: Java Collection Framework (JCF) Collection and Iterable List Set Map Java Collection Framework (JCF) Для чего вообще нужны коллекции? Очевидно, что для работы с группой неких связанных данных. Вы скажете: зачем нам нужны коллекции, если есть массивы? Да, такая структура данных как …
Рассмотрим простую задачу по поиску максимально длинной сбалансированной подстроки. Задача предоставлена сайтом 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. Иначе выведите длину наидлиннейшей сбалансированной подстроки. Примеры входные …