🟡Medium
274. H-Index

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

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

💡: используйте подсчет количества цитирований для решения за O(n)

158/200
#leetcode274 | #medium

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

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

⚡️ Идея
▫инициализируем переменную max, как максимальный возможный h-индекс, который равен длине заданного массива
▫для подсчета количества цитирований используем массив count размером max + 1
▫далее проходимся по заданному массиву и увеличиваем в count количество статей с текущим значением цитирования. При этом если значение больше max, кладем его по индексу max, так как h-индекс не может быть больше длины заданного массива
▫затем проходим по массиву count, начиная с max, и суммируем текущее количество цитирований: если оно стало больше или равно текущему индексу, значит возвращаем данный индекс в качестве ответа

#solution274

🟡Medium
328. Odd Even Linked List

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

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

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

💡: одновременно передвигайте два указателя — на четную и нечетную группы

159/200
#leetcode328 | #medium

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

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

⚡️ Идея
▫сохраним указатель на начало четной группы и проинициализируем указатели для прохода по списку на 1-ый и 2-ой узел
▫проходимся по списку, пока четный указатель и его следующий узел не null:
➖для обоих указателей меняем ссылку на следующий узел — ссылкой через один и передвигаем их на новую позицию
▫в конце для нечетного указателя следующим узлом делаем сохраненный указатель на начало четной группы и возвращаем начало нового списка

#solution328

🟡Medium
221. Maximal Square

📝Дана матрица, заполненная символами '0' и '1', найти наибольший квадрат, содержащий только '1', и вернуть его площадь

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

160/200
#leetcode221 | #medium

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

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

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

#solution221

🟢Easy
605. Can Place Flowers

📝 Дан целочисленный массив, содержащий 0 и 1, где 0 означает пустое место, 1 — посаженный цветок, а также целое число n.
Вернуть true, если можно посадить n цветов так, чтобы никакие два не находились рядом

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

161/200
#leetcode605 | #easy

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

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

⚡️ Идея
▫проходим данный массив и используем две переменные для проверки свободных мест слева и справа:
➖emptyL — true, если текущий элемент нулевой или значение слева равно 0
➖emptyR — true, если текущий индекс последний или значение справа равно 0
▫если обе переменные true и текущий элемент равен 0, значит здесь можно посадить цветок:
➖текущий элемент делаем 1 и уменьшаем переменную n
▫в конце возвращаем true, если n <= 0

#solution605

🟡Medium
1657. Determine if Two Strings Are Close

📝Даны две строки, вернуть true, если они близкие.

Две строки считаются близкими, если одну из другой можно получить с помощью следующих операций:
➖поменять местами любые два символа
➖поменять местами все вхождения двух символов. Например, все 'a' превращаются в 'b', а все 'b' превращаются в 'a':

"aacabb" —> "bbcbaa"

Можно использовать операции над любой строкой столько раз, сколько необходимо

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

162/200
#leetcode1657 | #medium

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

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

⚡️ Идея
▫формируем массив частот символов длиной 26 для двух строк и заполняем его
▫далее проходим по двум массивам и проверяем — существует ли текущий символ в обоих строках, если нет — возвращаем false
▫так как мы можем использовать операции любое количество раз, необходимо только проверить, что
частоты символов в двух строках совпадают, поэтому возвращаем true, если массивы идентичны после сортировки
▫сортировка выполняется за 26(log26), что сводится к O(1), поэтому общая сложность алгоритма O(n)

#solution1657

🟡Medium
962. Maximum Width Ramp

📝Дан целочисленный массив, вернуть максимальную ширину рампы.

Рампа в целочисленном массиве nums — это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такой рампы равна j - i

💡: используйте монотонный стек

163/200
#leetcode962 | #medium

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

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

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

#solution962

🟡Medium
539. Minimum Time Difference

📝Дан список точек времени в 24-часовом формате «ЧЧ:ММ», вернуть минимальную разницу в минутах между любыми двумя точками

💡: используйте массив размером 24 * 60 для сортировки

164/200
#leetcode539 | #medium

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

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

⚡️ Идея
▫инициализируем массив размером 24 * 60 и проходим по каждой точке времени, переводя ее в общее количество минут и отмечая в массиве соответствующую ячейку как true
▫затем проходим по этому массиву и, если текущее значение true:
➖ сохраняем первый индекс, если он не сохранен
➖ считаем минимальную разницу, используя указатель на предыдущий индекс
➖ сохраняем текущий индекс в предыдущий и последний
▫В конце считаем разницу между первым и последним индексом и возвращаем минимальный ответ

#solution539

🟡Medium
916. Word Subsets

📝Вам даны два строковых массива words1 и words2. Верните лист всех универсальных строк в words1.

▫Строка A из words1 — универсальная, если каждая строка B из words2 является подмножеством строки A.
▫Строка B является подмножеством строки A, если каждая буква B встречается в A, включая кратность
▫Например, "eo" является подмножеством "google", но не является подмножеством "apple"

💡: сформируйте общее слово из words2, используя массив частот символов

165/200
#leetcode916 | #medium

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

Time: O(N + M)
Space: O(1)

⚡️ Идея
▫проходим по words2 и составляем общую строку, которая имеет максимальное количество каждой буквы каждого слова из words2:
➖для каждого слова формируем свой массив частот с помощью функции count, а затем перемещаем его в общий массив, выбирая максимум из текущих частот букв
▫далее проходим по words1 и для каждого слова также формируем массив частот символов, а затем сравниваем этот массив с полученным массивом общего слова из words2, используя функцию check:
➖функция проверяет, что для каждого символа из B найдется такое же или большее количество символов в A
▫если текущая строка из words1 прошла проверку — добавляем ее в результат

#solution916

🟢Easy
408. Valid Word Abbreviation

📝Дана строка word и аббревиатура abbr, вернуть true, если строка соответствует заданной аббревиатуре

Строку можно сократить, заменив любое количество непустых подстрок их длинами, при этом длины не должны иметь начальных нулей. Например:

"substitution" -> "s10n"
"substitution" -> "sub4u4"
"substitution" -> "12"

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

166/200
#leetcode408 | #easy #premium

✅ Решение задачи 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