🟡Medium
92. Reverse Linked List II

Company: 🔍📱🅰️

📝Дан связный список и два целых числа left и right (left <= right). Необходимо развернуть элементы списка на позициях от left до right включительно

💡: реализуйте алгоритм reverseList для [left, right], но сохраните узел перед left

#leetcode92 | #medium #linkedlist

✅ Решение задачи 92

Time: O(n)
Space: O(1)

💡 Идея
🟦Решение состоит в том, чтобы применить знакомый алгоритм переворачивания списка на промежутке [left, right], поэтому ведем подсчет узлов (n) и, если n стал равен left, применяем данный алгоритм, пока n меньше right

🟦Но, после такого применения алгоритма, остаются неправильные ссылки по краям перевернутого списка, поэтому во время прохода по списку, пока n < left, ведем вспомогательный узел dummy, который остановится прямо перед left

🟦Благодаря dummy, теперь можно выставить нужные ссылки — узел left ссылаем на следующий после right: dummy.next.next = curr, а узел перед left ссылаем на right: dummy.next = prev

🟦В конце возвращаем исходную голову списка, если left > 1, иначе dummy.next, так как голова списка в таком случае также будет изменена

👩‍💻 Java Algo | #solution92

🖼Иллюстрация алгоритма к задаче 92

Пример: head = [1,2,3,4,5], left = 2, right = 4

#figure #linkedlist

❗️Обновление

Теперь доступен отдельный канал JA Roadmap c полной навигацией по всем задачам.

В нем можно очень удобно повторять нужные темы, сразу переходя к постам.

Вскоре еще добавится полная RoadMap по самым нужным задачам для прохождения собеседования, а также топ задач в конкретные компании

Не пропускайте ➡️ JA Roadmap

🟡Medium
148. Sort List

Company: 📱📱🔍

📝Дан связный список, отсортируйте его в порядке возрастания

💡: рекурсивно делите список пополам и сортируйте каждую его часть, а затем объедините их

#leetcode148 | #medium #linkedlist

✅ Решение задачи 148

Time: O(nlogn)
Space: O(logn)

💡 Идея
🟦Для решения реализуем сортировку слиянием: рекурсивно делим список пополам, сортируем каждую часть, а затем собираем вместе

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

🟦Для этого реализуем функцию getMid с идеей, как в этом решении, но здесь при четной длине возвращаться будет первый средний узел (fast изначально ставим на head.next):

private ListNode getMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

🟦Далее рекурсивно вызываем исходную функцию для каждой части, после чего получаем их отсортированными. Теперь можно их соединить, используя функцию merge:

➖проходим по обоим спискам, пока их указатели не равны null, выбираем наименьший узел из двух текущих и добавляем его в результат

➖после цикла присоединяем остаток одного из списков

🟦В итоге список последовательно делится на всё более мелкие части, пока не дойдет до одного узла, затем с помощью функции merge все части постепенно соединяются в один отсортированный список и в результате мы получаем правильный ответ

👩‍💻 Java Algo | #solution148

🔴Hard
23. Merge k Sorted Lists

Company: 🏢📱❤️

📝Вам дан массив k связанных списков lists, где каждый отсортирован в порядке возрастания.

Объедините все списки в один отсортированный и верните его

💡: соединяйте списки попарно с шагом, который постепенно увеличивается в 2 раза

#leetcode23 | #hard #linkedlist

✅ Решение задачи 23

Time: O(nlogk)
Space: O(1)

💡 Идея
🟦Одним из простых решений могло стать последовательное слияние всех списков с первым, но тогда бы мы получили сложность по времени O(nk), что не так хорошо

🟦Вместо этого можно соединять все списки парами с шагом step, пока данный шаг меньше длины массива

🟦В начале step равен 1, то есть мы соединяем только текущий и следующий список: merge(list[i], list[i + step]), но далее — после каждого прохода по массиву, мы увеличиваем его в два раза, чтобы объединять уже более длинные промежуточные списки

🟦При этом шаг i прохода по массиву должен быть в два раза больше step, чтобы “переступать” через уже объединенные списки, не затрагивая их повторно

🟦Таким образом, массив списков делится и объединяется по парам logk раз и в итоге мы получаем сложность O(nlogk)

👩‍💻 Java Algo | #solution23

🖼Иллюстрация алгоритма к задаче 23

#figure #linkedlist

