✅ Решение задачи 74
Time: O(log(mn))
Space: O(1)
📝 Идея
▫️Устанавливаем один указатель на первую строку, второй на последний элемент в строке
▫️Так как матрица отсортирована:
- если текущий элемент меньше target - остается только увеличивать индекс строки, потому что мы уже находимся на максимальном элементе в этой строке
- если больше - остается только уменьшать индекс столбца, так как мы уже дошли до нужной строки и меньшие элементы находятся только слева
#solution74
Time: O(log(mn))
Space: O(1)
📝 Идея
▫️Устанавливаем один указатель на первую строку, второй на последний элемент в строке
▫️Так как матрица отсортирована:
- если текущий элемент меньше target - остается только увеличивать индекс строки, потому что мы уже находимся на максимальном элементе в этой строке
- если больше - остается только уменьшать индекс столбца, так как мы уже дошли до нужной строки и меньшие элементы находятся только слева
#solution74
🟡 Medium
875. Koko Eating Bananas
Пример:
Подсказка:в каком диапазоне может находиться k, и как тогда можно применить бинарный поиск?
21/200
#medium
#leetcode875
875. Koko Eating Bananas
Пример:
Input: piles = [3,6,7,11], h = 8
Output: 4
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Подсказка:
21/200
#medium
#leetcode875
🟡 Medium
153. Find Minimum in Rotated Sorted Array
Пример:
Подсказка:какое условие выполняется для указателей left и right в отсортированном массиве?
22/200
#medium
#leetcode153
153. Find Minimum in Rotated Sorted Array
Пример:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: Исходный массив [1,2,3,4,5] был повернут 3 раза.
Input: nums = [11,13,15,17]
Output: 11
Explanation: Исходный массив [11,13,15,17] был повернут 4 раза.
Подсказка:
22/200
#medium
#leetcode153
✅ Решение задачи 875
Time: O(nlog(m))
Space: O(1)
📝 Идея
▫️Значение k может лежать в диапозоне от 1 до максимума в этом массиве (больше не имеет смысла)
▫️Бинарным поиском ищем минимальное значение k, при котором количество часов будет равно заданному h
#solution875
Time: O(nlog(m))
Space: O(1)
📝 Идея
▫️Значение k может лежать в диапозоне от 1 до максимума в этом массиве (больше не имеет смысла)
▫️Бинарным поиском ищем минимальное значение k, при котором количество часов будет равно заданному h
#solution875
✅ Решение задачи 153
Time: O(log(n))
Space: O(1)
📝 Идея
▫️В отсортированном массиве первый элемент всегда максимальный, поэтому необходимо найти такой указатель l на отрезке массива, чтобы выполнялось условие nums[l] <= nums[r]
#solution153
Time: O(log(n))
Space: O(1)
📝 Идея
▫️В отсортированном массиве первый элемент всегда максимальный, поэтому необходимо найти такой указатель l на отрезке массива, чтобы выполнялось условие nums[l] <= nums[r]
#solution153
🟢 Easy
643. Maximum Average Subarray I
Пример:
Подсказка:используйте "скользящее окно" длиной k
23/200
#easy
#leetcode643
643. Maximum Average Subarray I
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Максимальное среднее значение равно (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12,75
Подсказка:
23/200
#easy
#leetcode643
🟡 Medium
3. Longest Substring Without Repeating Characters
Пример:
Подсказка:какая структура данных подойдет для решения и как можно использовать подход sliding window?
24/200
#medium
#leetcode3
3. Longest Substring Without Repeating Characters
Пример:
Input: s = "abcabcbb"
Output: 3
Explanation: ответ: "abc" длиной 3.
Input: s = "pwwkew"
Output: 3
Explanation: ответ: "wke" длиной 3.
Подсказка:
24/200
#medium
#leetcode3
✅ Решение задачи 643
Time: O(n)
Space: O(1)
📝 Идея
▫️Посчитаем сумму первых k элементов, затем в новом цикле начиная с индекса k ищем максимально возможную сумму, добавляя к текущей сумме следующий элемент и удаляя при этом элемент i - k, чтобы размер "окна" не менялся
▫️Возвращаем полученную максимальную сумму, деленную на k (умножение на 1.0 нужно, чтобы привести сумму к типу double)
#solution643
Time: O(n)
Space: O(1)
📝 Идея
▫️Посчитаем сумму первых k элементов, затем в новом цикле начиная с индекса k ищем максимально возможную сумму, добавляя к текущей сумме следующий элемент и удаляя при этом элемент i - k, чтобы размер "окна" не менялся
▫️Возвращаем полученную максимальную сумму, деленную на k (умножение на 1.0 нужно, чтобы привести сумму к типу double)
#solution643
✅ Решение задачи 3
Time: O(n)
Space: O(n)
📝 Идея
▫️если set не содержит текущий символ, просто добавляем его и сравниваем длину текущего "окна" с максимумом
▫️если set содержит текущий символ, удаляем левую часть "окна", пока set содержит данный символ
#solution3
Time: O(n)
Space: O(n)
📝 Идея
▫️если set не содержит текущий символ, просто добавляем его и сравниваем длину текущего "окна" с максимумом
▫️если set содержит текущий символ, удаляем левую часть "окна", пока set содержит данный символ
#solution3
🟡 Medium
424. Longest Repeating Character Replacement
Пример:
Подсказка:какое условие должно выполняться для текущего отрезка строки, чтобы он подходил под ответ?
25/200
#medium
#leetcode424
424. Longest Repeating Character Replacement
Пример:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Замените две буквы «A» на две буквы «B» или наоборот.
Подсказка:
25/200
#medium
#leetcode424
🟡 Medium
567. Permutation in String
Пример:
Подсказка:какое общее свойство у строк, одна из которых является перестановкой другой?
26/200
#medium
#leetcode567
567. Permutation in String
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 содержит одну перестановку s1 ("ba").
Подсказка:
26/200
#medium
#leetcode567
✅ Решение задачи 424
Time: O(n)
Space: O(1)
📝 Идея
▫️Поскольку все символы в строке заглавные буквы, их количество в текущей подстроке считаем с помощью массива размером 26
▫️Условием для того, что подстрока подходит под возможный ответ:
- разница длины подстроки и самого встречающегося символа должна быть меньше или равна k, иначе удаляем символ с левого края
#solution424
Time: O(n)
Space: O(1)
📝 Идея
▫️Поскольку все символы в строке заглавные буквы, их количество в текущей подстроке считаем с помощью массива размером 26
▫️Условием для того, что подстрока подходит под возможный ответ:
- разница длины подстроки и самого встречающегося символа должна быть меньше или равна k, иначе удаляем символ с левого края
#solution424
✅ Решение задачи 567
Time: O(n)
Space: O(1)
📝 Идея
▫️Строка, которая является перестановкой другой строки имеет такое же количество символов, поэтому, перебирая вторую строку, сравниваем - если массивы строк count1 и count2 одинаковые, значит мы нашли нужную подстроку
▫️При этом следим, чтобы размер "окна" совпадал с размером строки s1, поэтому удаляем левый символ, если размер стал больше
#solution567
Time: O(n)
Space: O(1)
📝 Идея
▫️Строка, которая является перестановкой другой строки имеет такое же количество символов, поэтому, перебирая вторую строку, сравниваем - если массивы строк count1 и count2 одинаковые, значит мы нашли нужную подстроку
▫️При этом следим, чтобы размер "окна" совпадал с размером строки s1, поэтому удаляем левый символ, если размер стал больше
#solution567
🔴 Hard
239. Sliding Window Maximum
Подсказка:для решения используйте deque - двустороннюю очередь
27/200
#hard
#leetcode239
239. Sliding Window Maximum
Подсказка:
27/200
#hard
#leetcode239
✅ Решение задачи 239
Time: O(n)
Space: O(k)
📝 Идея
▫️ В dq храним индексы массива и на каждом шаге делаем следующее:
1. Если первый элемент в очереди выходит за пределы "окна" - удаляем его
2. Удаляем верхний элемент очереди, пока он меньше текущего
▫️Таким образом первый элемент в dq — всегда индекс самого большого элемента в текущем окне
#solution239
Time: O(n)
Space: O(k)
📝 Идея
▫️ В dq храним индексы массива и на каждом шаге делаем следующее:
1. Если первый элемент в очереди выходит за пределы "окна" - удаляем его
2. Удаляем верхний элемент очереди, пока он меньше текущего
▫️Таким образом первый элемент в dq — всегда индекс самого большого элемента в текущем окне
#solution239
Базовая задача, решение, как всегда, оказалось простым, но необходимо понять его принцип.
Он обязательно пригодится для решения задач на различных контестах, а кому-то может попасться похожая задача на собеседовании
Он обязательно пригодится для решения задач на различных контестах, а кому-то может попасться похожая задача на собеседовании
🔴 Hard
76. Minimum Window Substring
Подсказка:расширяйте правый указатель, пока не будут покрыты все символы строки t, затем левым указателем сузьте "окно"
28/200
#hard
#leetcode76
76. Minimum Window Substring
Подсказка:
28/200
#hard
#leetcode76
✅ Решение задачи 76
Time: O(n)
Space: O(1)
📝 Идея
▫️ С помощью правого указателя находим окно, в котором содержатся все символы из строки t, далее левым указателем сужаем окно для минимального ответа
▫️Эффективно искать минимальное окно нам помогает массив, в котором мы храним частоту символов
#solution76
Time: O(n)
Space: O(1)
📝 Идея
▫️ С помощью правого указателя находим окно, в котором содержатся все символы из строки t, далее левым указателем сужаем окно для минимального ответа
▫️Эффективно искать минимальное окно нам помогает массив, в котором мы храним частоту символов
#solution76
🟢 Easy
206. Reverse Linked List
Класс ListNode:
Подсказка:сохраняйте предыдущий и следующий узел
29/200
#easy
#leetcode206
206. Reverse Linked List
Класс ListNode:
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;
}
}Подсказка:
29/200
#easy
#leetcode206
✅ Решение задачи 206
Time: O(n)
Space: O(1)
📝 Идея
1️⃣ Итеративный способ
▫️На каждом шаге делаем следующее:
- Сохраняем следующий узел
- Для текущего узла ссылка теперь будет не на следующий, а на предыдущий узел
- Меняем переменную prev на текущий узел, так как теперь он будет предыдущим для следующего
- Переходим на следующий узел
2️⃣ Рекурсивный способ
▫️Реализовывается вся та же логика, что и в итеративном способе: необходимо заменить ссылку на следующий узел ссылкой на предыдущий, перед этим сохраняем следующий узел, чтобы сделать то же самое дальше
#solution206
Time: O(n)
Space: O(1)
📝 Идея
1️⃣ Итеративный способ
▫️На каждом шаге делаем следующее:
- Сохраняем следующий узел
- Для текущего узла ссылка теперь будет не на следующий, а на предыдущий узел
- Меняем переменную prev на текущий узел, так как теперь он будет предыдущим для следующего
- Переходим на следующий узел
2️⃣ Рекурсивный способ
▫️Реализовывается вся та же логика, что и в итеративном способе: необходимо заменить ссылку на следующий узел ссылкой на предыдущий, перед этим сохраняем следующий узел, чтобы сделать то же самое дальше
#solution206