Kira Pelayan yang Berkomunikasi

1267. Kira Pelayan yang Berkomunikasi

Kesukaran: Sederhana

Topik: Tatasusunan, Depth-First Search, Breadth-First Search, Union Find, Matriks, Pengiraan

Anda diberi peta pusat pelayan, diwakili sebagai grid matriks integer m * n, dengan 1 bermakna pada sel tersebut terdapat pelayan dan 0 bermakna ia bukan pelayan. Dua pelayan dikatakan berkomunikasi jika ia berada pada baris yang sama atau pada lajur yang sama.

Kembalikan bilangan pelayan yang berkomunikasi dengan mana-mana pelayan lain.

Contoh 1:

• Input: grid = [[1,0],[0,1]]
• Output: 0
• Penjelasan: Tiada pelayan boleh berkomunikasi dengan orang lain.

Contoh 2:

• Input: grid = [[1,0],[1,1]]
• Output: 3
• Penjelasan: Ketiga-tiga pelayan boleh berkomunikasi dengan sekurang-kurangnya satu pelayan lain.

Contoh 3:

• Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1] ]
• Output: 4
• Penjelasan: Kedua-dua pelayan di baris pertama boleh berkomunikasi antara satu sama lain. Kedua-dua pelayan dalam lajur ketiga boleh berkomunikasi antara satu sama lain. Pelayan di sudut kanan bawah tidak boleh berkomunikasi dengan mana-mana pelayan lain.

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 1
• 1
• grid[i][j] == 0 atau 1

Petunjuk:

1. Simpan nombor komputer dalam setiap baris dan lajur.
2. Kira semua pelayan yang tidak diasingkan.

Penyelesaian:

Kami akan mengikuti langkah ini:

Pendekatan:

1. Kira Pelayan dalam Setiap Baris dan Lajur:

   • Lintas grid dan hitung bilangan pelayan yang wujud dalam setiap baris dan setiap lajur. Ini boleh dilakukan menggunakan dua tatasusunan rowCount dan colCount, di mana:
     • rowCount[i] menyimpan bilangan pelayan dalam baris i.
     • colCount[j] menyimpan bilangan pelayan dalam lajur j.

2. Semak Komunikasi:

   • Untuk setiap pelayan dalam grid, semak sama ada ia boleh berkomunikasi dengan mana-mana pelayan lain dengan menyemak rowCount dan colCount. Jika salah satu lebih besar daripada 1, maka pelayan boleh berkomunikasi dengan orang lain.

3. Kira Pelayan yang Berkomunikasi:

   • Lintas grid sekali lagi dan untuk setiap pelayan (sel dengan nilai 1), semak sama ada ia tergolong dalam baris atau lajur yang terdapat lebih daripada satu pelayan.

Mari laksanakan penyelesaian ini dalam PHP: 1267. Kira Pelayan yang Berkomunikasi

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

Penjelasan:

1. Mengira Pelayan dalam Baris dan Lajur:

   • Kami mengulangi grid dan mengira bilangan pelayan (iaitu, 1s) dalam setiap baris dan setiap lajur. Kami menyimpan kiraan ini dalam tatasusunan rowCount dan colCount.

2. Mengenal pasti Pelayan Berkomunikasi:

   • Selepas mengira, kami mengulangi setiap pelayan (sel dengan nilai 1). Pelayan boleh berkomunikasi dengan orang lain jika kiraan pelayan dalam barisnya (rowCount[i] > 1) atau kiraan pelayan dalam lajurnya (colCount[j] > 1) lebih besar daripada 1. Kami kemudian menambah hasilnya kaunter untuk setiap pelayan berkomunikasi.

3. Output:

   • Fungsi ini mengembalikan jumlah kiraan pelayan yang boleh berkomunikasi dengan pelayan lain.

Kerumitan Masa:

• O(m * n), dengan m ialah bilangan baris dan n ialah bilangan lajur. Ini kerana kami berulang kali melalui grid dua kali: sekali untuk mengira pelayan dalam baris dan lajur, dan sekali untuk menyemak komunikasi.

Penyelesaian ini cekap mengendalikan masalah dalam kekangan yang diberikan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Kira Pelayan yang Berkomunikasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!