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

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

⚡️ Идея
▫проходим по строке word и аббревиатуре abbr с помощью двух указателей — i и j:
➖если текущий символ abbr цифра и не ноль — запускаем цикл с передвижением указателя j и записью всего числа, а затем передвигаем указатель i на соответствующее значение
➖если текущие символы равны, передвигаем оба указателя
➖иначе возвращаем false (символы не равны или число в abbr начинается с 0)
▫в конце возвращаем true, если оба указателя соответствуют длинам своих строк

#solution408

🟡Medium
2149. Rearrange Array Elements by Sign

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

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

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

167/200
#leetcode2149 | #medium

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

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

⚡️ Идея
▫инициализируем массив для ответа и два указателя — на положительные и отрицательные числа: pos = 0, neg = 1
▫далее проходим по массиву и сохраняем текущее число в массив, используя соответствующий указатель в зависимости от знака числа, а затем увеличиваем этот указатель на две позиции вперед
▫В результате получаем массив, который чередуется по знакам с сохранением исходного порядка

#solution2149

🟡Medium
2657. Find the Prefix Common Array of Two Arrays

📝 Даны два целочисленных массива A и B, вернуть их общий префиксный массив.

Общий префиксный массив A и B — это массив C, в котором C[i] равен количеству чисел, которые присутствуют в обоих массивах от 0 до i (включительно)

Для примера 2:

i = 0: ни одно число не является общим, поэтому C[0] = 0
i = 1: только 3 является общим для A и B, поэтому C[1] = 1
i = 2: 1, 2 и 3 являются общими A и B, поэтому C[2] = 3

💡: используйте HashSet

168/200
#leetcode2657 | #medium

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

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

⚡️ Идея
▫проходим по массивам и последовательно проверяем элементы A и B:
➖если в Set содержится текущий элемент массива, увеличиваем ячейку результата, а затем добавляем этот элемент в Set
▫после проверок суммируем текущую ячейку результата с предыдущей

#solution2657

🟢Easy
938. Range Sum of BST

📝Дано бинарное дерево поиска и два целых числа — low и high, вернуть сумму всех узлов со значениями в диапазоне [low, high]

💡: используйте свойство дерева

169/200
#leetcode938 | #easy

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

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

⚡️ Идея
▫так как в бинарном дереве поиска все элементы слева от текущего узла меньше, а справа больше — используем это свойство при обходе дерева с помощью вспомогательной функции:
➖суммируем к результату текущее значение, если оно находится в диапазоне
➖текущее значение > low — суммируем к результату рекурсивный вызов функции с левым поддеревом
➖текущее значение < high — суммируем к результату рекурсивный вызов функции с правым поддеревом
▫в результате, вызвав из основной функции вспомогательную с корнем дерева, получаем сумму всех узлов со значениями в заданном диапазоне

#solution938

🔴Hard
220. Contains Duplicate III

📝Вам дан массив целых чисел nums и два целых числа — indexDiff и valueDiff.

Найдите пару индексов (i, j), такую ​​что:

➖ i != j
➖ abs(i - j) <= indexDiff
➖ abs(nums[i] - nums[j]) <= valueDiff

Верните true, если такая пара существует

💡: используйте bucket sort, где bucket будет формироваться как [элемент массива / (valueDiff + 1)]

170/200
#leetcode220 | #hard

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

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

⚡️ Идея
▫для решения задачи используем bucket sort, где bucket будет формироваться как nums[i] / (valueDiff + 1) c округлением вниз, чтобы обработать отрицательные элементы

▫проблема, которую нужно решить — это проверка для элемента x наличия в текущем окне длиной indexDiff значения в диапазоне [x - valueDiff, x + valueDiff]

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

▫возвращаем true, если разность между элементом из bucket и текущим <= valueDiff или уже существует такой же bucket

▫добавляем (bucket, nums[i]) в HashMap и удаляем левый элемент из окна, если текущий индекс >= indexDiff

#solution220

🟡Medium
236. Lowest Common Ancestor of a Binary Tree

📝Дано бинарное дерево, найдите наименьшего общего предка для двух заданных узлов p и q (заданный узел также может являться предком)

💡: возвращайте некоторый флаг, если встретили p или q, обходя дерево в глубину

171/200
#leetcode236 | #medium

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

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

⚡️ Идея
▫реализуем функцию helper, которая проходит дерево в глубину и возвращает true, если поддерево содержит p или q

▫используем три переменные для отслеживания общего предка:
➖curr — отмечаем 1, если текущий узел равен p или q
➖left — отмечаем 1, если рекурсивный вызов функции для левого поддерева возвращает true
➖right — отмечаем 1, если рекурсивный вызов функции для правого поддерева возвращает true

