حل مسئله مصاحبه میوه به سبد [+ ВИДЕО]
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) ثابت می شود.
https://www.youtube.com/watch?v=YldEWOgbSnE
تعیین وظایف
از مزرعه ای بازدید می کنید که در آن درختان در یک ردیف از چپ به راست ردیف شده اند. درختان با یک آرایه عدد صحیح نشان داده می شوند 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) ثابت می شود.