🖼Иллюстрация к решению задачи 3404

Расстановка и передвижение указателей (p, q, r, s)

#figure #array #hash

🔴Hard
2488. Count Subarrays With Median K

Company: 🔍

📝Вам дан массив размером n, состоящий из различных целых чисел от 1 до n, и положительное число k.

Верните количество непустых подмассивов, медиана которых равна k.

Медиана массива — это средний элемент после сортировки массива по возрастанию. Если массив имеет четную длину, медианой является левый средний элемент.

Например:

медиана [2,3,1,4] — 2
медиана [8,4,3,5,1] — 4

💡: ведите переменную баланса, которую будете увеличивать, если текущий элемент больше k и уменьшать, если меньше

#leetcode2488 | #hard #array #hash

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

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

💡 Идея
➖инициализируем переменную balance, которая показывает соотношение элементов относительно k:
▫balance < 0 — элементов меньше k больше
▫balance > 0 — элементов больше k больше
▫balance == 0 — равное количество

➖проходим по массиву и на каждом шаге обновляем balance, сохраняя в HashMap его количество, пока не наткнулись на k

➖как только встретили k, начинаем считать количество подмассивов, складывая из HashMap:
▫количество текущего balance, что позволит составить подмассив с медианой k
▫количество balance - 1, учитывая случай, когда длина подмассива четная

📎Логика после нахождения ķ:

➖Если в HashMap содержится текущее значение balance, значит мы можем отбросить часть массива, которая дала такое значение, чтобы получить balance = 0, то есть подмассив с медианой k ровно посередине

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

👩‍💻 Java Algo | #solution2488

🔴Hard
1224. Maximum Equal Frequency

Company: 🔍

📝Дан целочисленный массив.

Вернуть максимально возможную длину префикса, где после удаления ровно одного элемента все оставшиеся встречаются одинаковое количество раз

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

#leetcode1224 | #hard #array #hash

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

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

💡 Идея

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

🟦инициализируем две HashMap: для частоты элементов и количества чисел с такой частотой

🟦проходим по массиву и на каждом шаге:
➖заполняем обе HashMap

➖вычисляем длину подмассива, который можно составить из частоты текущего элемента и количества чисел с такой частотой, перемножая эти два значения, а затем сравниваем ее с длиной префикса от начала:

▫если получили равную длину, значит можно добавить любой элемент справа и обновить результат, как длину префикса + 1
▫если получили длину на 1 меньше, значит в подмассиве есть элемент с частотой 1 и можно обновить результат, как текущую длину префикса

👩‍💻 Java Algo | #solution1224

➡️ Стартуем тему двух указателей

#twopointers

🟢Easy
1089. Duplicate Zeros

Company: 📱📱🚖

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

Элементы, выходящие за пределы длины исходного массива, не сохраняются.
Необходимо выполнить данные действия на месте, без дополнительной памяти

💡: найдите позицию конца массива после удвоения нулей

#leetcode1089 | #easy #twopointers

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

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

💡 Идея
➖инициализируем указатели l — для прохода по массиву и r — для обозначения конца массива после удвоения нулей, а также end, который указывает на конец всех удвоений

➖первым проходом по массиву передвигаем r влево, если встретили 0

➖при этом, если l и r указывают на один и тот же элемент, равный 0 — ставим 0 в конец массива и уменьшаем end, так как при удвоении данного элемента, второй 0 не влезет в размер массива и нам не нужно его учитывать

➖далее проходим массив с end до 0 указателем i и смотрим на элементы под указателем r:
▫если равен 0, удваиваем его, копируя в i и i - 1
▫если не равен 0, просто копируем в i

👩‍💻 Java Algo | #solution1089

🟢Easy
541. Reverse String II

Company: 📱🔍📱

📝Даны строка s и целое число k. Поделите всю строку на части размером 2k и для каждой переверните первые k символов

💡: преобразуйте строку в массив символов

#leetcode541 | #easy #twopointers

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

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

💡 Идея
➖в начале преобразуем строку в массив символов с помощью s.toCharArray()

➖проходим по массиву указателем part с шагом 2k и для каждой такой части:

▫устанавливаем левый указатель в начало текущей части — part, а правый выбираем, как минимум из последнего индекса строки и (part + k - 1), обрабатывая возможный выход за пределы

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

➖в конце возвращаем ответ, преобразуя массив обратно в строку c помощью new String(arr)

👩‍💻 Java Algo | #solution541

🟢Easy
27. Remove Element

Company: 🔍🚖❤️

📝Дан массив целых чисел nums и целое число val. Вернуть количество элементов, которые не равны val.

При этом измените массив nums так, чтобы первые k элементов были не равны val, остальные элементы не важны, порядок может быть любой.

💡: пропускайте передвижение одного из указателей, если встретили элемент, равный val

#leetcode27 | #easy #twopointers

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

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

💡 Идея
➖инициализируем переменную j = 0, которая будет показывать куда записывать элементы, не равные val, и count для подсчета их количества

