Zählen Sie Server, die kommunizieren

1267. Zählen Sie Server, die kommunizieren

Schwierigkeit:Mittel

Themen: Array, Tiefensuche, Breitensuche, Unionssuche, Matrix, Zählen

Sie erhalten eine Karte eines Serverzentrums, dargestellt als m * n-Ganzzahlmatrixgitter, wobei 1 bedeutet, dass sich in dieser Zelle ein Server befindet, und 0 bedeutet, dass es sich nicht um einen Server handelt. Zwei Server sollen kommunizieren, wenn sie sich in derselben Zeile oder derselben Spalte befinden.

Gibt die Anzahl der Server zurück, die mit einem anderen Server kommunizieren.

Beispiel 1:

• Eingabe: Gitter = [[1,0],[0,1]]
• Ausgabe: 0
• Erklärung:Kein Server kann mit anderen kommunizieren.

Beispiel 2:

• Eingabe: Gitter = [[1,0],[1,1]]
• Ausgabe: 3
• Erklärung:Alle drei Server können mit mindestens einem anderen Server kommunizieren.

Beispiel 3:

• Eingabe: Gitter = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1] ]
• Ausgabe: 4
• Erklärung: Die beiden Server in der ersten Reihe können miteinander kommunizieren. Die beiden Server in der dritten Spalte können miteinander kommunizieren. Der Server in der rechten unteren Ecke kann mit keinem anderen Server kommunizieren.

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 1
• 1
• grid[i][j] == 0 oder 1

Hinweis:

1. Speichern Sie die Anzahl der Computer in jeder Zeile und Spalte.
2. Zählt alle Server, die nicht isoliert sind.

Lösung:

Wir folgen diesen Schritten:

Ansatz:

1. Server in jeder Zeile und Spalte zählen:

   • Durchqueren Sie das Raster und berechnen Sie, wie viele Server in jeder Zeile und jeder Spalte vorhanden sind. Dies kann mithilfe der beiden Arrays rowCount und colCount erfolgen, wobei:
     • rowCount[i] speichert die Anzahl der Server in Zeile i.
     • colCount[j] speichert die Anzahl der Server in Spalte j.

2. Überprüfen Sie die Kommunikation:

   • Überprüfen Sie für jeden Server im Raster, ob er mit einem anderen Server kommunizieren kann, indem Sie rowCount und colCount überprüfen. Wenn einer davon größer als 1 ist, kann der Server mit anderen kommunizieren.

3. Zählen Sie die Server, die kommunizieren:

   • Durchsuchen Sie das Raster erneut und prüfen Sie für jeden Server (Zelle mit Wert 1), ob er zu einer Zeile oder Spalte gehört, in der es mehr als einen Server gibt.

Lassen Sie uns diese Lösung in PHP implementieren: 1267. Zählen Sie Server, die kommunizieren

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function countServers($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function with the provided examples
$grid1 = [[1, 0], [0, 1]];
$grid2 = [[1, 0], [1, 1]];
$grid3 = [[1, 1, 0, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1]];

echo countServers($grid1) . "\n"; // Output: 0
echo countServers($grid2) . "\n"; // Output: 3
echo countServers($grid3) . "\n"; // Output: 4
?>

Erläuterung:

1. Server in Zeilen und Spalten zählen:

   • Wir durchlaufen das Raster und zählen, wie viele Server (d. h. 1) sich in jeder Zeile und jeder Spalte befinden. Wir speichern diese Zählungen in den Arrays rowCount und colCount.

2. Kommunikationsserver identifizieren:

   • Nach dem Zählen iterieren wir über jeden Server (Zelle mit Wert 1). Ein Server kann mit anderen kommunizieren, wenn die Anzahl der Server in seiner Zeile (rowCount[i] > 1) oder die Anzahl der Server in seiner Spalte (colCount[j] > 1) größer als 1 ist. Anschließend erhöhen wir das Ergebnis Zähler für jeden kommunizierenden Server.

3. Ausgabe:

   • Die Funktion gibt die Gesamtzahl der Server zurück, die mit anderen Servern kommunizieren können.

Zeitkomplexität:

• O(m * n), wobei m die Anzahl der Zeilen und n die Anzahl der Spalten ist. Dies liegt daran, dass wir das Raster zweimal durchlaufen: einmal, um Server in Zeilen und Spalten zu zählen, und einmal, um die Kommunikation zu überprüfen.

Diese Lösung löst das Problem effizient innerhalb der gegebenen Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonZählen Sie Server, die kommunizieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!