Hoje eu encontrei uma pergunta de algoritmo muito interessante. A seguir, a descrição do algoritmo, que vem de uma pergunta de entrevista no Twitter.
Descrição do algoritmo do Twitter Puddles
Olhe para uma foto primeiro
Os números na figura acima são descritos de acordo com o conteúdo de uma matriz. Finalmente, a altura de uma parede será simulada de acordo com o tamanho de cada número, e uma parede será gerada. Pergunte a você, quando chover, quanta água essa parede pode ser preenchida, em 1 como a unidade de contagem.
Aqui está uma parede depois de encher a água
Depois de ler a foto acima, você acha que é divertido? De fato, vamos analisar brevemente sua implementação de algoritmo abaixo.
De fato, esse princípio é relativamente simples, existem alguns pontos -chave:
1. Definitivamente não há água nos lados esquerdo e direito
2. A altura da carga de água depende do valor mínimo dos dois valores máximos nos lados esquerdo e direito de si mesmo
Vamos usar o JS para implementá -lo simplesmente:
A cópia do código é a seguinte:
/**
* Calcule quanta água pode ser instalada na parede com termos de matriz como a altura
* Exemplo de matriz [2,5,1,2,3,4,7,7,6,9]
**/
função getwatercounts (arg) {
var i = 0,
j = 0,
contagem = 0;
// os primeiros e os últimos itens devem ser excluídos
for (i = 1; i <arg.length - 1; i ++) {
var esquerdo = math.max.apply (null, arg.slice (0, i + 1));
var à direita = math.max.apply (null, arg.slice (i, arg.length));
var min = esquerda> = certo? direita: esquerda;
// O valor máximo dos lados esquerdo e direito prevalecerá
// Se o valor atual for maior ou igual a esse valor, não faça nada
if (arg [i] <min) {
contagem += min - arg [i];
}
}
console.log (contagem);
}
getwaterCounts ([2,5,1,2,3,4,7,7,6,9]); // 11
Resumir
Hehe, a implementação não é muito simples? De fato, desde que você esteja disposto a pensar, você pode usar o JS para implementar muitas coisas divertidas.