حل کردن "پرتقال های پوسیده"

Summarize this content to 400 words in Persian Lang امروز مطالعه در مورد چگونگی حل لیت کد نارنجی پوسیده است

بیایید نحوه حل مشکل، نحوه درک برخی از کلمات کلیدی از توضیحات و کد راه حل در پایتون را بررسی کنیم.

مشکل

در یک آرایه m x n، هر موقعیت می تواند سه مقدار داشته باشد:

0 – یک موقعیت خالی؛

1 – یک پرتقال تازه؛

2 – یک پرتقال گندیده

هر دقیقه یک پرتقال تازه که نزدیک به یک پرتقال پوسیده است نیز می پوسد.

باید تعداد دقیقه های سپری شده تا زمانی که همه پرتقال ها پوسیده شوند را برگردانیم، یا -1 اگر امکان پوسیده شدن همه آنها وجود ندارد.

فکر کنم مشکلی نیست

برای کمک به حل مشکل، ضروری است که بتوانیم طرح این ماتریس را با چند رنگ پرتقال تجسم کنیم:

با این چیدمان چند دقیقه طول میکشه که همشون پوسیده بشن؟

الف) 5
ب) 3
ج) 4

شاید من شما را ناامید کردم، اما پاسخ 4 نیست.
3 دقیقه طول می کشد تا همه پرتقال ها پوسیده شوند.

منطق پشت آن این است که در هر دقیقه بیش از یک پرتقال می تواند پوسیده شود. به عبارت دیگر پرتقال ها در حال فاسد شدن هستند همزمان. این کلمه را به خوبی حفظ کنید.

این ماتریس یک است شمردن. بله، ماتریس ها نمودار هستند. امکان رمزگذاری گراف در ماتریس وجود دارد.

و دانستن این موضوع چه چیزی را تغییر می دهد؟ اولا، این امر درک ما از مشکل را تسهیل می کند. هدف ما این است که بگوییم چقدر طول می کشد تا همه پرتقال ها پوسیده شوند و سعی کنیم نقاط را به هم وصل کنیم (پرتقال فاسد و پرتقال تازه). مسائلی که در آن ما بین نقاط یک ماتریس ارتباط داریم، بویی شبیه به نمودار دارند.

دو راه بسیار معروف برای حل مسائل نمودار وجود دارد: DFS (Depth-First Search) ه BFS (جستجوی عرض-اول).

برای این مشکل استفاده خواهیم کرد BFS. انگیزه با کلمه ارتباط دارد همزمان. وقتی از DFS برای حل یک مشکل استفاده می کنیم، از stack استفاده می کنیم. و پشته یک ساختار داده است که در بازگشت استفاده می شود. وقتی از بازگشت استفاده می کنیم، قبل از آزمایش گزینه های دیگر، امکان مسیر را تمام می کنیم که از همزمانی آن جلوگیری می کند.

در این مشکل، برای مثال، با استفاده از بازگشت، مسیری را که از یک پرتقال پوسیده شروع می‌شود، شمارش می‌کند و اشتباه شمارش می‌شود.

مراحل الگوریتم

بشمار که چند تا پرتقال تازه داریم. تا زمانی که آنها در حال پوسیدن هستند، وقتی به صفر رسید، می توانیم از آن به عنوان یک شرط توقف استفاده کنیم.
موقعیت های پرتقال های فاسد را جمع آوری کنید. دلیل آن این است که با دانستن اینکه آنها کجا هستند، می توانیم از BFS برای تکرار همزمان همه پرتقال های بد استفاده کنیم.
راه رفتن در همه جهات به جز مورب ها، تلاش برای یافتن پرتقال های جدید برای پوسیدگی.

کد راه حل

class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
minutes = 0

queue = deque()
fresh = 0

for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 2:
queue.append((row, col))
elif grid[row][col] == 1:
fresh += 1

deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)] while queue and fresh:
length = len(queue)

for _ in range(length):
row, col = queue.popleft()

for dr, dc in deltas:
next_row, next_col = row + dr, col + dc

if (
next_row in range(len(grid))
and next_col in range(len(grid[0]))
and grid[next_row][next_col] == 1
):
grid[next_row][next_col] = 2
queue.append((next_row, next_col))
fresh -= 1
minutes += 1

return minutes if fresh == 0 else -1

