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

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

⚡️ Идея
▫инициализируем указатель ind на последний столбец матрицы

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

▫используем это и, проходя по строкам матрицы, на каждой:
➖перемещаем указатель влево, пока под ним находится отрицательный элемент
➖добавляем к результату количество отрицательных элементов, как (m - 1) - ind

#solution1351

🟡Medium
31. Next Permutation

📝Дан массив целых чисел nums, верните его следующую перестановку за O(1) по памяти.

Например, для arr = [1, 2, 3] все перестановки по порядку:

[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

💡: найдите позицию с конца, где nums[i] < nums[i + 1] и делайте перестановку, используя подмассив справа от неё

185/200
#leetcode31 | #medium

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