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

Пример:

head = [0, 2, 3, 3, 4]

#figure #listnode

🔴Hard
135. Candy

📝Дан массив ratings, где ratings[i] — рейтинг отдельного ребенка.

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

Верните минимально необходимое количество конфет

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

194/200
#leetcode135 | #hard

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

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

⚡️ Идея
🟦инициализируем массив count количества конфет для каждого ребенка и изначально заполним его единицами

🟦первым проходом слева направо по ratings гарантируем, что ребенок с большим рейтингом получит больше конфет, чем его сосед слева, сохраняя в count[i] значение +1 от левого

🟦вторым проходом с конца проверяем, что ребенок с большим рейтингом получит больше конфет, чем его сосед справа, при этом для count[i] выбираем максимум из текущего значения и (count[i + 1] + 1), чтобы сохранить правильное отношение с левым соседом

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

#solution135

🟡Medium
1590. Make Sum Divisible by P

📝Дан массив положительных целых чисел nums, удалите наименьший подмассив (возможно пустой) так, чтобы сумма оставшихся элементов делилась на p. Не допускается удаление всего массива.

Верните длину наименьшего подмассива, который необходимо удалить или -1, если это невозможно

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

195/200
#leetcode1590 | #medium

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

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

⚡️ Идея
▫в начале находим общую сумму массива, при этом после суммы каждого элемента считаем остаток от деления на p, так как число может превысить Integer.MAX_VALUE

▫затем вычисляем target, как остаток от деления всей суммы на p: target = totalSum % p, который определяет на сколько вся сумма отклоняется от числа, которое делится на p

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

▫проходим по всему массиву и для каждого элемента:
➖вычисляем текущую сумму по модулю p

➖считаем какую сумму нужно найти в HashMap, чтобы разница между текущей суммой и найденной была равна target: needed = (curr - target + p) % p, где +p гарантирует, что needed будет всегда положительный

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

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

#solution1590

🟢Easy
234. Palindrome Linked List

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

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

💡: разделите список на две части и переверните одну из них

196/200
#leetcode234 | #easy

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

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

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

🟦с помощью функции endOfFirst проходим по списку обычным slow и быстрым fast (переходит через один) указателями, получая в slow конец первой части

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

🟦далее проходим от начал первой и второй части и сравниваем значения в узлах, возвращая false, если они не равны

#solution234

🟡Medium
650. 2 Keys Keyboard

📝На экране есть только один символ 'A'. Вы можете выполнить одну из двух операций за один шаг:

1⃣скопировать все символы, представленные на экране (частичное копирование не допускается)
2⃣вставить символы, скопированные в прошлый раз

Для заданного целого числа n верните минимальное количество операций, необходимое для появления символа 'A' на экране n раз

💡: используйте динамическое программирования, считая для каждого числа от 2 до n минимальное количество операций

197/200
#leetcode650 | #medium

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

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

⚡️ Идея
🟦для решения создадим массив dp размером n+1 и изначально заполним его максимальным количеством операций

🟦проходим по числам от 2 до n и для каждого перебираем его делители j от 1 до i / 2:
➖если i делится на j, обновляем количество операций для i, как минимум из текущего значения dp[i] и количества операций для j (dp[j]) плюс одно копирование и необходимое количество вставок — (i / j)

🟦в результате в dp[n] получаем ответ

#solution650

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

Пример использования делителей j для i = 6

#figure #dp

🟡Medium
670. Maximum Swap

📝Дано целое число num. Вы можете поменять местами две цифры максимум один раз, чтобы получить наибольшее значение.

Верните максимально возможное число

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

198/200
#leetcode670 | #medium

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

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

⚡️ Идея
🟦в начале создадим символьный массив nums из цифр числа с помощью String.valueOf(num).toCharArray()

🟦далее создадим массив rightMax для хранения индексов самой большой цифры, которая находится справа от текущей и заполним его, двигаясь с конца nums:
➖если текущая цифра больше максимальной справа (nums[rightMax[i + 1]]), сохраняем текущий индекс
➖иначе дублируем значение из rightMax[i + 1]

🟦далее проходим от начала nums и, если текущая цифра меньше, чем цифра в позиции rightMax[i], меняем их местами и сразу возвращаем ответ, как Integer.parseInt(new String(nums))

#solution670

🟢Easy
1752. Check if Array Is Sorted and Rotated

📝Дан массив, вернуть true, если он был изначально отсортирован в неубывающем порядке, а затем повернут на некоторое количество позиций (включая ноль)

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

199/200
#leetcode1752 | #easy

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

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

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

🟦если нашли точку поворота, после прохода проверяем, что последний элемент меньше или равен нулевому

🟦если поворота не было, значит массив изначально отсортирован, и можно просто вернуть true

#solution1752

🟡Medium
2364. Count Number of Bad Pairs

📝Дан целочисленный массив nums. Пара индексов (i, j) является " плохой", если i < j и j - i != nums[j] - nums[i].

Верните общее количество "плохих" пар

💡: преобразуйте выражение в nums[i] - i != nums[j] - j и используйте HashMap для подсчета "хороших" пар

200/200
#leetcode2364 | #medium

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

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

⚡️ Идея
🟦Используем факт, что число "плохих" пар равно общему количеству пар минус число "хороших"

🟦Хорошими являются те, для которых выполняется выражение nums[i] - i == nums[j] - j, то есть достаточно сохранять в HashMap nums[i] - i, а затем сравнивать с текущей разницей

🟦Проходим по массиву и для каждого шага:
➖считаем текущую разницу diff = nums[i] - i
➖находим количество хороших пар goodPairs, обращаясь к HashMap по ключу diff
➖считаем плохие пары, добавляя i - goodPairs, то есть количество всех пар до i минус хорошие пары
➖обновляем HashMap, увеличивая значение для diff

#solution2364

➡️ Стартуем тему массивов и Хэш-таблиц #array #hash

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

🟢Easy
1331. Rank Transform of an Array

Company: 📱🔍

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

Ранг показывает, насколько велик элемент и имеет следующие правила:
➖начинается с 1
➖чем больше элемент, тем больше ранг. Если два элемента равны, их ранги должны быть одинаковыми
➖ранг должен быть как можно меньше

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

#leetcode1331 | #easy #array #hash

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

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

💡 Идея
➖создадим клон массива и отсортируем его

➖проходим по новому массиву и сохраняем в HashMap [sortArr[i] — rank], при этом ранг увеличиваем только, если текущий элемент больше предыдущего

➖в конце обновляем исходный массив, заменяя элементы на их ранги, взятые из значений HashMap

👩‍💻 Java Algo | #solution1331

🟢Easy
219. Contains Duplicate II

Company: 🔍📱❤️

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

Вернуть true, если в массиве есть два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k

💡: поддерживайте set размером k

#leetcode219 | #easy #array #hash