🔴Hard
25. Reverse Nodes in k-Group

Company: 🔍🅰️🚀

📝Дан односвязный список и целое число k. Требуется переворачивать список по группам из k узлов.

Если число узлов не кратно k, то оставшиеся узлы оставьте в том же порядке

💡: передвигайте указатель на k вперед для отделения группы узлов, после чего используйте алгоритм переворачивания

#leetcode25 | #hard #linkedlist

✅ Решение задачи 25

Time: O(n)
Space: O(1)

💡 Идея
🟦В основе решения — вспомогательная функция getKNode, которая возвращает k-й узел от начала текущей группы. Если такой узел существует, значит группа полная и её можно перевернуть знакомым алгоритмом

🟦Перед разворотом сохраняем начало следующей группы: kNode.next и используем его как начальное значение для prev, чтобы сразу соединить текущую группу с оставшейся частью списка

🟦После разворота соединяем предыдущую часть списка с новой головой группы: prevPart.next = kNode, затем сдвигаем prevPart к концу текущей уже перевёрнутой группы

🟦Таким образом, список обрабатывается по частям длиной k, каждая из которых переворачивается и аккуратно соединяется с остальными, обеспечивая правильную структуру

👩‍💻 Java Algo | #solution25

➡️ Стартуем тему бинарного поиска

Представь, что кто-то загадал число от 1 до 100, и ты пытаешься его угадать, задавая вопросы: "твоё число больше этого?" или "меньше?".

Самый быстрый способ это сделать — каждый раз отбрасывать половину возможных вариантов. Для этого нужно начать с середины диапазона — с числа 50.

Спрашиваешь: "Твоё число больше 50?":
▫Если да — значит, всё, что меньше или равно 50, можно забыть. Теперь ты ищешь только в диапазоне от 51 до 100.
▫Если нет — значит, загаданное число находится где-то между 1 и 49.

Теперь снова берёшь середину нового диапазона — например, 75, и повторяешь. С каждым вопросом ты уменьшаешь количество возможных вариантов в два раза и быстро приближаешься к загаданному числу.

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

Пример кода бинарного поиска заданного числа target в массиве (задача):

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return -1;
    }
}

📎Обратите внимание, что для вычисления mid используется l + (r - l) / 2, вместо привычного (l + r) / 2. Это нужно для того, чтобы избежать переполнения int при больших значениях l и r.

#binarysearch

🟢Easy
35. Search Insert Position

Company: 📱🏢🚖

📝Дан отсортированный массив различных целых чисел и значение target. Верните индекс вставки target в массив.

Вам необходимо написать алгоритм со сложностью O(logn) по времени

💡: определите какой указатель бинарного поиска будет указывать на нужную позицию после цикла

#leetcode35 | #easy #binarysearch

✅ Решение задачи 35

Time: O(logn)
Space: O(1)

💡 Идея
🟦Назначаем границы начального диапазона: l = 0, r = nums.length – 1

🟦Начинаем поиск, пока границы находятся в правильном отношении: l <= r:
➖находим середину: mid = l + (r - l) / 2

➖сравниваем nums[mid] с target:
▫если nums[mid] < target: значит target должен быть правее, поэтому сдвигаем левую границу: l = mid + 1
▫иначе target должен быть на этой позиции или левее, значит: r = mid – 1

🟦когда цикл завершён, l указывает на позицию вставки:
➖если target есть в массиве — это будет индекс его вхождения
➖если нет — это место, куда его нужно вставить, чтобы массив остался отсортированным

👩‍💻 Java Algo | #solution35

🟢Easy
69. Sqrt(x)

Company: 📱📱📱

📝Дано неотрицательное целое число x, вернуть квадратный корень x, округленного вниз до ближайшего целого числа.

Не допускается использование встроенных функций

💡: ищите ответ в диапазоне от 2 до x / 2

#leetcode69 | #easy #binarysearch

✅ Решение задачи 69

Time: O(logx)
Space: O(1)

💡 Идея
🟦Если x равен 0 или 1, сразу возвращаем его, так как корень равен самому числу

🟦Установим начальные границы для бинарного поиска: l = 2, r = x / 2, так как квадратный корень числа x точно не больше x / 2 (если x > 1)

🟦Начинаем поиск, пока l <= r:
➖находим среднее значение между l и r и его квадрат: square = (long) mid * mid, используя приведение к long, чтобы избежать переполнения