اگرچه کد کمی طولانی است (حل مشکلات نمودار معمولاً به کد زیادی نیاز دارد)، اما آنقدرها هم پیچیده نیست. حداقل این احساس را به شما نمی دهد که باید یک خرگوش را از سوراخ خرگوش به خط بیرون بکشید.

ما با چند متغیر مهم شروع می کنیم:

یک عرشه برای BFS

minutes برای ذخیره نتیجه نهایی؛
E fresh شمارش کنیم که چند پرتقال تازه داریم.

حالا می شمریم که چند پرتقال تازه داریم و کدام یک فاسد شده اند:

for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 2:
queue.append((row, col))
elif grid[row][col] == 1:
fresh += 1

اکنون یک بلوک کمی پیچیده می آید:

deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)] while queue and fresh:
length = len(queue)

for _ in range(length):
row, col = queue.popleft()

for dr, dc in deltas:
next_row, next_col = row + dr, col + dc

if (
next_row in range(len(grid))
and next_col in range(len(grid[0]))
and grid[next_row][next_col] == 1
):
grid[next_row][next_col] = 2
queue.append((next_row, next_col))
fresh -= 1
minutes += 1

deltas یک متغیر برای ذخیره تمام جهت هایی است که می توانیم در آن راه برویم. در یک آرایه m x n می توانیم یک ستون را به سمت چپ، یک خط زیر و غیره حرکت دهیم.

while queue and fresh شرایط توقف ما را تضمین می کند. تا زمانی که پرتقال برای اضافه کردن داریم یا دیگر پرتقال تازه نداریم، باید به اضافه کردن پرتقال های فاسد ادامه دهیم تا همه پرتقال های دیگر را که در دسترس هستند بپوسند.

حالا مهم ترین قسمت می آید روی حیله و تزویر: o for داخل while.
برای ما ضروری است که دقیقه پرتقال های پوسیده را به طور همزمان بشماریم.

می تونی اونجا امتحان بدی یک مفسر پایتون را باز کنید، deque را وارد کنید، یک deque ایجاد کنید و شروع به حذف عناصر از سمت چپ و اضافه کردن به سمت راست کنید.

O for این تضمین می‌کند که برای مثال، بار اول، همه پرتقال‌های بد را تکرار می‌کنیم و برای دفعه بعد همان استراتژی را دنبال می‌کنیم. اگر در حلقه بعدی 3 پرتقال فاسد دیگر را ردیف کنیم، روی این 3 پرتقال تکرار می کنیم که تعداد بیشتری اضافه می کند. n پرتقال و غیره

حالا یکی دیگه for. این در همه جهات تکرار می شود:

for dr, dc in deltas:
next_row, next_col = row + dr, col + dc

if (
next_row in range(len(grid))
and next_col in range(len(grid[0]))
and grid[next_row][next_col] == 1
):
grid[next_row][next_col] = 2
queue.append((next_row, next_col))
fresh -= 1

و شرایط محیطی بسیار مهم است:

بررسی کنید که آیا هنوز در ماتریس راه می رویم – ستون ها و ردیف های معتبر.
بررسی می کند که آیا موقعیت فعلی نارنجی است و تازه است.

در صورت مثبت بودن آن را به آن اضافه می کنیم صف پرتقال های فاسد و تعداد پرتقال های تازه را کاهش دادیم.

بدون فراموش کردن به‌روزرسانی مقدار به 2، زیرا تضمین می‌کند که پرتقال پوسیده را به ما اضافه نمی‌کنیم. صف.

و در نهایت مقدار دقیقه را برمی گردانیم:

return minutes if fresh == 0 else -1

اگر هنوز پرتقال تازه دارید، پس امکان نداشت همه آنها پوسیده شوند و برگردند -1. اگر نه، تعداد دقایق گذشته را برمی گردانیم.

نتیجه

پیچیدگی زمانی: O(mxn)
برای کشف پرتقال ها باید کل تخته را تکرار کنیم، اما فقط یک بار برای هر سطر/ستون.

پیچیدگی فضا: O(mxn)
ما از یک صف استفاده می کنیم که در بدترین حالت، یک آرایه کامل پر از پرتقال های پوسیده خواهد داشت.

این چالش ساده نیست و چند ساعت طول کشید تا آن را انجام دهم. و این کد نهایی نبود. در کل سعی کردم ارسال کنم هشت بار در پلت فرم leetcode.

