2270. Número de maneiras de dividir a matriz

dificuldade: Medium

tópicos: Array, prefixo sum

você recebe um 0-Indexed Integer Array nums de comprimento n.

nums contém um válido Split no índice I Se os seguintes são verdadeiros:

• A soma dos primeiros elementos i 1 é maior ou igual a a soma dos últimos n - i - 1 elementos.
• existe pelo menos um elemento à direita de i. Isto é, 0

retornar o número de válido Splits em nums .

Exemplo 1:

• entrada: nums = [10,4, -8,7]
• output: 2
• Explicação: Existem três maneiras de dividir os nums em duas partes não vazias:
  • Split nums no índice 0. Então, a primeira parte é [10], e sua soma é 10. A segunda parte é [4, -8,7], e sua soma é 3. Desde 10> = 3, i = 0 é uma divisão válida.
  • Split nums no índice 1. Então, a primeira parte é [10,4] e sua soma é 14. A segunda parte é [-8,7], e sua soma é -1. Desde 14> = -1, i = 1 é uma divisão válida.
  • Split nums no índice 2. Então, a primeira parte é [10,4, -8], e sua soma é 6. A segunda parte é [7], e sua soma é 7. Como 6
  • Assim, o número de divisões válidas no NUMS é 2.

Exemplo 2:

• entrada: nums = [2,3,1,0]
• output: 2
• Explicação: Existem duas divisões válidas no NUMS:
  • Split nums no índice 1. Então, a primeira parte é [2,3], e sua soma é 5. A segunda parte é [1,0], e sua soma é 1. Desde 5> = 1, i = 1 é uma divisão válida.
  • Split nums no índice 2. Então, a primeira parte é [2,3,1] e sua soma é 6. A segunda parte é [0], e sua soma é 0. Desde 6> = 0, i = 2 é uma divisão válida.

restrições:

]
• -10 ⁵ 5
• Dica:

Para qualquer índice I, como podemos encontrar a soma dos primeiros (i 1) elementos da soma dos primeiros elementos I?

Se a soma total da matriz for conhecida, como podemos verificar se a soma dos primeiros (i 1) elementos maiores ou iguais aos elementos restantes?

2. Solução:

podemos abordá -lo usando as seguintes etapas: Abordagem:

prefixo sum

: primeiro, calculamos a soma cumulativa da matriz da esquerda, o que ajuda a verificar a soma dos primeiros elementos i 1.

1. soma total : Calcule a soma total da matriz, que é útil na verificação se a soma dos elementos restantes for menor ou igual à soma dos primeiros elementos i 1.
2. iterar sobre a matriz : Para cada índice válido i (onde 0
3. eficiência : em vez de recalcular as somas repetidamente, use a soma do prefixo e a soma total para comparações eficientes.
4. Vamos implementar esta solução em php: 2270. Número de maneiras de dividir a matriz

Php /** * @param inteiro [] $ nums * @return inteiro */ função waystosplitarray ($ nums) { ... ... ... /** * vá para ./solution.php */ } // Exemplo de uso: $ nums1 = [10, 4, -8, 7]; eco waystosplitarray ($ nums1); // saída: 2 $ nums2 = [2, 3, 1, 0]; eco waystosplitarray ($ nums2); // saída: 2 ?>
Explicação:

$ Totalsum

: Esta variável armazena a soma de todos os elementos na Array Nums.

1. $ prefixsum : Esta variável acompanha a soma cumulativa de elementos da esquerda (até o índice i).
2. $ RESTERINGING : Esta é a soma dos elementos restantes do índice I 1 ao final da matriz. É calculado subtraindo $ prefixum de $ Totalsum.
3. válido split check : Para cada índice I, verificamos se a soma do prefixo é maior ou igual à soma restante.
4. Complexidade do tempo:

O (n)

: Largamos através da matriz uma vez para calcular a soma e mais uma vez para verificar se há divisões válidas. Portanto, a complexidade do tempo é linear em relação ao comprimento da matriz.

• Complexidade espacial:

o (1)

: estamos usando apenas algumas variáveis ​​extras ($ totsum, $ prefixsum, $ restante), então a complexidade do espaço é constante.

• Contato Links

Se você achou essa série útil, considere dar o repositório uma estrela no github ou compartilhar a postagem em suas redes sociais favoritas?. Seu apoio significaria muito para mim!

Se você quiser um conteúdo mais útil como este, fique à vontade para me seguir:

Linkedin

• github