Declaração do problema:

Dado um array inteiro nums, retorne uma resposta de array tal que resposta[i] seja igual ao produto de todos os elementos de nums, exceto nums[i].

É garantido que o produto de qualquer prefixo ou sufixo de nums caiba em um número inteiro de 32 bits.

Você deve escrever um algoritmo que seja executado em tempo O(n) e sem usar a operação de divisão.

Exemplo 1:

• Entrada: números = [1,2,3,4]
• Saída: [24,12,8,6]

Exemplo 2:

• Entrada: números = [-1,1,0,-3,3]
• Saída: [0,0,9,0,0]

Restrições:

• 2
• -30
• É garantido que o produto de qualquer prefixo ou sufixo de nums caiba em um número inteiro de 32 bits.

Seguir:

Você pode resolver o problema de complexidade de espaço extra O(1)? (A matriz de saída não conta como espaço extra para análise de complexidade de espaço.)

Processo de pensamento inicial:

Para resolver este problema, precisamos calcular o produto de todos os elementos, exceto o elemento atual, sem usar a operação de divisão. Isso pode ser feito usando duas passagens pelo array:

1. Calcule os produtos de prefixo para cada elemento.
2. Calcule os produtos de sufixo para cada elemento e multiplique pelos produtos de prefixo.

Solução Básica:

Podemos usar dois arrays para armazenar os produtos de prefixo e sufixo e depois multiplicá-los para obter o resultado final.

Código:

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 




  
  
  Análise de complexidade de tempo:

• Complexidade de tempo: O(n), onde n é o comprimento da matriz. Iteramos pelo array três vezes.
• Complexidade espacial: O(n), para armazenar os produtos de prefixo e sufixo.

Limitações:

A solução básica funciona bem, mas usa espaço extra para armazenar produtos com prefixo e sufixo.

Solução otimizada:

Podemos otimizar a solução para usar espaço extra O(1) usando a matriz de saída para armazenar produtos de prefixo primeiro e depois modificá-la no local para incluir os produtos de sufixo.

Código:

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;
}

Análise de complexidade de tempo:

• Complexidade de tempo: O(n), onde n é o comprimento da matriz. Iteramos pelo array duas vezes.
• Complexidade do espaço: O(1), pois estamos usando o array de saída para armazenar resultados intermediários e não usando nenhum espaço adicional.

Melhorias em relação à solução básica:

• A solução otimizada reduz a complexidade do espaço para O(1) usando a matriz de saída para resultados intermediários.

Casos extremos e testes:

Casos extremos:

1. A matriz contém zero(s).
2. A matriz contém números negativos.
3. O comprimento da matriz é o limite mínimo (2) ou máximo (10^5).

Casos de teste:

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]

Estratégias gerais de resolução de problemas:

1. Entenda o problema: Leia atentamente a declaração do problema para entender os requisitos e restrições.
2. Identificar as principais operações: Determine as principais operações necessárias, como produtos de prefixo e sufixo de computação.
3. Otimizar para legibilidade: Use uma lógica clara e concisa para garantir que o código seja fácil de seguir.
4. Teste Completamente: Teste a solução com vários casos, incluindo casos extremos, para garantir a correção.

Identificando problemas semelhantes:

1. Matriz de soma de prefixos:

   • Problemas em que você precisa calcular somas de prefixos para consultas de intervalo.
   • Exemplo: consulta de soma de intervalo.

2. Algoritmos no local:

   • Problemas em que as operações precisam ser realizadas em local com espaço extra limitado.
   • Exemplo: girar uma matriz para a direita em k etapas.

3. Manipulação de matriz:

   • Problemas em que você precisa modificar matrizes com base em condições específicas.
   • Exemplo: mover zeros para o final de uma matriz.

Conclusão:

• O problema de calcular o produto de uma matriz, exceto o próprio, pode ser resolvido de forma eficiente usando uma abordagem básica com espaço extra e uma abordagem otimizada no local.
• Compreender o problema e dividi-lo em partes gerenciáveis ​​é crucial.
• Usar uma lógica clara e otimizar a legibilidade garante que a solução seja fácil de seguir.
• Testes com vários casos extremos garantem robustez.
• Reconhecer padrões em problemas pode ajudar a aplicar soluções semelhantes a outros desafios.

Ao praticar esses problemas e estratégias, você pode melhorar suas habilidades de resolução de problemas e estar mais bem preparado para vários desafios de codificação.