Дисклеймер: если ты продвинутый разработчик с Х годами опыта, пожалуйста, закрой эту статью. Здесь ты не найдешь абсолютно ничего полезного для себя.

Итак, небольшое вступление. Когда мне впервые пришлось делать коммит на GitHub, я помню, что перерыла кучу источников, и везде все было как-то не так, как в итоге сделала я.

В этой статье я расскажу о том, как сделать первый коммит на GitHub, и как делать последующие. Только мой опыт и сочетание консоли и фич IntelliJ Idea + у меня mac os, поэтому здесь именно про него (важно для установки).

Погнали.

Задача этой статьи только одна - попробовать уложить принципы SOLID на понятных «бытовых» примерах, а уже потом посмотреть, как оно может работать на практике - в коде.

Итак, SOLID - это 5 принципов, которые используются при разработке приложений. На каждый принцип по букве:

1. S — Single Responsibility Principle (Принцип единственной ответственности)

Определение: Каждый класс должен выполнять только одну задачу.

Пример из жизни:

Например, мы купили шкаф для одежды. 

Есть много статей, в том числе и на хабре, где подробно рассказывается про бинарные деревья как про структуру данных. В этой статье я больше сосредоточусь на подходах к решению алгоритмических задач, где используются бинарные деревья.

Немного теории для общего понимания сути.

Бинарное дерево - это иерархические структура данных, в которой каждый узел имеет не более двух дочерних узлов. Узлы обычно называются правыми и левыми потомками. При этом каждый из потомков, в свою очередь тоже является узлом, который может иметь двух потомков. Если у узла нет потомков, такой узел называют листом.

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Пару статей назад я уже рассматривала один из алгоритмов Бойера-Мура, с помощью которого можно было найти подстроку в строке.

Сегодня хочу поболтать об алгоритме большинства голосов, который позволяется найти преобладающий элемент последовательности.

Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.

Условие здесь: https://leetcode.com/problems/most-frequent-even-element/description/

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Возвращаемся к Муру!

Кратко: на вход мы получаем массив, состоящий из чисел. Нужно найти число, которое встречается наибольшее количество раз. 

Не супер очевидно, но это число занимает больше половины элементов массива, т.е.

Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело. 

Queue - однонаправленная очередь, представляет собой структуру данных, которая строится по принципу FIFO (first-in-first-out). Другими словами, чем раньше элемент был добавлен в коллекцию, тем раньше он оттуда будет удален. 

Выжимка по методам:

Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.

Кажется, что для решения такой задачки отлично подходит бинарный поиск, который по итогу даст нам логарифмическую временную сложность. 

Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/

Но прежде чем приступить к решению, пройдемся по теории, что такое бинарный поиск и как его использовать.

Бинарный поиск - это поисковый алгоритм, который позволяет найти элемент в отсортированном массиве с логарифмической сложностью. Массив делится пополам, искомый элемент сравнивается с серединой массива, если искомый элемент больше, то поиск переходит в правую часть массива, и наоборот. После каждого перехода в правую или левую часть будет происходить сравнение серединного элемента с искомым до тех пор, пока он не будет найден.

Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.

Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать.

Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O(n).

Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 2³¹ - 1. Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2.

Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.

Алгоритм Хорспула используется для нахождения подстроки в строке. Например, у нас есть строка «The game is over» и подстрока «over». Алгоритм Хорспула вернет значение первого вхождения подстроки «over» в строку «The game is over», а именно 12. 

Фактически, данный алгоритм является упрощенным алгоритмом Бойера-Мура, который, считается работает лучше, чем стандартный алгоритм на случайных текстах, но в худшем случае его скорость равна |needle| * |haystack| вместо 3 х |haystack|. 

Тем не менее, для восприятия, на мой взгляд, он гораздо проще.

Итак, погнали.

Условие задачи с leetcode: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

Как работает алгоритм?

Строка и подстрока совмещаются по первому символу, и начинаются сравниваться от последнего символа к первому.

Для примера возьмем строку: «aabcdadbc» и подстроку «adb»

Совмещаются строки следующим образом (слева направо):

Рекурсивные методы в Java — это методы, которые вызывают сами себя и требуют осторожности с их обращением.

Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.

Базис — это условие выхода из рекурсии, а шаг — это вызов методом самого себя с измененными параметрами.

Самый частый пример, который можно встретить в интернете при попытке найти информацию о рекурсии — нахождение факториала числа. Быстренько пройдемся по нему перед рассмотрением более интересной задачки с leetCode.