Почему я нарушаю лимит времени!? Цикл связанных списков LeetCode (решено, но необходимо объяснение!)

Я работаю над решением проблемы LeetCode 141. Цикл связанных списков:

Учитывая head, заголовок связанного списка, определите, есть ли в связанном списке цикл.

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

Верните true, если в связанном списке есть цикл. В противном случае верните false.

Пример 1:

Ввод: head = [3,2,0,-4], pos = 1
Вывод: true
Пояснение: В связанном списке есть цикл, хвост которого соединяется с узлом 1st (с индексом 0).

Мое исходное решение (версия A) превысило лимит времени, указанный выше. В конце концов мне удалось сделать решение достаточно быстрым, изменив две строки кода (Версия B), и решение было принято и в некотором смысле более эффективно.

Почему версия B быстрее, чем версия A? Почему назначение переменной происходит быстрее/эффективнее, чем использование исходного объекта?

Я изменил это...

Версия А (неудачное решение)

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = null;
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2
        fastPointer = head?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

к этому ...

Версия Б (Рабочее решение)

var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = head; // !!!CHANGE #1
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2 
        // !!!CHANGE #2 and solution worked!!!!
        fastPointer = fastPointer?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

На самом деле сейчас не самое подходящее время, чтобы спрашивать, поскольку вы можете тривиально добавить некоторую регистрацию в свои функции и профилировать, сколько ваших функций и циклов внутри ваших функций вызываются (и с какими значениями), чтобы вы могли выяснить, почему один набор инструкций занимает вечность, тогда как другой набор инструкций более эффективен. Сначала вам придется провести некоторую отладку самостоятельно.

Mike 'Pomax' Kamermans 25.04.2024 21:57
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
1
1
66
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

в первом решении, которое вы определяете

let fastPointer = null;

и затем вы делаете это:

fastPointer = fastPointer?.next?.next || null;

это означает, что вы пытаетесь переназначить переменную, а переменная уже равна нулю, это означает

fastPointer = null?.next?.next || null;

в первой опциональной цепочке оно уже равно нулю это означает следующее условие:

if (fastPointer === null)

истинно и вернет false, даже если у меня есть цикл и код не завершит выполнение

так что, по сути, это время не превышает "это сразу возвращает false...

Спрашивающий говорит, что они получают ошибку ограничения по времени. Почему вы настаиваете, что они этого не делают? Зачем им лгать об этом?

trincot 26.04.2024 00:14

@trincot Я сам запускаю код в leetcode, и у меня не было превышения времени

ziad-amer-1 26.04.2024 00:33

Я предполагаю, что вы не запускали код спрашивающего, в котором возникла проблема, или что вы не запускали проблемный тестовый пример, например, случай «пример 1» (который упоминает спрашивающий). Наверняка код спрашивающего попадает в бесконечный цикл и, следовательно, достигает тайм-аута.

trincot 26.04.2024 13:28
Ответ принят как подходящий

В ошибочной версии петля fastPointer опережает на два узла по сравнению с head. Но это означает, что fastPointer на самом деле не движется быстрее... он находится всего на два узла впереди, но движется с той же «скоростью», что и head. Что вам действительно нужно, так это то, чтобы fastPointer увеличивал свое преимущество на каждом шаге, чтобы fastPointer находился в связанном списке вдвое дальше, чем head, а не всего на 2 узла впереди.

Это также объясняет, почему первая версия достигает ограничения по времени: она попадает в бесконечный цикл, когда во входном списке есть цикл, и этот цикл имеет размер, отличный от 2. В этом случае fastPointer никогда не станет равным head, поскольку находится ровно в 2 узлах от head. Например, если в цикле 3 узла, то fastPointer будет на 2 узла впереди head и в конечном итоге (после прибытия в цикл) также на один узел позади head. Это никогда не изменится: это расстояние останется прежним, поэтому цикл никогда не закончится.

Другие вопросы по теме