Implémentation JavaScript de l'algorithme des flaques d'eau Twitter example_javascript skills

J'ai trouvé aujourd'hui une question d'algorithme très intéressante. Voici la description de son algorithme, qui est dérivée d'une question d'interview sur Twitter.

Description de l'algorithme des flaques d'eau Twitter

Regardez d'abord une photo

Les nombres dans l'image 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 enfin un mur sera généré, quand. s'il pleut, ce mur peut être installé Combien d'eau, en unités de 1.

Voici à quoi ressemble un mur après l'avoir rempli d'eau

Après avoir lu l'image ci-dessus, je la trouve très intéressante. En effet, analysons brièvement la mise en œuvre de son algorithme

.

En fait, ce principe est relativement simple. Il y a au total quelques points clés :

1. Les côtés les plus à gauche et à droite ne doivent pas être remplis d'eau
2. La hauteur de remplissage d'eau dépend du minimum des deux valeurs maximales des côtés gauche et droit

Ci-dessous, nous utilisons js pour l'implémenter simplement :

Copier le code Le code est le suivant :

/**
* Calculez la quantité d'eau qu'un mur avec l'élément du tableau peut contenir en hauteur
* Exemple de tableau [2,5,1,2,3,4,7,7,6,9]
**/
fonction getWaterCounts(arg){
var je = 0,
        j = 0,
Compte = 0 ;
// Le premier et le dernier élément doivent être exclus
pour(je = 1; je < arg.length - 1; je ){
      var left = Math.max.apply(null, arg.slice(0, i 1));
      var right = Math.max.apply(null, arg.slice(i, arg.length));
        var min = gauche >= droite ? : gauche ;
              // La plus petite des valeurs maximales sur les côtés gauche et droit prévaudra
​​​​ //Si la valeur actuelle est supérieure ou égale à cette valeur, ne faites rien
           if(arg[i] < min){
Nombre = min - arg[i];
>
>
console.log(count);
>
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

Résumé

Hé, la mise en œuvre est assez simple, en fait, tant que vous êtes prêt à réfléchir, vous pouvez réaliser beaucoup de choses amusantes avec js.