🔴Hard
1106. Parsing A Boolean Expression

Company: 📱🔍🏢

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

Выражение состоит из:
▫'t' — true
▫'f' — false
▫'!(subExpr)' — логическое НЕ внутреннего выражения subExpr
▫'&(subExpr1, subExpr2, ...)' — логическое И внутренних выражений
▫'|(subExpr1, subExpr2, ...)' — логическое ИЛИ внутренних выражений

💡: складывайте в стек операторы и булевые значения, а при встрече ')' сразу обрабатывайте подвыражение

#leetcode1106 | #hard #stack

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

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

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

🟦если встретили ')', это знак, что пора обрабатывать внутреннее выражение:
➖достаем из стека все булевые значения, пока не встретили оператор, при этом помечаем — было ли хотя бы одно true или false

➖затем вычисляем подвыражение:
▫если оператор '&', ответ true, только, если не было false
▫если оператор '|', ответ true, если было хотя бы одно true
▫если оператор '!', переворачиваем булевое значение

🟦после полной обработки строки, в стеке остается только один символ — результат всего выражения, возвращаем true, если это 't'

👩‍💻 Java Algo | #solution1106

🔴Hard
1944. Number of Visible People in a Queue

Company: 🔍📱🏢

📝Вам дан массив heights различных целых чисел, где heights[i] представляет собой рост человека, стоящего на позиции i.

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

Верните массив result, где result[i] — количество людей, которых человек на позиции i может видеть справа от себя

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

#leetcode1944 | #hard #stack

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

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

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

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

🟦поэтому проходим исходный массив с конца, поддерживая убывающий стек:

➖для каждого элемента сначала удаляем с вершины стека все элементы, которые меньше него, одновременно считая их количество

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

➖затем добавляем текущий индекс в стек

👩‍💻 Java Algo | #solution1944

🔴Hard
768. Max Chunks To Make Sorted II

Company: 📱📱🔍

📝Дан массив целых чисел.

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

Найдите максимальное количество таких фрагментов, при котором выполняется условие

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

#leetcode768 | #hard #stack

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

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

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

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

🟦в итоге получаем следующий алгоритм на каждом шаге прохода по массиву:

➖пока текущий элемент меньше вершины стека, то есть он нарушает условие порядка фрагментов, мы удаляем элементы из стека (расширяем предыдущий фрагмент)

➖если текущий элемент больше или равен текущему максимуму, значит мы можем начать новый фрагмент:
▫кладем в стек currMax и обновляем его на текущий элемент

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

👩‍💻 Java Algo | #solution768

🔴Hard
224. Basic Calculator

Company: 🏢🚖🖼

📝Дана строка s, представляющее выражение, состоящее из цифр и символов '+', '-', '(', ')', ' '.

Верните результат выражения

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

#leetcode224 | #hard #stack

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

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

💡 Идея
🟦проходим по строке:
➖если символ цифра
▫строим текущее число, учитывая, что оно может быть многозначным

➖если символ оператор ('+' и '-')
▫добавляем к результату текущее число, умноженное на ранее сохранённый знак
▫сбрасываем текущее число
▫обновляем знак в соответствии с оператором ('+' → 1, '-' → -1)

➖если символ открывающая скобка
▫сохраняем текущий результат и знак в стек — они понадобятся после вычисления выражения в скобках
▫обнуляем результат и знак, чтобы начать вычисление новой подформулы внутри скобок

➖если символ закрывающая скобка:
▫завершаем вычисление текущего числа (умножаем на знак и прибавляем к результату)
▫достаём из стека знак и результат до скобки
▫умножаем текущий результат на сохранённый знак и прибавляем результат до скобки

👩‍💻 Java Algo | #solution224

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

Представь очередь за билетами на концерт. Каждый человек знает, кто следующий и никто не оглядывается назад.

Если ты решаешь пропустить вперёд своего друга, ты просто говоришь: "Я теперь за тобой", а он запоминает, кто должен быть следующим. Так работает вставка — связи между людьми меняются, но сама очередь не двигается.

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

А вот если ты пришёл в конец очереди и хочешь найти друга где-то в середине, тебе придётся пройти ее всю по порядку, спрашивая каждого: "Кто следующий?", пока не дойдёшь до нужного человека. Потому что в этой очереди никто не пронумерован — доступ возможен только шаг за шагом. Так работает поиск.

В задачах класс односвязного списка представлен как:

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

🟦Принципы LinkedList
▫Узел
Каждый элемент состоит из двух частей: значение и ссылка на следующий узел

▫Голова (Head)
Список начинается с одного элемента — головы, именно с неё начинается обход всего списка

▫Последовательный доступ
Нельзя просто взять и перейти сразу, например, к пятому элементу. Нужно идти от головы, шаг за шагом — пока не дойдёшь. Это похоже на то, как ты читаешь книгу — перелистывая страницу за страницей

▫Вставка
Сначала надо дойти до нужного места, затем поменять ссылки

▫Удаление
Похоже на вставку: находишь нужный узел и просто перенаправляешь ссылку предыдущего элемента мимо него, на следующий

