Aujourd'hui, j'ai trouvé une question d'algorithme très intéressante. Ce qui suit est sa description d'algorithme, qui provient d'une question d'interview sur Twitter.
Description de l'algorithme Twitter Puddles
Regardez d'abord une image
Les nombres de la figure ci-dessus sont décrits en fonction du contenu d'un tableau. Enfin, la hauteur d'un mur sera simulée en fonction de la taille de chaque nombre, et un mur sera généré. Demandez-vous, quand il pleut, combien d'eau peut être rempli cette paroi, en 1 comme unité de comptage.
Voici un mur après avoir rempli l'eau
Après avoir lu l'image ci-dessus, pensez-vous que c'est amusant? En effet, analysons brièvement sa mise en œuvre de son algorithme ci-dessous.
En fait, ce principe est relativement simple, il y a quelques points clés:
1. Il n'y a certainement pas d'eau sur les côtés gauche et droit
2. La hauteur de la charge d'eau dépend de la valeur minimale des deux valeurs maximales sur les côtés gauche et droit de soi
Utilisons JS pour l'implémenter simplement:
La copie de code est la suivante:
/ **
* Calculez la quantité d'eau peut être installée sur le mur avec des termes de tableau comme hauteur
* Exemple de tableau [2,5,1,2,3,4,7,7,6,9]
** /
fonction getWaterCounts (arg) {
var i = 0,
J = 0,
count = 0;
// Les deux et les derniers éléments doivent être exclus
for (i = 1; i <arg.length - 1; i ++) {
var left = math.max.apply (null, arg.slice (0, i + 1));
var droite = math.max.apply (null, arg.slice (i, arg.length));
var min = gauche> = droit? Droite: à gauche;
// La valeur maximale des côtés gauche et droite doit prévaloir
// Si la valeur actuelle est supérieure ou égale à cette valeur, ne faites rien
if (arg [i] <min) {
Count + = min - arg [i];
}
}
console.log (count);
}
GetwaterCounts ([2,5,1,2,3,4,7,7,6,9]); // 11
Résumer
Hehe, la mise en œuvre n'est-elle pas assez simple? En fait, tant que vous êtes prêt à penser, vous pouvez utiliser JS pour mettre en œuvre de nombreuses choses amusantes.