حل مسئله مصاحبه میوه به سبد [+ ВИДЕО]

Summarize this content to 400 words in Persian Lang

تعیین وظایف

از مزرعه ای بازدید می کنید که در آن درختان در یک ردیف از چپ به راست ردیف شده اند. درختان با یک آرایه عدد صحیح نشان داده می شوند fruits، جایی که fruits[i] نوع میوه درخت i-ام است.

شما می خواهید تا آنجا که ممکن است میوه جمع آوری کنید، اما مالک مزرعه قوانین زیر را تعیین کرده است:

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

چالش این است که حداکثر تعداد میوه هایی را که می توان با رعایت این قوانین جمع آوری کرد، پیدا کرد.

رویکرد راه حل

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

الگوریتم

مقداردهی اولیه متغیرها:

res برای ذخیره نتیجه (حداکثر تعداد میوه ها).

type_counter برای ردیابی مقدار هر نوع میوه در پنجره فعلی.

left برای نشان دادن حاشیه سمت چپ پنجره.

قدم زدن در یک آرایه fruits:

با استفاده از یک متغیر right برای نشان دادن حاشیه سمت راست پنجره.
شمارنده نوع فعلی میوه را افزایش دهید right_fruit.

بررسی وضعیت اعتبار پنجره:

اگر تعداد انواع میوه در پنجره بیشتر از دو شود (len(type_counter) == 3، حاشیه سمت چپ پنجره را حرکت دهید left در سمت راست، شمارنده‌های میوه‌ها را کاهش دهید و انواع میوه‌ها را با شمارنده صفر حذف کنید.

به روز رسانی نتیجه:

در هر تکرار ما به روز می کنیم res، محاسبه طول پنجره فعلی.

کد راه حل

from collections import defaultdict
from typing import List

class Solution:
def totalFruit(self, fruits: List[int]) -> int:
res = 0
type_counter = defaultdict(int)
left = 0

for right in range(len(fruits)):
right_fruit = fruits[right] type_counter[right_fruit] += 1

while len(type_counter) == 3:
left_fruit = fruits[left] type_counter[left_fruit] -= 1
if type_counter[left_fruit] == 0:
del type_counter[left_fruit] left += 1

res = max(res, right – left + 1)

return res

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

توضیح کد

مقداردهی اولیه:

res – متغیر برای نگهداری حداکثر میوه.

type_counter – یک جدول هش برای پیگیری مقدار هر نوع میوه در پنجره فعلی.

left – شاخص حاشیه سمت چپ پنجره.

حلقه اصلی:

از میان آرایه عبور می کنیم fruits با حاشیه سمت راست پنجره right.
شمارنده نوع فعلی میوه را افزایش دهید right_fruit.

کاهش پنجره:

اگر تعداد انواع میوه در پنجره از دو نوع بیشتر باشد (len(type_counter) == 3) حاشیه سمت چپ پنجره را به سمت راست ببرید تا تعداد انواع میوه قابل قبول (دو یا کمتر) شود.

به روز رسانی نتیجه:

در هر تکرار ما به روز می کنیم res، محاسبه طول پنجره فعلی (right – left + 1).

تجسم راه حل

یک آرایه را در نظر بگیرید fruits = [1, 2, 1, 2, 3, 3, 2, 1] و مراحل حل مشکل را تجسم کنید و وضعیت فعلی پنجره کشویی را نشان دهید.

مراحل اجرا:

تکرار 0:

میوه فعلی: 1
پنجره: [1]، 2، 1، 2، 3، 3، 4، 1، 2
type_counter: {1: 1}
طول پنجره: 1

تکرار 1:

میوه فعلی: 2
پنجره: [1, 2]، 1، 2، 3، 3، 4، 1، 2
type_counter: {1: 1، 2: 1}
طول پنجره: 2

تکرار 2:

میوه فعلی: 1
پنجره: [1, 2, 1]، 2، 3، 3، 4، 1، 2
type_counter: {1: 2، 2: 1}
طول پنجره: 3

تکرار 3:

میوه فعلی: 2
پنجره: [1, 2, 1, 2]، 3، 3، 4، 1، 2
type_counter: {1: 2، 2: 2}
طول پنجره: 4

تکرار 4:

میوه فعلی: 3
پنجره: [1, 2, 1, 2, 3]، 3، 4، 1، 2
type_counter: {1: 2، 2: 2، 3: 1}
طول پنجره: 5
کاهش پنجره:

سمت چپ: 1
پنجره پس از کاهش: 1، [2, 1, 2, 3]، 3، 4، 1، 2
type_counter: {1: 1، 2: 2، 3: 1}
طول پنجره: 4
سمت چپ: 2
پنجره پس از کاهش: 1، 2، [1, 2, 3]، 3، 4، 1، 2
type_counter: {1: 1، 2: 1، 3: 1}
طول پنجره: 3
سمت چپ: 3
پنجره پس از کاهش: 1، 2، 1، [2, 3]، 3، 4، 1، 2
type_counter: {2: 1، 3: 1}
طول پنجره: 2

پنجره پس از به روز رسانی نتیجه: 1، 2، 1، [2, 3]، 3، 4، 1، 2

حداکثر فعلی: 4

تکرار 5:

میوه فعلی: 3
پنجره: 1، 2، 1، [2, 3, 3]، 4، 1، 2
type_counter: {2: 1، 3: 2}
طول پنجره: 3

تکرار 6:

میوه فعلی: 4
پنجره: 1، 2، 1، [2, 3, 3, 4]، 1، 2
type_counter: {2: 1، 3: 2، 4: 1}
طول پنجره: 4
کاهش پنجره:

سمت چپ: 4
پنجره پس از کاهش: 1، 2، 1، 2، [3, 3, 4]، 1، 2
type_counter: {3: 2، 4: 1}
طول پنجره: 3

پنجره پس از به روز رسانی نتیجه: 1، 2، 1، 2، [3, 3, 4]، 1، 2

حداکثر فعلی: 4

تکرار 7:

میوه فعلی: 1
پنجره: 1، 2، 1، 2، [3, 3, 4, 1]، 2
type_counter: {3: 2، 4: 1، 1: 1}
طول پنجره: 4
کاهش پنجره:

سمت چپ: 5
پنجره پس از کاهش: 1، 2، 1، 2، 3، [3, 4, 1]، 2
type_counter: {3: 1، 4: 1، 1: 1}
طول پنجره: 3
سمت چپ: 6
پنجره پس از کاهش: 1، 2، 1، 2، 3، 3، [4, 1]، 2
type_counter: {4: 1، 1: 1}
طول پنجره: 2

پنجره پس از به روز رسانی نتیجه: 1، 2، 1، 2، 3، 3، [4, 1]، 2

حداکثر فعلی: 4

تکرار 8:

میوه فعلی: 2
پنجره: 1، 2، 1، 2، 3، 3، [4, 1, 2] type_counter: {4: 1، 1: 1، 2: 1}
طول پنجره: 3
کاهش پنجره:

سمت چپ: 7
پنجره پس از کاهش: 1، 2، 1، 2، 3، 3، 4، [1, 2] type_counter: {1: 1، 2: 1}
طول پنجره: 2

پنجره پس از به روز رسانی نتیجه: 1، 2، 1، 2، 3، 3، 4، [1, 2]

حداکثر فعلی: 4

پس از تمام تکرارها، حداکثر تعداد میوه های قابل جمع آوری 4 عدد است.

پیچیدگی مجانبی

پیچیدگی زمانی: O(n)

در حال قدم زدن در میان توده هستیم fruits یک بار با استفاده از حاشیه پنجره سمت راست (right).
در بدترین حالت، حاشیه سمت چپ پنجره (left) همچنین از هر عنصر آرایه یک بار عبور می کند.
در نتیجه، هر عنصر آرایه بیش از دو بار پردازش نمی شود، که منجر به پیچیدگی زمانی خطی O(n) می شود، که در آن n – طول آرایه fruits.

پیچیدگی حافظه: O(1)

ما از جدول هش استفاده می کنیم type_counter برای ذخیره مقدار هر نوع میوه در پنجره فعلی.
حداکثر تعداد انواع مختلف میوه در جدول هش به دو عدد محدود است، زیرا ما فقط دو سطل داریم.
بنابراین، مقدار حافظه مورد نیاز برای ذخیره داده ها در جدول هش مستقل از اندازه آرایه ورودی است و ثابت می ماند.
این منجر به پیچیدگی حافظه O(1) ثابت می شود.

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        res = 0
        type_counter = defaultdict(int)
        left = 0

        for right in range(len(fruits)):
            right_fruit = fruits[right]
            type_counter[right_fruit] += 1

            while len(type_counter) == 3:
                left_fruit = fruits[left]
                type_counter[left_fruit] -= 1
                if type_counter[left_fruit] == 0:
                    del type_counter[left_fruit]
                left += 1

            res = max(res, right - left + 1)

        return res