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

Time: O(V + E)
Space: O(V)

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

▫в основной функции инициализируем булевый массив visited посещеннных комнат, а затем вызываем dfs, передав его в функцию

▫далее проходим по visited и, если все значения в массиве true, значит можно посетить все комнаты

#solution841

🔴Hard
2302. Count Subarrays With Score Less Than K

📝Дан положительный целочисленный массив nums и целое число k, вернуть количество непустых подмассивов, оценка которых строго меньше k.

Оценка массива определяется, как произведение его суммы и его длины.

💡: используйте подход sliding window

189/200
#leetcode2302 | #hard

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

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

⚡️ Идея
▫используем подход sliding window:
➖добавляем в сумму текущий элемент под правым указателем

➖в цикле while пока произведение текущей суммы и длины подмассива больше k — передвигаем левый указатель, вычитая из суммы элементы под ним

➖затем добавляем к результату размер окна, считая тем самым все подходящие подмассивы

#solution2302

🟡Medium
1169. Invalid Transactions

📝Вам дан массив строк transactions, представляющих собой имя, время (в минутах), сумму и город транзакции.
Верните список недействительных транзакций.

Транзакция признается недействительной, если:
➖сумма превышает 1000
➖она происходит с разницей в 60 минут от другой транзакции с тем же именем, но в другом городе

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

190/200
#leetcode1169 | #medium

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

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

⚡️ Идея
▫предварительно реализуем класс Transaction

static class Transaction {
String name;
int time;
int amount;
String city;

public Transaction(String s) {
String[] data = s.split(",");
name = data[0];
time = Integer.parseInt(data[1]);
amount = Integer.parseInt(data[2]);
city = data[3];
}
}

▫проходим по заданному массиву с транзакциями и формируем HashMap [имя — список транзакций]

▫затем еще раз проходим по всем транзакциям и сохраняем текущую в ответ, если:
➖сумма превышает 1000 или после прохода по всем транзакциям от текущего имени нашли такую, для которой разница по времени <= 60, и она совершена в другом городе

#solution1169

🟢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