#linkedlist

🟢Easy
876. Middle of the Linked List

Company: 🔍📱🏢

📝Дан односвязный список, вернуть его средний узел. Если имеется два средних узла, вернуть второй

💡: используйте быстрый указатель

#leetcode876 | #easy #linkedlist

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

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

💡 Идея
🟦Для решения использована техника двух указателей ("черепаха и заяц"):
▫один — медленный (slow), делает по одному шагу
▫второй — быстрый (fast), делает по два шага

🟦Получаем, что когда fast доходит до конца, slow всегда оказывается посередине в нужной позиции:
▫длина списка нечетная — ровно посередине
▫длина четная — на втором из двух средних узлов

👩‍💻 Java Algo | #solution876

🟢Easy
203. Remove Linked List Elements

Company: 🔍📱📱

📝Дан cвязный список и целое число val, удалите из списка все узлы, имеющие значение равное val

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

#leetcode203 | #easy #linkedlist

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

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

💡 Идея
🟦чтобы удалить текущий узел, значение которого равно val, необходимо ссылку предыдущего узла перенаправить через текущий: prev.next = curr.next, иначе просто передвинуть предыдущий узел: prev = curr

🟦но, что, если голова заданного списка так же будет удалена, как тогда вернуть ответ?

🟦для этого в начале введен вспомогательный узел sentinel с ссылкой на начало заданного списка, в конце sentinel.next указывает на обновленнный список

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

👩‍💻 Java Algo | #solution203

🟢Easy
160. Intersection of Two Linked Lists

Company: 🚖📱🏢

📝Даны два связных списка A и B, вернуть узел, в котором они пересекаются. Если такого узла нет, вернуть null

Попробуйте написать решение, используя O(1) памяти

💡: попробуйте выровнять A и B по длине переходом указателя на противоположный список

#leetcode160 | #easy #linkedlist

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

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

💡 Идея
🟦Найти пересечение двух списков было бы проще, если бы их длины были равны, тогда мы бы просто прошли по обоим спискам одновременно, пока не встретили бы пересечение

🟦Чтобы выровнять списки, можно найти их длины простым проходом со счетчиком, а затем передвинуть стартовый узел большего списка вперед на разницу значений

🟦Но есть более элегантный способ:

➖создаем два указателя: currA и currB и одновременно передвигаем их вперед

➖если один указатель дошёл до конца своего списка, он переходит в начало другого. То есть currA сначала проходит список A, затем список B, а currB наоборот

➖если указатель равны, прекращаем цикл и возвращаем ответ

🟦Почему это работает?
➖пусть длина списка A – a, B – b, тогда указатель сurrA пройдет a + b, а currB b + a

➖в результате перехода одного указателя на соседний список, они оба проходят a + b, поэтому списки гарантированно синхронизируются по длине и указатели либо встречаются в точке пересечения, либо оба становятся null

👩‍💻 Java Algo | #solution160

🟡Medium
24. Swap Nodes in Pairs

Company: 🏢🅰️🏢

📝Дан связный список, поменяйте местами каждые два соседних узла. Решите задачу, не изменяя значений в узлах списка

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

#leetcode24 | #medium #linkedlist

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

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

💡 Идея
🟦cоздаем вспомогательные узлы sentinel и prev, а затем проходим по списку, пока доступно два узла: текущий и следующий

🟦на каждом шаге последовательно меняем ссылки, держа в голове результат, который хотим получить. Разберем на примере prev -> 1 -> 2 -> 3:

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

▫меняем ссылку с предыдущего узла на второй, так как после перестановки он будет идти после него: prev -> 2

▫ссылку на следующий элемент от первого узла перекидываем через второй: 1 -> 3

▫и наконец, ссылку на следующий элемент от второго узла назначаем на первый узел, в итоге получаем: prev -> 2 -> 1 -> 3

▫далее обновляем prev на первый узел и переходим на следующую пару

👩‍💻 Java Algo | #solution24

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

#figure #linkedlist

🟡Medium
61. Rotate List

Company: 🔍🏢📱

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

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

#leetcode61 | #medium #linkedlist

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

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

💡 Идея
🟦Чтобы повернуть список на k позиций вправо, необходимо взять k последних узлов и поставить их перед началом. Поэтому нужно найти этот блок и поменять ссылки на его границах

🟦Для этого пройдем указателем curr до конца списка, заодно посчитаем его длину и избавимся от лишних поворотов, взяв остаток от деления для k

🟦сurr в данный момент находится в конце блока k, поэтому поменяем ссылку данного узла на начало списка, тем самым поставим данный блок перед началом

🟦далее необходимо оказаться перед началом блока k, чтобы завершить алгоритм, поэтому проходим указателем curr расстояние (n – k) и оказываемся в нужном месте

🟦далее запоминаем следующий узел для ответа (начало нового списка) и ссылаем текущий узел на null (конец нового списка)

👩‍💻 Java Algo | #solution61

🟡Medium
86. Partition List

Company: 📱🅰️🏢

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

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

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

#leetcode86 | #medium #linkedlist