امروز مطالعه در مورد چگونگی حل لیت کد نارنجی پوسیده است

بیایید نحوه حل مشکل، نحوه درک برخی از کلمات کلیدی از توضیحات و کد راه حل در پایتون را بررسی کنیم.

مشکل

در یک آرایه m x n، هر موقعیت می تواند سه مقدار داشته باشد:

• 0 – یک موقعیت خالی؛
• 1 – یک پرتقال تازه؛
• 2 – یک پرتقال گندیده

هر دقیقه یک پرتقال تازه که نزدیک به یک پرتقال پوسیده است نیز می پوسد.

باید تعداد دقیقه های سپری شده تا زمانی که همه پرتقال ها پوسیده شوند را برگردانیم، یا -1 اگر امکان پوسیده شدن همه آنها وجود ندارد.

فکر کنم مشکلی نیست

برای کمک به حل مشکل، ضروری است که بتوانیم طرح این ماتریس را با چند رنگ پرتقال تجسم کنیم:

با این چیدمان چند دقیقه طول میکشه که همشون پوسیده بشن؟

الف) 5
ب) 3
ج) 4

شاید من شما را ناامید کردم، اما پاسخ 4 نیست.
3 دقیقه طول می کشد تا همه پرتقال ها پوسیده شوند.

منطق پشت آن این است که در هر دقیقه بیش از یک پرتقال می تواند پوسیده شود. به عبارت دیگر پرتقال ها در حال فاسد شدن هستند همزمان. این کلمه را به خوبی حفظ کنید.

این ماتریس یک است شمردن. بله، ماتریس ها نمودار هستند. امکان رمزگذاری گراف در ماتریس وجود دارد.

و دانستن این موضوع چه چیزی را تغییر می دهد؟ اولا، این امر درک ما از مشکل را تسهیل می کند. هدف ما این است که بگوییم چقدر طول می کشد تا همه پرتقال ها پوسیده شوند و سعی کنیم نقاط را به هم وصل کنیم (پرتقال فاسد و پرتقال تازه). مسائلی که در آن ما بین نقاط یک ماتریس ارتباط داریم، بویی شبیه به نمودار دارند.

دو راه بسیار معروف برای حل مسائل نمودار وجود دارد: DFS (Depth-First Search) ه BFS (جستجوی عرض-اول).

برای این مشکل استفاده خواهیم کرد BFS. انگیزه با کلمه ارتباط دارد همزمان. وقتی از DFS برای حل یک مشکل استفاده می کنیم، از stack استفاده می کنیم. و پشته یک ساختار داده است که در بازگشت استفاده می شود. وقتی از بازگشت استفاده می کنیم، قبل از آزمایش گزینه های دیگر، امکان مسیر را تمام می کنیم که از همزمانی آن جلوگیری می کند.

در این مشکل، برای مثال، با استفاده از بازگشت، مسیری را که از یک پرتقال پوسیده شروع می‌شود، شمارش می‌کند و اشتباه شمارش می‌شود.

مراحل الگوریتم

• بشمار که چند تا پرتقال تازه داریم. تا زمانی که آنها در حال پوسیدن هستند، وقتی به صفر رسید، می توانیم از آن به عنوان یک شرط توقف استفاده کنیم.
• موقعیت های پرتقال های فاسد را جمع آوری کنید. دلیل آن این است که با دانستن اینکه آنها کجا هستند، می توانیم از BFS برای تکرار همزمان همه پرتقال های بد استفاده کنیم.
• راه رفتن در همه جهات به جز مورب ها، تلاش برای یافتن پرتقال های جدید برای پوسیدگی.

کد راه حل

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        minutes = 0

        queue = deque()
        fresh = 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh += 1

        deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue and fresh:
            length = len(queue)

            for _ in range(length):
                row, col = queue.popleft()

                for dr, dc in deltas:
                    next_row, next_col = row + dr, col + dc

                    if (
                        next_row in range(len(grid))
                        and next_col in range(len(grid[0]))
                        and grid[next_row][next_col] == 1
                    ):
                        grid[next_row][next_col] = 2
                        queue.append((next_row, next_col))
                        fresh -= 1
            minutes += 1

        return minutes if fresh == 0 else -1

اگرچه کد کمی طولانی است (حل مشکلات نمودار معمولاً به کد زیادی نیاز دارد)، اما آنقدرها هم پیچیده نیست. حداقل این احساس را به شما نمی دهد که باید یک خرگوش را از سوراخ خرگوش به خط بیرون بکشید.