➖проходим по массиву и, если текущий элемент не равен val:
▫записываем его в позицию j
▫увеличиваем j и count

➖в конце возвращаем count, при этом исходный массив изменен по условию

👩‍💻 Java Algo | #solution27

🟢Easy
925. Long Pressed Name

Company: 📱🔍

📝Ваш друг печатает name на клавиатуре. Иногда при наборе клавиша может залипать и символ будет напечатан 1 или более раз.

Верните true, если возможно, что typed — это попытка набрать name с возможным залипанием клавиш

💡: проверьте свой алгоритм на примере: name = "leelee", typed = "lleeelee" и учтите все возможные краевые случаи

#leetcode925 | #easy #twopointers

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

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

💡 Идея
➖инициализируем указатели i и j на начала name и typed, соответственно

➖проходим по строкам:

🟦если текущие символы на позициях i и j совпадают, и при этом i ещё не достиг конца строки name, увеличиваем оба указателя
🟦если символы не совпадают, но текущий символ в typed равен предыдущему, передвигаем указатель j, учитывая возможное залипание
🟦в любом другом случае сразу возвращаем false

➖выражение "i < конца строки" name в первом условии позволяет учесть случай, когда залип последний символ в typed (то есть будет двигаться только указатель j)

➖в конце возвращаем true, только если i равен концу строки, учитывая случай, когда в typed оказалось меньше символов

👩‍💻 Java Algo | #solution925

🟡Medium
151. Reverse Words in a String

Company: 📱🏢💳

📝Дана строка s, верните обратный порядок слов, соединенных только одним пробелом

💡: проходите строку с конца, не забывая обрабатывать множественные пробелы

#leetcode151 | #medium #twopointers

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

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

💡 Идея
🟦инициализируем StringBuilder res для сохранения ответа и проходим строку с конца указателем i:

➖внутренним циклом уменьшаем i, пока текущий символ равен пробелу. Если прошли всю строку – сразу выходим из цикла

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

➖после того, как нашли границы – добавляем слово в результат с помощью res.append(s, j + 1, i + 1) и добавляем пробел, а затем обновляем индекс i, как (j – 1) для поиска следующего слова

🟦в конце возвращаем результат, приводя его к строке и убирая лишний пробел в конце: res.toString().trim()

👩‍💻 Java Algo | #solution151

🟡Medium
2337. Move Pieces to Obtain a String

Company: 🔍📱📱

📝Даны две строки start и target одинаковой длины n, состоящие из символов 'L', 'R' и '_'. Строки представляют собой поле, в котором:

▫символ 'L' обозначает фигуру, которая может двигаться только влево, если там есть пустое пространство
▫символ 'R' обозначает фигуру, которая может двигаться только вправо, если там есть пустое пространство
▫символ '_' обозначает пустое пространство, которое может быть занято любой из фигур

Верните true, если возможно получить строку target, перемещая фигуры строки start любое количество раз

💡: пропускайте все пустые пространства, сравнивая только позиции фигур в двух строках

#leetcode2337 | #medium #twopointers

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

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

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

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

🟪далее делаем основную проверку, возвращая false, если:
➡️текущие символы в строках не равны, то есть последовательность L и R в строках неодинаковая
➡️текущий символ равен ‘L’ и его позиция в строке start меньше, чем в строке target, то есть он не сможет туда попасть, так как не может двигаться вправо
➡️текущий символ равен ‘R’ и его позиция в строке start больше, чем в строке target, то есть он не сможет туда попасть, так как не может двигаться влево

🟪если все условия прошли, увеличиваем оба указателя

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

👩‍💻 Java Algo | #solution2337

🟡Medium
80. Remove Duplicates from Sorted Array II

Company: 🪄📱❤️

📝Дан массив nums, отсортированный в неубывающем порядке.
Измените его так, чтобы первые k элементов составляли массив, в котором каждый элемент встречается не более двух раз. Относительный порядок элементов должен остаться прежним.

Необходимо решить задачу без использования дополнительной памяти и вернуть k в качестве ответа

💡: поддерживайте счетчик одинаковых элементов

#leetcode80 | #medium #twopointers

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

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

💡 Идея
➖инициализируем переменные l и r на первый элемент и счетчик одинаковых элементов count

➖проходим по массиву указателем r:

▫если текущий элемент равен предыдущему, увеличиваем count, иначе ставим значение 1
▫если count <= 2, копируем текущий элемент в позицию l и увеличиваем ее (то есть, если count > 2, текущий элемент просто пропускается)

➖таким образом в позиции l всегда записываются не более двух одинаковых элементов и можно вернуть конечное значение l, как ответ

👩‍💻 Java Algo | #solution80

🟡Medium
1229. Meeting Scheduler

Company: 📱🚖📱

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

Гарантируется, что никакие два слота доступности одного и того же человека не пересекаются друг с другом

💡: вычисляйте общий промежуток времени для текущих слотов

#leetcode1229 | #medium #premium #twopointers