➖если square == x, найден точный корень — сразу возвращаем mid
➖если square < x, ищем большее значение, сдвигая левую границу: l = mid + 1
➖если square > x, ищем меньшее значение, сдвигая правую границу: r = mid - 1

🟦После завершения поиска, l будет указывать на первое число, квадрат которого превышает x, поэтому нужный результат — l - 1, то есть нужный по условию округлённый вниз квадратный корень

👩‍💻 Java Algo | #solution

🟢Easy
1539. Kth Missing Positive Number

Company: 🏢📱📱

📝Дан отсортированный массив arr натуральных чисел и целое число k.

Верните k-ое пропущенное число в этом массиве

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

#leetcode1539 | #easy #binarysearch

✅ Решение задачи 1539

Time: O(logn)
Space: O(1)

💡 Идея
🟦Чтобы применить бинарный поиск, нужно уметь быстро определять сколько положительных чисел отсутствует перед i-м элементом массива

🟦Для этого сравним входной массив [2, 3, 4, 7, 11] с массивом без отсутствующих чисел: [1, 2, 3, 4, 5]. Количество отсутствующих целых чисел — это простая разница между соответствующими элементами этих двух массивов:
➖Перед 2 отсутствует: 2 - 1 = 1
➖Перед 7 отсутствует: 7 - 4 = 3
➖Перед 11 отсутствует: 11 - 5 = 6

То есть, получаем формулу: arr[i] – (i + 1)

🟦Теперь применяем бинарный поиск — ищем первую позицию, где пропущено k или больше чисел:
➖если количество отсутствующих чисел перед arr[mid] меньше k — продолжаем поиск в правой части массива: l = mid + 1

➖иначе случае продолжаем поиск на левой стороне: r = mid - 1

🟦После цикла получаем, что l = r + 1. Это означает, что на позиции r пропущено меньше, чем k чисел, а на l позиции — k или больше. То есть, k-е пропущенное число находится между arr[r] и arr[l]

🟦Количество целых чисел, пропущенных до arr[r]: missed = arr[r] - (r + 1), значит k- е число равно: arr[r] + (k - missed).
В итоге получаем такой ответ: arr[r] + k - (arr[r] - r - 1) = k + r + 1 = k + l

👩‍💻 Java Algo | #solution1539

🟡Medium
540. Single Element in a Sorted Array

Company: 🔍📱✴️

📝Дан отсортированный массив, состоящий из целых чисел, где каждый элемент встречается ровно дважды, за исключением одного элемента, который встречается ровно один раз.

Верните элемент, который встречается только один раз. Реализуйте решение за O(logn) по времени и O(1) по памяти

💡: используйте тот факт, что длина массива всегда нечетная

#leetcode540 | #medium #binarysearch

✅ Решение задачи 540

Time: O(logn)
Space: O(1)

💡 Идея
🟦Можно заметить, что подмассив с одним уникальным элементом всегда будет иметь нечетную длину, поэтому при передвижении указателей в бинарном поиске пользуемся именно этим свойством

🟦Но есть проблема — при вычислении среднего значения, mid может попасть как на первый элемент пары, так и на второй, поэтому важно уметь правильно определять границы левой и правой частей массива

🟦Для этого будем всегда вычислять четность левой части и, чтобы она была полной, при вычислении mid сдвигаем его на позицию вперед, если там такой же элемент

🟦Получаем левую часть с полными парами и сначала проверяем, что текущий элемент под mid имеет пару слева, иначе сразу возвращаем ответ, а затем вычисляем длину подмассива (mid – l + 1):
➖если нечетная — сдвигаем поиск левую сторону: r = mid – 1
➖иначе в правую: l = mid + 1

👩‍💻 Java Algo | #solution540

🟡Medium
2560. House Robber IV

Company: 🚔📱📱

📝Дан массив чисел, представляющий собой последовательность домов, в каждом из которых есть деньги. Грабитель хочет ограбить ровно k домов, но он не может грабить два соседних дома подряд.

Способность грабителя — это максимальная сумма, которую он способен украсть из одного дома.

Верните минимальную способность грабителя, чтобы бы он смог ограбить k домов

💡: ищите минимальную способность в диапазоне [min(a), max(a)] и для каждой проверяйте, можно ли ограбить k домов

#leetcode2560 | #medium #binarysearch