Leetcode Challenge #3

Привет! Сегодня мы закончим последнюю часть Two pointers.

Сегодняшние задачи

Сегодняшняя тема: Two pointers.

Здесь 2 задачи на работу со строками и 2 задачи на связный список.

344. Обратная строка

Это простая обратная задача. Просто установите 2 указателя в начале и в конце одновременно, поменяйте значения в указателях местами, а затем переместите их внутрь. Повторяйте процесс, пока left >= right.

Сложность составляет O(n) времени и O(1) дополнительного места.

ПРИМЕЧАНИЕ: Проблема заключалась в том, что требовалось выполнить обратное преобразование на месте, в то время как JavaScript не поддерживает манипуляции со строками на месте. Поэтому leetcode посылает массив char в качестве входных данных. Очень мило!

577. Обратный перевод слов в строке III

Для этой задачи не требуется обратный ход на месте, поэтому пришло время воспользоваться возможностями языка высокого уровня. LOL!
Потребуется всего одна строка. Комбо split+join — мощный инструмент для работы со строками. Используйте его вместе с map для работы с каждым сегментом.

return s.split(' ').map(x => x.split('').reverse().join('')).join(' ');

Сложность составляет O(n) времени и O(n) дополнительного пространства.

ПРИМЕЧАНИЕ: O(1) дополнительного пространства в данной задаче невозможно, так как задача требует возврата новой строки вместо массива char. А JS не поддерживает манипуляцию строками на месте.

876. Середина связного списка

Простым решением является однократный итерационный просмотр связанного списка для получения длины. И повторить итерацию для половины длины, чтобы получить середину.

Другое решение — поддерживать два указателя, оба из которых начинаются с головы. На каждой итерации указатель A перемещается на 2 шага, а указатель B — на 1 шаг. Таким образом, когда указатель A достигнет конца, указатель B окажется в середине связного списка.

Оба решения занимают O(n) времени и O(1) дополнительного места.

19. Удаление N-го узла из конца списка

Как и в предыдущей задаче, простым решением будет сначала подсчитать длину. И повторить итерацию, чтобы получить n-й узел из конца.

Другой способ — установить указатель A в начале и установить указатель B на n шагов вперед. Затем переместить их оба одновременно, в то время как указатель B достигает конца, указатель A находится в n-ом узле от конца.

Оба решения занимают O(n) времени и O(1) дополнительного места.

ПРИМЕЧАНИЕ: Для второго решения будьте осторожны с некоторыми особыми случаями, такими как: удаление первого элемента (поэтому мы должны вернуть второй элемент в качестве head вместо удаленного head).

Дополнительная проблема

Я забыл установить фильтр tag:two pointers, поэтому дополнительная проблема не связана с двумя указателями.

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

Начинаем со старшего правого разряда, складываем их, записываем сумму по модулю и переносим, повторяем процесс в следующем разряде.

Есть еще два момента, с которыми нужно обращаться аккуратно. Числа могут быть разной длины, и не забудьте добавить последний перенос.

Сложность составляет O(n) времени и O(n) пространства.

Заключение

Сегодняшние 5 задач проще, чем в прошлый раз. На их решение ушло всего около 50 минут.
В следующий раз будет 3 средних задачи. Надеюсь, вам будет интереснее читать.

<— Предыдущая | Главная | Следующая —>