Heute fand ich eine sehr interessante Algorithmusfrage. Das Folgende ist die Beschreibung der Algorithmus, die aus einer Interviewfrage auf Twitter stammt.
Twitter Puddles Algorithmus Beschreibung
Schauen Sie sich zuerst ein Bild an
Die Zahlen in der obigen Abbildung werden gemäß dem Inhalt eines Arrays beschrieben. Schließlich wird die Höhe einer Wand gemäß der Größe jeder Zahl simuliert und eine Wand erzeugt. Fragen Sie Sie, wenn es regnet, wie viel Wasser in 1 als Zähleinheit mit dieser Wand gefüllt werden kann.
Hier ist eine Wand nach dem Füllen des Wassers
Haben Sie nach dem Lesen des obigen Bildes das Gefühl, dass es Spaß macht? Lassen Sie uns in der Tat kurz seine Algorithmus -Implementierung analysieren.
Tatsächlich ist dieses Prinzip relativ einfach, es gibt einige wichtige Punkte:
1. Es gibt definitiv kein Wasser auf der linken und rechten Seite
2. Die Höhe der Wasserbelastung hängt vom Mindestwert der beiden maximalen Werte auf der linken und rechten Seite der sich selbst ab
Verwenden wir JS, um es einfach zu implementieren:
Die Codekopie lautet wie folgt:
/**
* Berechnen Sie, wie viel Wasser an der Wand mit Array -Begriffen als Höhe installiert werden kann
* Array -Beispiel [2,5,1,2,3,4,7,7,6,9]
**//
Funktion GetWaterCounts (arg) {
var i = 0,
J = 0,
count = 0;
// Sowohl die ersten als auch die letzten Artikel müssen ausgeschlossen werden
für (i = 1; i <arg.length - 1; i ++) {
var links = math.max.apply (null, arg.lice (0, i + 1));
var right = math.max.apply (null, arg.slice (i, arg.length));
var min = links> = rechts? rechts: links;
// Der Maximalwert der linken und rechten Seite muss sich durchsetzen
// Wenn der aktuelle Wert größer oder gleich diesem Wert ist, tun Sie nichts
if (arg [i] <min) {
count += min - arg [i];
}
}
console.log (count);
}
GetWaterCounts ([2,5,1,2,3,4,7,7,6,9]); // 11
Zusammenfassen
Hehe, ist die Implementierung nicht einfach? Solange Sie bereit sind zu denken, können Sie JS verwenden, um viele lustige Dinge zu implementieren.