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

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

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

⚡️ Идея
🟦Используем факт, что число "плохих" пар равно общему количеству пар минус число "хороших"

🟦Хорошими являются те, для которых выполняется выражение nums[i] - i == nums[j] - j, то есть достаточно сохранять в HashMap nums[i] - i, а затем сравнивать с текущей разницей

🟦Проходим по массиву и для каждого шага:
➖считаем текущую разницу diff = nums[i] - i
➖находим количество хороших пар goodPairs, обращаясь к HashMap по ключу diff
➖считаем плохие пары, добавляя i - goodPairs, то есть количество всех пар до i минус хорошие пары
➖обновляем HashMap, увеличивая значение для diff

#solution2364

➡️ Стартуем тему массивов и Хэш-таблиц #array #hash

К каждой задаче теперь добавляется соответствующий тег, а также компании, где недавно ее спрашивали на собеседовании

🟢Easy
1331. Rank Transform of an Array

Company: 📱🔍

📝Дан массив целых чисел, замените каждый элемент его рангом.

Ранг показывает, насколько велик элемент и имеет следующие правила:
➖начинается с 1
➖чем больше элемент, тем больше ранг. Если два элемента равны, их ранги должны быть одинаковыми
➖ранг должен быть как можно меньше

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

#leetcode1331 | #easy #array #hash

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

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

💡 Идея
➖создадим клон массива и отсортируем его

➖проходим по новому массиву и сохраняем в HashMap [sortArr[i] — rank], при этом ранг увеличиваем только, если текущий элемент больше предыдущего

➖в конце обновляем исходный массив, заменяя элементы на их ранги, взятые из значений HashMap

👩‍💻 Java Algo | #solution1331

🟢Easy
219. Contains Duplicate II

Company: 🔍📱❤️

📝Дан массив целых чисел nums и целое число k.

Вернуть true, если в массиве есть два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k

💡: поддерживайте set размером k

#leetcode219 | #easy #array #hash

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

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

💡 Идея
➖используем HashSet, который будем поддерживать размером k, чтобы при обнаружении одинаковых элементов точно знать, что они находятся на нужном расстоянии

➖проходим по массиву:
▫если текущий элемент содержится в set, возвращаем true
▫добавляем текущий элемент в set
▫если размер set больше k, удаляем самый левый элемент (nums[i - k])

➖в конце возвращаем false, так как массив полностью пройден и подходящих элементов не нашлось

📎В комментариях код с использованием HashMap

👩‍💻 Java Algo | #solution219

🟡Medium
532. K-diff Pairs in an Array

Company: 🔍📱🚖

📝Дан массив целых чисел nums и целое число k, верните количество уникальных пар k-diff в массиве.

Пара k-diff — это пара (nums[i], nums[j]), для которой верны следующие условия:
➖0 <= i, j < nums.length
➖i != j
➖abs(nums[i] - nums[j]) == k

💡: для поиска уникальных пар перебирайте ключи HashMap

#leetcode532 | #medium #array #hash

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

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

💡 Идея
🟦создадим и заполним HashMap частот, которая хранит уникальные элементы в качестве ключей и количество их появлений в массиве в качестве значений

🟦затем перебираем ключи HashMap:

▫если k > 0, проверяем наличие в хэш-карте (k + key). Используя только сложение, мы исключаем возможность появления дубликатов, то есть если мы нашли пару (1,3), мы не будем учитывать (3,1)

▫если k == 0, необходимо проверить, что количество появлений в массиве текущего элемента больше 1, тогда при вычитании одинаковых элементов можно получить 0

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

👩‍💻 Java Algo | #solution532

🟡Medium
1711. Count Good Meals

Company: 🔍

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

Вернуть результат по модулю (10⁹ + 7)

Ограничения:

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

💡: для каждого элемента примените идею TwoSum, где target будет равен всем степеням двойки из условия

#leetcode1711 | #medium #array #hash

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

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

💡 Идея
➖поскольку по условию значения элементов массива не превосходят 2²⁰, задача сводится к поиску пар чисел, сумма которых является степенью двойки

➖проходим по всем элементам массива и для каждого:
▫перебираем все степени двойки (target) от 0 до 21, так как максимально возможная сумма двух элементов (2²⁰ + 2²⁰) не превысит 2²¹

▫если в HashMap содержится (target - num), добавляем в результат значение по данному ключу, тем самым учитывая все возможные варианты составления пар

▫делим текущий результат по модулю на (10⁹ + 7), чтобы избежать переполнения и выполнить условие

▫после проверки всех степеней двойки для текущего элемента — добавляем его в HashMap, увеличивая значение на 1

👩‍💻 Java Algo | #solution1711

🟡Medium
3185. Count Pairs That Form a Complete Day II

Company: 📱

📝Дан целочисленный массив hours, представляющий время в часах, вернуть количество пар (i, j), где i < j и hours[i] + hours[j] образуют полный день.

Полный день определяется как продолжительность времени, кратная 24 часам

💡: для текущего элемента ищите необходимый остаток, чтобы дополнить его до числа кратного 24

#leetcode3185 | #medium #array #hash

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

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

💡 Идея
➖инициализируем массив count, в котором будем хранить количество остатков от деления на 24

➖проходим по массиву и для каждого элемента:
▫вычисляем необходимый остаток, чтобы в сумме получить число кратное 24, то есть ищем значение (24 - num % 24) и дополнительно берем его по модулю 24, чтобы обработать случай, когда num кратно 24

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

▫увеличиваем ячейку count для текущего элемента по модулю 24

👩‍💻 Java Algo | #solution3185

🟡Medium
3371. Identify the Largest Outlier in an Array

Company: 📱🔍

📝Вам дан массив целых чисел, который содержит n элементов, где ровно (n - 2) элементов — это специальные числа . Один из оставшихся двух элементов — это сумма специальных чисел, а другой — выброс.

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

Верните наибольший выброс из массива

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

#leetcode3371 | #medium #array #hash

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

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

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

➖затем проходим по ключам HashMap и каждый проверяем на возможный выброс:
▫вычисляем сумму check, как общую без текущего элемента

▫обновляем результат, если сумма check четная и выполняется одно из условий:
1⃣половина check равна текущему элементу и элемент встречается больше 1-го раза
2⃣половина check отличается от текущего элемента и в HashMap существует данный ключ

👩‍💻 Java Algo | #solution3371