Привет! Сегодня мы закончим последнюю часть Two pointers
.
Сегодняшние задачи
Сегодняшняя тема: Two pointers
.
ID | Имя | Трудность | Проблема | Решение |
---|---|---|---|---|
344 | Обратная строка | легко | ссылка | ссылка |
557 | Реверс слов в строке III | легко | ссылка | ссылка |
876 | Середина связного списка | легко | ссылка | ссылка |
19 | Удаление N-го узла из конца списка | средний | ссылка | ссылка |
Здесь 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).
Дополнительная проблема
ID | Имя | Трудность | Проблема | Решение |
---|---|---|---|---|
2 | Сложите два числа | средний | ссылка | ссылка |
Я забыл установить фильтр tag:two pointers
, поэтому дополнительная проблема не связана с двумя указателями.
Проблема заключается в простой реализации целочисленного сложения так, как нас учили в начальной школе.
Начинаем со старшего правого разряда, складываем их, записываем сумму по модулю и переносим, повторяем процесс в следующем разряде.
Есть еще два момента, с которыми нужно обращаться аккуратно. Числа могут быть разной длины, и не забудьте добавить последний перенос.
Сложность составляет O(n) времени и O(n) пространства.
Заключение
Сегодняшние 5 задач проще, чем в прошлый раз. На их решение ушло всего около 50 минут.
В следующий раз будет 3 средних задачи. Надеюсь, вам будет интереснее читать.
<— Предыдущая | Главная | Следующая —>