Краткий обзор моего опыта использования Leetcode

Следующие сегменты этого сообщения в блоге будут служить каталогом моего опыта работы с проблемами leetcode. Все мои успехи и неудачи будут хорошо задокументированы, как и мои решения вопросов, которые я делаю. Это будет упорядочено по проблемам, как я их делаю, не обязательно так, как они устроены на платформе Leetcode.

Не стесняйтесь пропустить и проверить любые конкретные проблемы или решения по своему усмотрению. Цель этого — помочь мне лучше понять мыслительный процесс, связанный с решением проблем, путем подробного описания того, как я решил конкретную проблему. Для этого используется концепция техники Фейнмана. Там будут ответы на вопросы Leetcode, поэтому, если вы предпочитаете работать над ними самостоятельно, подумайте о том, чтобы пропустить вопросы, которые вам еще предстоит решить самостоятельно.

238. Произведение массива, кроме собственного

Ссылка на задачу здесь

Краткое содержание

Эта проблема немного сбивала меня с толку. Сразу признаюсь, что это я не решал самостоятельно, но я посмотрел немного видео из списка 150 NeetCode.

Как бы плохо это ни звучало, я понял концепцию и не копировал и не вставлял код. Я просмотрел его прекрасное наглядное объяснение, обработал его на бумаге, а затем, исходя из своего понимания, запрограммировал его в код. Цель этого не в том, чтобы быть совершенным, а в том, чтобы учиться по ходу дела. Если бы мое эго было слишком велико, я бы просто не стал пытаться решить эту проблему с самого начала, а просто отправился бы искать ту, которую ЗНАЛ, что смогу решить, чтобы поддержать это эго. Однако в разделе Первоначальные мысли вы увидите ход моих мыслей до того, как я посмотрел объяснение.

Первоначальные мысли

Моя первоначальная мысль, касающаяся этой проблемы, заключалась в том, что я мог бы использовать встроенную функцию сокращения Javascript для исходного массива, зафиксировать ее для каждого элемента и вернуть это. Однако я быстро понял, что, несмотря на то, что это функция O(n), использование ее для каждого элемента таким образом означало, что я перебирал ее n*n раз. Это нарушило условия задания.

Тут я начал заморачиваться. Я понятия не имел, как мне перебрать весь массив менее чем за n² раз. Именно тогда я решил искать руководство, а не искать решение.

Объяснение

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

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

Поскольку первый индекс не имеет префикса, его «префикс» по умолчанию равен 1, поскольку он ищет продукт, а не сумму. Тогда префикс второго индекса равен префиксу первого индекса * самому первому индексу . Это продолжается до тех пор, пока вы не дойдете до последнего элемента.

var productExceptSelf = function(nums) {
    let temp = [];
    let prefix = 1;
    let postfix = 1;

//Populate temp with nums's prefixes
    for(i = 0; i < nums.length; i++){
        temp.push(prefix);
        prefix *= nums[i];
    }
//Get postfix and multiply it to its corresponding prefix
    for(j = nums.length-1; j >= 0; j--){
        temp[j] *= postfix;
        postfix *= nums[j];
    }

    return temp;
};