▫если для текущего узла сумма трех переменных равна 2-м — значит мы нашли наименьшего общего предка

▫возвращаем true, если любая из трех переменных содержит p или q (их сумма больше 0)

#solution236

🟡Medium
275. H-Index II

📝Дан массив целых чисел citations, отсортированный по возрастанию, где citations[i] — количество цитирований, полученных исследователем для i-ой статьи.

Необходимо вернуть индекс Хирша исследователя с решением за O(logn) по времени

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

172/200
#leetcode275 | #medium

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

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

⚡️ Идея
▫реализуем бинарный поиск, в котором для перемещения указателей будем использовать на длину массива (n)

▫вычисляем mid, а затем сравниваем текущее значение цитирований с оставшимся количеством статей (n - mid) :
➖если цитирований больше — передвигаем правый указатель, пробуя увеличить индекс Хирша
➖если цитирований меньше — передвигаем левый указатель, рассматривая варианты справа

▫в конце возвращаем количество статей после левого указателя (n - l)

#solution275

🟡Medium
624. Maximum Distance in Arrays

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

Верните максимальное расстояние, как абсолютную разность |a - b|, выбрав два целых числа из двух разных массивов

💡: сначала считайте результат, а затем обновляйте минимум и максимум

173/200
#leetcode624 | #medium

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

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

⚡️ Идея
▫в начале проинициализируем минимум и максимум, используя нулевой массив из списка

▫далее проходим по всему списку массивов, начиная с первого, и на каждом шаге делаем следующее:
➖считаем текущий результат, используя максимальный и минимальный элемент из массива — |a[0] - max| и |a[last] - min|
➖обновляем текущий минимум и максимум

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

#solution624

🟡Medium
280. Wiggle Sort

📝Дан массив целых чисел nums, отсортируйте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Необходимо решить задачу за O(n) по времени

💡: используйте свойство четной и нечетной позиций относительно левого элемента

174/200
#leetcode280 | #medium #premium

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

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

⚡️ Идея
🟦заметим, что на выходе значения на нечетных позициях должны быть всегда больше значений слева, а на четных позициях меньше

🟦используем этот факт и, проходя по массиву, меняем местами текущий и элемент слева, если:
➖позиция нечетная и текущий элемент меньше левого
➖позиция четная и текущий элемент больше левого

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

#solution280

🟢Easy
350. Intersection of Two Arrays II

📝 Даны два целочисленных массива nums1 и nums2, вернуть массив их пересечение.

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

💡: используйте HashMap для массива меньшей длины

175/200
#leetcode350 | #easy

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

Time: O(n + m)
Space: O(min(n, m))

⚡️ Идея
🟦в начале выбираем меньший по длине массив, рекурсивно вызывая функцию, поменяв местами аргументы, если nums1 > nums2

🟦проходим по первому массиву и в HashMap формируем частоту элементов

🟦проходим по второму массиву и, если в HashMap частота текущего элемента больше нуля, ставим его в nums1[k], а затем увеличиваем k и уменьшаем частоту элемента

🟦в конце с помощью Arrays.copyOfRange(nums1, 0, k) возвращаем массив ответа от 0 до k (не включительно)

#solution350

🟡Medium
93. Restore IP Addresses

📝Дана строка, содержащая только цифры, вернуть все допустимые IP-адреса (в любом порядке), которые могут быть сформированы путем вставки точек.

Допустимый IP-адрес состоит ровно из четырех целых чисел, разделенных точками. Каждое целое число находится в диапазоне [0, 255] и не имеет ведущих нулей

💡: рассматривайте позиции точек, используя поход backtracking

176/200
#leetcode93 | #medium

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

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

⚡️ Идея
▫реализуем функцию backtrack для рассмотрения всех вариантов постановки точек

▫поскольку допустимый IP-адрес состоит из чисел в диапазоне [0, 255], можно рассматривать только три варианта постановки точки: после 1-ой, 2-ой и 3-ей цифры от текущей

▫поэтому для текущей позиции запускаем цикл на 3 вперед, составляя возможный вариант числа для IP-адреса и, если он подходит под условия, рекурсивно вызываем функцию backtrack, в которую передаем:
➖текущую позицию + 1
➖счетчик точек + 1
➖текущий IP-адрес, добавляя полученное число и точку
➖список результата

▫базовым случаем для функции будет являться количество точек, равное 4-м, и полностью пройденная строка, тогда добавляем текущий адрес в результат, убирая лишнюю точку в конце

#solution93