ما با چند متغیر مهم شروع می کنیم:

• یک عرشه برای BFS
• minutes برای ذخیره نتیجه نهایی؛
• E fresh شمارش کنیم که چند پرتقال تازه داریم.

حالا می شمریم که چند پرتقال تازه داریم و کدام یک فاسد شده اند:

for row in range(len(grid)):
    for col in range(len(grid[0])):
        if grid[row][col] == 2:
            queue.append((row, col))
        elif grid[row][col] == 1:
            fresh += 1

اکنون یک بلوک کمی پیچیده می آید:

deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue and fresh:
    length = len(queue)

    for _ in range(length):
        row, col = queue.popleft()

        for dr, dc in deltas:
            next_row, next_col = row + dr, col + dc

            if (
                next_row in range(len(grid))
                and next_col in range(len(grid[0]))
                and grid[next_row][next_col] == 1
            ):
                grid[next_row][next_col] = 2
                queue.append((next_row, next_col))
                fresh -= 1
    minutes += 1

deltas یک متغیر برای ذخیره تمام جهت هایی است که می توانیم در آن راه برویم. در یک آرایه m x n می توانیم یک ستون را به سمت چپ، یک خط زیر و غیره حرکت دهیم.

while queue and fresh شرایط توقف ما را تضمین می کند. تا زمانی که پرتقال برای اضافه کردن داریم یا دیگر پرتقال تازه نداریم، باید به اضافه کردن پرتقال های فاسد ادامه دهیم تا همه پرتقال های دیگر را که در دسترس هستند بپوسند.

حالا مهم ترین قسمت می آید روی حیله و تزویر: o for داخل while.
برای ما ضروری است که دقیقه پرتقال های پوسیده را به طور همزمان بشماریم.

می تونی اونجا امتحان بدی یک مفسر پایتون را باز کنید، deque را وارد کنید، یک deque ایجاد کنید و شروع به حذف عناصر از سمت چپ و اضافه کردن به سمت راست کنید.

O for این تضمین می‌کند که برای مثال، بار اول، همه پرتقال‌های بد را تکرار می‌کنیم و برای دفعه بعد همان استراتژی را دنبال می‌کنیم. اگر در حلقه بعدی 3 پرتقال فاسد دیگر را ردیف کنیم، روی این 3 پرتقال تکرار می کنیم که تعداد بیشتری اضافه می کند. n پرتقال و غیره

حالا یکی دیگه for. این در همه جهات تکرار می شود:

for dr, dc in deltas:
    next_row, next_col = row + dr, col + dc

    if (
        next_row in range(len(grid))
        and next_col in range(len(grid[0]))
        and grid[next_row][next_col] == 1
    ):
        grid[next_row][next_col] = 2
        queue.append((next_row, next_col))
        fresh -= 1

و شرایط محیطی بسیار مهم است:

• بررسی کنید که آیا هنوز در ماتریس راه می رویم – ستون ها و ردیف های معتبر.
• بررسی می کند که آیا موقعیت فعلی نارنجی است و تازه است.

در صورت مثبت بودن آن را به آن اضافه می کنیم صف پرتقال های فاسد و تعداد پرتقال های تازه را کاهش دادیم.

بدون فراموش کردن به‌روزرسانی مقدار به 2، زیرا تضمین می‌کند که پرتقال پوسیده را به ما اضافه نمی‌کنیم. صف.

و در نهایت مقدار دقیقه را برمی گردانیم:

return minutes if fresh == 0 else -1

اگر هنوز پرتقال تازه دارید، پس امکان نداشت همه آنها پوسیده شوند و برگردند -1. اگر نه، تعداد دقایق گذشته را برمی گردانیم.

نتیجه

پیچیدگی زمانی: O(mxn)
برای کشف پرتقال ها باید کل تخته را تکرار کنیم، اما فقط یک بار برای هر سطر/ستون.

پیچیدگی فضا: O(mxn)
ما از یک صف استفاده می کنیم که در بدترین حالت، یک آرایه کامل پر از پرتقال های پوسیده خواهد داشت.

این چالش ساده نیست و چند ساعت طول کشید تا آن را انجام دهم. و این کد نهایی نبود. در کل سعی کردم ارسال کنم هشت بار در پلت فرم leetcode.