Compter les serveurs qui communiquent

1267. Comptez les serveurs qui communiquent

Difficulté :Moyen

Sujets : Tableau, recherche en profondeur d'abord, recherche en largeur d'abord, recherche d'union, matrice, comptage

Vous recevez une carte d'un centre de serveurs, représentée sous la forme d'une grille matricielle m * n entière, où 1 signifie que sur cette cellule il y a un serveur et 0 signifie qu'il n'y a pas de serveur. On dit que deux serveurs communiquent s'ils sont sur la même ligne ou sur la même colonne.

Renvoyer le nombre de serveurs qui communiquent avec n'importe quel autre serveur.

Exemple 1 :

• Entrée : grille = [[1,0],[0,1]]
• Sortie : 0
• Explication : Aucun serveur ne peut communiquer avec les autres.

Exemple 2 :

• Entrée : grille = [[1,0],[1,1]]
• Sortie : 3
• Explication : Les trois serveurs peuvent communiquer avec au moins un autre serveur.

Exemple 3 :

• Entrée : grille = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1] ]
• Sortie : 4
• Explication : Les deux serveurs de la première rangée peuvent communiquer entre eux. Les deux serveurs de la troisième colonne peuvent communiquer entre eux. Le serveur dans le coin inférieur droit ne peut communiquer avec aucun autre serveur.

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 1
• 1
• grille[i][j] == 0 ou 1

Indice :

1. Stockez le numéro d'ordinateur dans chaque ligne et colonne.
2. Comptez tous les serveurs qui ne sont pas isolés.

Solution :

Nous suivrons ces étapes :

Approche:

1. Compter les serveurs dans chaque ligne et colonne :

   • Parcourez la grille et calculez le nombre de serveurs existants dans chaque ligne et chaque colonne. Cela peut être fait en utilisant deux tableaux rowCount et colCount, où :
     • rowCount[i] stocke le nombre de serveurs dans la ligne i.
     • colCount[j] stocke le nombre de serveurs dans la colonne j.

2. Vérifier la communication :

   • Pour chaque serveur de la grille, vérifiez s'il peut communiquer avec n'importe quel autre serveur en vérifiant le rowCount et le colCount. Si l'un ou l'autre est supérieur à 1, alors le serveur peut communiquer avec les autres.

3. Comptez les serveurs qui communiquent :

   • Parcourez à nouveau la grille et pour chaque serveur (cellule de valeur 1), vérifiez s'il appartient à une ligne ou une colonne où il y a plus d'un serveur.

Implémentons cette solution en PHP : 1267. Compter les serveurs qui communiquent

<?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
?>

Explication:

1. Comptage des serveurs en lignes et colonnes :

   • Nous parcourons la grille et comptons le nombre de serveurs (c'est-à-dire 1) dans chaque ligne et chaque colonne. Nous stockons ces décomptes dans les tableaux rowCount et colCount.

2. Identification des serveurs communicants :

   • Après avoir compté, nous parcourons chaque serveur (cellule de valeur 1). Un serveur peut communiquer avec d'autres si le nombre de serveurs dans sa ligne (rowCount[i] > 1) ou le nombre de serveurs dans sa colonne (colCount[j] > 1) est supérieur à 1. On incrémente ensuite le résultat compteur pour chaque serveur communicant.

3. Sortie :

   • La fonction renvoie le nombre total de serveurs pouvant communiquer avec d'autres serveurs.

Complexité temporelle :

• O(m * n), où m est le nombre de lignes et n est le nombre de colonnes. En effet, nous parcourons la grille deux fois : une fois pour compter les serveurs dans les lignes et les colonnes, et une fois pour vérifier la communication.

Cette solution gère efficacement le problème dans les limites données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!