🟢Easy
2423. Remove Letter To Equalize Frequency

📝Дана строка, верните true, если можно удалить в ней ровно одну букву так, чтобы частота всех букв была одинаковой

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

191/200
#leetcode2423 | #easy

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

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

⚡️ Идея
🟦реализуем функцию для проверки массива частот символов, которая возвращается true, если все значения в нем одинаковые

private boolean check(int[] count) {
int num = -1;
for (int c : count) {
if (c == 0) {
continue;
} else if (num == -1) {
num = c;
} else if (num == c) {
continue;
} else {
return false;
}
}
return true;
}

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

🟦далее проходим по count и, если символ встречается в строке (частота не равна 0), делаем следующее:
➖удаляем символ из строки, уменьшая его частоту
➖возвращаем true, если прошла проверка count c помощью функции check
➖добавляем символ обратно, увеличивая его частоту

🟦если дошли до конца, возвращаем false, так как условие выполнить не удалось

#solution2423

🟡Medium
2381. Shifting Letters II

📝Дана строка s строчных английских букв и двумерный массив сдвигов shifts, где shifts[i] = [start_i, end_i, dir_i], что означает сдвиг каждого символа от start до end (включительно) вперед, если dir = 1 и назад, если dir = 0.

Сдвиг символа вперед означает замену его на следующую букву в алфавите ('c' -> 'd', 'z' -> 'a'). Аналогично сдвиг символа назад.

Верните окончательную строку после применения всех сдвигов

💡: используйте массив, где будете отмечать только начало и конец сдвига соответствующими значениями

192/200
#leetcode2381| #medium

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

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

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

▫для текущего интервала отмечаем начало, добавляя в diff[start] — 1, если dir = 1 и -1, если dir = 0

▫но, так как далее мы будем использовать префиксную сумму, необходимо отметить и конец интервала, добавив в diff[end + 1] противоположное значение от старта, чтобы следующий отрезок остался неизменным

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

#solution2381

🟡Medium
82. Remove Duplicates from Sorted List II

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

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

193/200
#leetcode82 | #medium

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

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

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

▫проходим по списку пока текущий указатель head не null:
➖если следующий узел имеет такой же номер, как и текущий, перемещаем указатель, пока это условие верно, а затем
сохраняем ссылку на следующий элемент save, как head.next
➖иначе просто переходим на следующий узел save

▫в конце возвращаем start.next, то есть ссылку на ответ с новым списком

#solution82

🖼Иллюстрация алгоритма к задаче 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