Постановка задачи:

Для целочисленного массива nums вернуть ответ массива, такой, что ответ[i] равен произведению всех элементов nums, кроме nums[i].

Произведение любого префикса или суффикса чисел гарантированно вписывается в 32-битное целое число.

Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.

Пример 1:

• Ввод: числа = [1,2,3,4]
• Выход: [24,12,8,6]

Пример 2:

• Ввод: числа = [-1,1,0,-3,3]
• Выход: [0,0,9,0,0]

Ограничения:

• 2
• -30
• Произведение любого префикса или суффикса чисел гарантированно вписывается в 32-битное целое число.

Следовать за:

Можете ли вы решить задачу со сложностью дополнительного пространства O(1)? (Выходной массив не считается дополнительным пространством для анализа сложности пространства.)

Первоначальный мыслительный процесс:

Чтобы решить эту проблему, нам нужно вычислить произведение всех элементов, кроме текущего, без использования операции деления. Это можно сделать, используя два прохода по массиву:

1. Вычислите префиксные продукты для каждого элемента.
2. Вычислите суффиксные произведения для каждого элемента и умножьте на префиксные произведения.

Основное решение:

Мы можем использовать два массива для хранения продуктов префикса и суффикса, а затем умножить их, чтобы получить окончательный результат.

Код:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i = 0; i--) {
        suffixProducts[i] = suffixProducts[i   1] * nums[i   1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i 




  
  
  Анализ временной сложности:

• Временная сложность: O(n), где n — длина массива. Мы перебираем массив три раза.
• Пространственная сложность: O(n), для хранения продуктов префикса и суффикса.

Ограничения:

Базовое решение работает хорошо, но требует дополнительного места для хранения префиксных и суффиксных продуктов.

Оптимизированное решение:

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

Код:

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i = 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

Анализ временной сложности:

• Временная сложность: O(n), где n — длина массива. Мы дважды перебираем массив.
• Пространственная сложность: O(1), поскольку мы используем выходной массив для хранения промежуточных результатов и не используем дополнительное пространство.

Улучшения по сравнению с базовым решением:

• Оптимизированное решение снижает сложность пространства до O(1) за счет использования выходного массива для промежуточных результатов.

Краевые случаи и тестирование:

Краевые случаи:

1. Массив содержит нули.
2. Массив содержит отрицательные числа.
3. Длина массива равна минимальному (2) или максимальному (10^5) пределу.

Тестовые случаи:

console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

Общие стратегии решения проблем:

1. Понимание проблемы: Внимательно прочтите формулировку проблемы, чтобы понять требования и ограничения.
2. Определите ключевые операции: Определите необходимые ключевые операции, такие как вычисление префиксных и суффиксных продуктов.
3. Оптимизируйте читаемость: Используйте четкую и краткую логику, чтобы код было легко понять.
4. Тщательное тестирование: Проверьте решение в различных случаях, включая крайние случаи, чтобы убедиться в правильности.

Выявление подобных проблем:

1. Массив сумм префиксов:

   • Задачи, при которых необходимо вычислить суммы префиксов для запросов диапазона.
   • Пример: запрос суммы диапазона.

2. Алгоритмы на месте:

   • Проблемы, при которых операции необходимо выполнять на месте с ограниченным дополнительным пространством.
   • Пример: поворот массива вправо на k шагов.

3. Манипуляции с массивами:

   • Проблемы, при которых необходимо изменить массивы в зависимости от конкретных условий.
   • Пример: переместить нули в конец массива.

Заключение:

• Проблему вычисления произведения массива, кроме self, можно эффективно решить, используя как базовый подход с дополнительным пространством, так и оптимизированный подход на месте.
• Очень важно понять проблему и разбить ее на управляемые части.
• Использование четкой логики и оптимизация для удобства чтения гарантируют легкость понимания решения.
• Тестирование с различными крайними случаями обеспечивает надежность.
• Распознавание закономерностей в проблемах может помочь применить аналогичные решения к другим проблемам.

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