🟡Medium
456. 132 Pattern

Company: 📱🏢🅰️

📝Дан массив целых чисел nums. Шаблон 132 представляет собой подпоследовательность из трех целых чисел nums[i], nums[j], nums[k], где i < j < k и nums[i] < nums[k] < nums[j]

Верните true, если в массиве есть шаблон 132

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

#leetcode456 | #medium #stack

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

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

💡 Идея
🟦Для поиска элементов j и k будем поддерживать монотонный стек, в котором все элементы идут в убывающем порядке. Поэтому в тот момент, когда наш стек не пуст, у нас всегда есть две найденные позиции, для которых выполняется условие nums[k] < nums[j]

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

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

1⃣Удаляем элементы из стека, пока он не пуст и его верхний элемент меньше или равен текущему

2⃣Проверяем главное условие nums[i] < nums[k] < nums[j]:
▫стек не пуст — значит в нем сейчас содержится элемент j, а текущий является k
▫минимальный элемент слева от индекса j меньше текущего элемента k (ищем элемент i)

3⃣Добавляем индекс текущего элемента в стек

👩‍💻 Java Algo | #solution456

🔴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