1267. تعداد سرورهایی که ارتباط برقرار می کنند

1267. تعداد سرورهایی که ارتباط برقرار می کنند

سختی: متوسط

موضوعات: Array، Depth-First Search، Breadth-First Search، Union Find، Matrix، Counting

نقشه ای از یک مرکز سرور به شما داده می شود که به صورت یک نشان داده شده است m * n ماتریس عدد صحیح grid، کجا 1 یعنی روی آن سلول یک سرور و 0 یعنی سرور نیست گفته می شود که دو سرور در یک ردیف یا در یک ستون با هم ارتباط برقرار می کنند.

بازگشت تعداد سرورهایی که با هر سرور دیگری در ارتباط هستند.

مثال 1:

• ورودی: شبکه = [[1,0]،[0,1]]
• خروجی: 0
• توضیح: هیچ سروری نمی تواند با دیگران ارتباط برقرار کند.

مثال 2:

• ورودی: شبکه = [[1,0]،[1,1]]
• خروجی: 3
• توضیح: هر سه سرور می توانند حداقل با یک سرور دیگر ارتباط برقرار کنند.

مثال 3:

• ورودی: شبکه = [[1,1,0,0]،[0,0,1,0]،[0,0,1,0]،[0,0,0,1]]
• خروجی: 4
• توضیح: دو سرور در ردیف اول می توانند با یکدیگر ارتباط برقرار کنند. دو سرور در ستون سوم می توانند با یکدیگر ارتباط برقرار کنند. سرور در گوشه پایین سمت راست نمی تواند با هیچ سرور دیگری ارتباط برقرار کند.

محدودیت ها:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 250
• 1 <= n <= 250
• grid[i][j] == 0 or 1

اشاره:

1. تعداد رایانه را در هر سطر و ستون ذخیره کنید.
2. تمام سرورهایی که ایزوله نیستند را بشمارید.

راه حل:

ما این مراحل را دنبال خواهیم کرد:

رویکرد:

1. تعداد سرورها در هر سطر و ستون:

   • از شبکه عبور کنید و تعداد سرورها را در هر سطر و هر ستون محاسبه کنید. این را می توان با استفاده از دو آرایه انجام داد rowCount و colCount، جایی که:
     • rowCount[i] تعداد سرورهای ردیفی را ذخیره می کند i.
     • colCount[j] تعداد سرورها را در ستون ذخیره می کند j.

2. ارتباط را بررسی کنید:

   • برای هر سرور در شبکه، بررسی کنید که آیا می‌تواند با سرور دیگری ارتباط برقرار کند یا خیر rowCount و colCount. اگر یکی از آنها بزرگتر از 1 باشد، سرور می تواند با دیگران ارتباط برقرار کند.

3. سرورهایی را که ارتباط برقرار می کنند بشمارید:

   • دوباره از طریق شبکه و برای هر سرور (سلول با مقدار) عبور کنید 1، بررسی کنید که آیا به سطر یا ستونی تعلق دارد که در آن بیش از یک سرور وجود دارد.

بیایید این راه حل را در PHP پیاده سازی کنیم: 1267. تعداد سرورهایی که ارتباط برقرار می کنند

/**
 * @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
?>

توضیح:

1. شمارش سرورها در سطر و ستون:

   • ما روی شبکه تکرار می کنیم و تعداد سرورها را می شماریم (یعنی 1s) در هر سطر و هر ستون هستند. ما این تعداد را در rowCount و colCount آرایه ها

2. شناسایی سرورهای ارتباطی:

   • پس از شمارش، روی هر سرور (سلول با مقدار) تکرار می کنیم 1). یک سرور می تواند با دیگران ارتباط برقرار کند اگر تعداد سرورها در ردیف آن (rowCount[i] > 1) یا تعداد سرورها در ستون آن (colCount[j] > 1) بزرگتر از 1 است. سپس شمارنده نتیجه را برای هر سرور در حال ارتباط افزایش می دهیم.

3. خروجی:

   • این تابع تعداد کل سرورهایی را که می توانند با سرورهای دیگر ارتباط برقرار کنند، برمی گرداند.

پیچیدگی زمانی:

• O(m * n)، کجا m تعداد ردیف ها و n تعداد ستون ها است. این به این دلیل است که ما دو بار از طریق شبکه تکرار می کنیم: یک بار برای شمارش سرورها در ردیف ها و ستون ها، و یک بار برای بررسی ارتباط.

این راه حل به طور موثر مشکل را در محدودیت های داده شده مدیریت می کند.

لینک های تماس

اگر این مجموعه را مفید یافتید، لطفاً آن را در نظر بگیرید مخزن یک ستاره در GitHub یا اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود 😍. حمایت شما برای من اهمیت زیادی دارد!

اگر محتوای مفیدتری مانند این می‌خواهید، در صورت تمایل من را دنبال کنید: