DSA Chronicles Day 3: جامد کردن هسته – 5 مشکلات ، 5 یادگیری

مشکل 1 طولانی ترین بستر بدون تکرار شخصیت ها

مشکل:

با توجه به مجموعه ای از تعداد عدد صحیح ، طول طولانی ترین دنباله عناصر متوالی را برگردانید.

شما باید الگوریتمی بنویسید که در زمان O (n) اجرا شود.

پیوند به مشکل: https://leetcode.com/problems/longest-consount- pertive-sequence/description/

رویکرد:

فکر اول:

1. از یک شمارش اساسی استفاده کرد[256] آرایه برای ردیابی فرکانس کاراکترها.
2. در صورت یافتن نسخه تکراری ، فرکانس را بررسی کرده و به روزرسانی را مستقیماً شروع کنید.
3. ترتیب نادرست شروع ++ و شمارش[s[start]]-، که باعث ایجاد خطاهای منطقی برای شخصیت های همپوشانی شد.

رویکرد نهایی:

1. تکنیک پنجره کشویی استفاده شده با دو نشانگر شروع و پایان.
2. برای ردیابی چند بار شخصیت در پنجره فعلی ، یک آرایه شمارش را حفظ کرد.
3. در تشخیص یک شخصیت تکراری (تعداد[s[end]]> 1) ، پنجره را با استفاده از حلقه مدتی کوچک کنید. سپس تعداد کاهش یافته[s[start]]و شروع به جلو.
4. اندازه پنجره فعلی محاسبه شده.

آنچه من آموختم:

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

مشکل 2 فواصل ادغام

مشکل:

با توجه به فاصله ای از فواصل زمانی که فواصل دارند[i] = [starti, endi]، تمام فواصل همپوشانی را ادغام کنید و آرایه ای از فواصل غیر همپوشانی را که تمام فواصل ورودی را پوشش می دهد ، برگردانید.

پیوند به مشکل: https://leetcode.com/problems/merge-intervals/description/

رویکرد:

فکر اول:

1. مقایسه زمان پایان و ادغام بر اساس آن.
2. بررسی در نظر گرفتن اینکه آیا فاصله فعلی قبل از پایان دوره قبلی شروع می شود و محدوده را بر این اساس تنظیم می کند.
3. متوجه شد که مرتب سازی توسط زمان شروع برای گروه بندی فواصل همپوشانی بالقوه به طور مؤثر ضروری است.

رویکرد نهایی:

1. تمام فواصل را بر اساس زمان شروع آنها با استفاده از یک عملکرد Lambda مرتب کنید.
2. برای نگه داشتن فواصل ادغام ، یک لیست جدید را آغاز کنید.
3. فواصل مرتب شده را طی کنید.
4. اگر لیست ادغام شده خالی است یا هیچ همپوشانی وجود ندارد ، به سادگی فاصله را اضافه کنید.
5. اگر فاصله فعلی با آخرین فاصله ادغام شده همپوشانی دارد ، پایان آخرین فاصله ادغام شده را به حداکثر هر دو انتها به روز کنید.

آنچه من آموختم:

1. نحوه استفاده از یک تابع Lambda در C ++ برای مرتب کردن یک بردار 2D بر اساس معیارهای خاص (زمان شروع در اینجا).
2. اهمیت مرتب سازی قبل از ادغام حریص

مشکل 3 عناصر مکرر k برتر

مشکل:

با توجه به یک عدد آرایه عدد صحیح و یک عدد صحیح k ، k را که بیشترین عناصر را باز می گرداند ، برگردانید. ممکن است جواب را به هر ترتیب برگردانید.

پیوند به مشکل: https://leetcode.com/problems/top-k-frequent-elements/description/

رویکرد:

فکر اول:

1. من می دانستم که باید فرکانس ها را بشمارم اما در مورد چگونگی استخراج K Top K به طور کارآمد مشخص نیست.
2. فکر کردن به مرتب سازی نقشه کامل هش ، اما ناکارآمد است (o (n log n)).
3. فراموش کرده اید که قبل از فشار دادن به پشته ، در واقع جفت (فرکانس ، عدد) ایجاد کنید.

رویکرد نهایی:

1. یک hash_map را بسازید که کلید آن عدد باشد و مقدار فرکانس آن است.
2. حداکثر پشته را با فرکانس به عنوان اولین عنصر ایجاد کنید تا شایع ترین عناصر در مرحله اول قرار بگیرند.
3. نقشه را عبور دهید ، هر جفت (فرکانس ، عدد) را به داخل پشته فشار دهید.
4. عناصر k برتر را از پشته پاپ کرده و شماره ها را در یک بردار نتیجه ذخیره کنید.

آنچه من آموختم:

1. متوجه شدم که (فرکانس ، عنصر) اگر بخواهم بر اساس فرکانس با استفاده از رفتار پیش فرض حداکثر ، بر اساس فرکانس مرتب سازی کنم ، باید در این جفت سفارش باشد.
2. درک کنید که چگونه یک پشته به شبیه سازی رفتار یک ساختار پویا “بالا k” – از نظر خودکار کمک می کند. آنها مهمترین (مکرر) عناصر را در بالا حفظ می کنند.

مشکل 4 مبلغ فرعی برابر k

مشکل:

با توجه به مجموعه ای از شماره های عدد صحیح و یک عدد صحیح k ، تعداد کل زیر مجموعه هایی را که مبلغ آن برابر با k است ، برگردانید.

یک فرعی یک توالی غیر خالی از عناصر در یک آرایه است.

پیوند به مشکل: https://leetcode.com/problems/subarray-sum-equals-k/description/

رویکرد:

1. در حین گذر از آرایه ، یک پیشوند در حال اجرا را حفظ کرد.
2. از نقشه هش برای ذخیره فرکانس هر مبلغ پیشوند روبرو شده استفاده شده است.
3. در هر مرحله ، بررسی کنید که آیا (Prefixsum – k) در نقشه وجود دارد – نشانگر یک زیر مجموعه ای است که خلاصه آن است.
4. نقشه را با {0: 1} تنظیم کنید تا زیر مجموعه ها را از فهرست 0 شروع کنید.

آنچه من آموختم:

1. پیشوند مبلغ با ردیابی مقادیر انباشته ، به کاهش حلقه های تو در تو کمک می کند.
2. نقشه های هش جستجوی سریع برای مبالغ پیشوند قبلی – ساخت زمان خطی الگوریتم.
3. این تکنیک یک الگوی متداول در مشکلاتی است که شامل زیر مجموعه هایی با مبلغ داده شده است.

مشکل 5 3sum

مشکل:

با توجه به تعداد آرایه عدد صحیح ، تمام سه گانه را برگردانید [nums[i]، شماره[j]، شماره[k]]به گونه ای که من! = j ، i! = k ، و j! = k ، و nums[i] + شماره[j] + شماره[k] == 0.

توجه کنید که مجموعه راه حل نباید حاوی سه گانه تکراری باشد.

پیوند به مشکل: https://leetcode.com/problems/3sum/description/

رویکرد:

1. برای پیگیری مبالغ تجمعی در حین عبور از آرایه ، مقدار پیشوند استفاده شده است.
2. برای ذخیره فرکانس هر مبلغ پیشوند ، نقشه هش را حفظ کرد.
3. برای هر شاخص ، من بررسی کردم که آیا یک فرعی که پایان می یابد در آنجا تعداد K با استفاده از: Prefix_sum – K وجود دارد
4. اگر بله ، من شمارش را افزایش دادم تا چند بار این تفاوت قبلاً ظاهر شده باشد.
5. نقشه هش را با 0: 1} تنظیم کنید تا در هنگام شروع زیر مجموعه در شاخص 0 ، موارد لبه را کنترل کنید.

آنچه من آموختم:

1. مبالغ پیشوند ابزارهای قدرتمندی برای مشکلات فرعی است.
2. نقشه های هش می توانند به طور مؤثر مبلغ پیشوند قبلی را برای یافتن زیر مجموعه ها در زمان O (n) ردیابی کنند.
3. این رویکرد نسبت به نیروی بی رحمانه که O (N²) است ، بهبود می یابد.

پیوند به کد من: https://github.com/amruta-25/dsa_chronicles.git