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

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

⚡️ Идея
▫отметим, что для любой последовательности в порядке убывания следующая перестановка невозможна (как для [3, 2, 1])

▫проходим массив с конца и находим положение, где nums[i] < nums[i + 1], это значит, что для подмассива справа от i перестановка невозможна, так как он находится в порядке убывания

▫теперь, для создания перестановки необходимо поменять местами nums[i] и следующее минимально большее число после него

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

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

#solution31

🟢Easy
859. Buddy Strings

📝Даны две строки s и goal, верните true, если можно поменять местами две буквы в s так, чтобы результат был равен goal

💡: найдите 2 индекса, где символы в строках не совпадают

186/200
#leetcode859 | #easy

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

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

⚡️ Идея
▫в начале проверим один из краевых случаев:
➖строки идентичны — возвращаем true, если в s содержатся повторяющиеся символы, иначе false

▫строку s можно превратить в goal с помощью одной перестановки, если только два символа в строках отличаются, поэтому инициализируем два указателя, как -1 и проходим по строкам:
➖нашли 1-е несовпадение — сохраняем позицию в первый указатель
➖нашли 2-е несовпадение — сохраняем позицию во второй указатель
➖если различий больше — сразу возвращаем false

▫далее проверяем, что несовпадений ровно 2 (второй указатель не равен -1) и возвращаем true, если символы в строках s и goal равны по разным указателям, то есть перестановка в s даст goal

#solution859

🟡Medium
71. Simplify Path

📝 Вам дан абсолютный путь для файловой системы в стиле Unix, который всегда начинается с косой черты '/'. Преобразуйте этот абсолютный путь в упрощенный.

Правила файловой системы в стиле Unix:
▫ '.' — представляет текущий каталог
▫ '..' — обозначает предыдущий каталог
▫несколько последовательных слешей (например '//' или '///') рассматриваются, как один слеш '/'
▫любая последовательность точек, которая не соответствует правилам выше, рассматривается, как допустимое имя каталога

Правила упрощенного пути:
▫путь должен начинаться с одного слеша '/'
▫каталоги в пути должны быть разделены ровно одним слешем '/'
▫путь не должен заканчиваться слешем '/', если это не корневой каталог
▫путь не должен содержать одинарных или двойных точек

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

187/200
#leetcode71 | #medium

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

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

⚡️ Идея
▫инициализируем стек и массив директорий, разделив входную строку пути, используя path.split("/")

▫далее проходим по каждой директории:
➖если она пустая или равна ".", пропускаем ее
➖если она равна "..", переходим на один уровень наверх, то есть убираем последний элемент из стека
➖иначе добавляем ее в стек

▫после обработки собираем все директории из стека в ответ с помощью StringBuilder, добавляя разделитель "/" перед каждой и, если путь получился пустым, возвращаем "/"

#solution71

🟡Medium
841. Keys and Rooms

📝 Дан массив rooms, где rooms[i] — набор ключей, которые можно получить, посетив комнату i.
Верните true, если можно посетить все комнаты, начав с нулевой.

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

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

188/200
#leetcode841 | #medium

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