🟡Medium
1497. Check If Array Pairs Are Divisible by k

📝Дан массив целых чисел четной длины n и целое число k.

Верните true, если можно разделить массив ровно на n / 2 пары так, чтобы сумма каждой делилась на k

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

180/200
#leetcode1497 | #medium

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

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

⚡️ Идея
▫составим массив частот freq остатков от деления на k:
➖проходим по массиву и для каждого числа вычисляем остаток от деления на k, при этом используем запись (num % k + k) % k, чтобы предотварить отрицательные значения

▫проходим по freq и, поскольку пар необходимо n / 2, то количество остатков i должно быть столько же, сколько и остатков k - i, поэтому возвращаем false, если условие нарушено

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

Для примера 1:

[1 2 3 4 5 10 6 7 8 9] — исходный массив
[1 2 3 4 0 0 1 2 3 4] — остатки от деления на k
[2 2 2 2 2] — массив частот остатков

#solution1497

🟢Easy
1427. Perform String Shifts

📝 Вам дана строка s и матрица shift, где shift[i] = [d, c]

▫d — это направление: 0 для сдвига влево, 1 для сдвига вправо
▫c — это величина, на которую должна быть смещена строка

Верните окончательную строку после всех операций

💡: посчитайте общий сдвиг, пройдя по всей матрице shift

181/200
#leetcode1427 | #easy #premium

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

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

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

▫затем находим для него остаток от деления на длину строки n для обработки случая, когда сдвиг превышает n

▫в зависимости от знака total делаем следующее:
➖если total > 0 — выполняем сдвиг total элементов вправо, вернув строку, как [n - total, n) + [0, n - total)
➖если total < 0 — выполняем сдвиг total элементов влево, поменяв знак у total и вернув строку, как [-total, n) + [0, -total)
➖иначе — возвращаем исходную строку

#solution1427

🟡Medium
983. Minimum Cost For Tickets

📝Дан массив days, представляющий собой номера дней поездки.

Есть три варианта проездных:
➖1-дневный продается за costs[0]
➖7-дневный продается за costs[1]
➖30-дневный продается за costs[2]

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

💡: используйте динамическое программирование, для каждого дня от 1 до max выбирая минимум из вариантов проезда

182/200
#leetcode983 | #medium

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

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

⚡️ Идея
🟦инициализируем массив dp размером последнего дня поездки и указатель t=0 на текущий день

🟦далее проходим по dp, начиная с единицы:
➖ если текущее значение меньше текущего дня поездки, значит в этот день ехать не нужно и стоимость будет как в предыдущий день: dp[i] = dp[i - 1]

➖иначе увеличиваем t и для dp[i] выбираем минимум из 3 вариантов:
▫покупаем 1-дневный проездной и добавляем его стоимость к значению dp предыдущего дня: dp[i - 1]
▫покупаем 7-дневный проездной и добавляем его стоимость к значению dp за 7 дней до этого: dp[i - 7]
▫покупаем 30-дневный проездной и добавляем его стоимость к значению dp за 30 дней до этого: dp[i - 30]

🟦в итоге в dp[lastDay] получаем минимальную стоимость всей поздки

#solution983

🟡Medium
767. Reorganize String

📝Дана строка, переставьте ее символы так, чтобы любые два соседних не были одинаковыми.

Верните любую возможную перестановку или верните "", если это невозможно

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

183/200
#leetcode767 | #medium

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

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

⚡️ Идея
▫в начале составляем массив частот символов count и сохраняем самый частый; если его частота больше половины длины строки — возвращаем ""

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

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

▫в конце с помощью String.valueOf(res) превращаем массив в строку ответа

Пример алгоритма для строки s = "bfrbs":
после max: b_b__
далее: b_b_f -> brb_f -> brbsf

#solution767

🟢Easy
1351. Count Negative Numbers in a Sorted Matrix

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

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

💡: используйте указатель на отрицательные элементы и перемещайте его на каждой строке

184/200
#leetcode1351 | #easy

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