نوشته های نسیم نژند

حل سوال پر کردن مستطیل با کمترین مربع

نسیم نژند — Thu, 19 Dec 2024 16:04:57 +0330

یک مسئله جالب در leetcode وجود داره که میخواد یک سطح مستطیلی رو با کمترین تعداد مربع پوشش بده. مسئله شماره ۱۲۴۰. اضلاع مربع‌های انتخابی اعداد صحیح هستند. شاید اولین ایده قرار دادن بزرگترین مربع ممکن باشه به این شکل که عرض مستطیل اولیه میشه اولین مربع انتخابی بعد از فضای باقیمانده مربع بعدی رو انتخاب کنیم و به همین ترتیب جواب رو بدست بیاریم. پس تا اینجا با یک رویه بازگشتی سر و کار داریم. اما اگر آخرین مثال این مسئله رو نگاه کنید به راحتی متوجه میشید که این راه ما رو به جواب نمی‌رسونه. در نتیجه نیاز به بررسی تمام حالت‌های ممکن داریم.با توجه به محدودیت‌های مسئله بزرگ‌ترین ضلع میتونه ۱۳ باشه پس هم‌چنان ایده بازگشتی میتونه کارآمد باشه اما با کمی هرس! پس یعنی می‌تونیم از روش عقب‌گرد یا backtracking استفاده کنیم. چرا؟ چون ایده اولیه که از بزرگ‌ترین مربع ممکن که ضلعی برابر با عرض مستطیل داره هم چنان می‌تونه کارآمد باشه. شاید خود این حالت ما رو به جواب درست نرسونه اما میتونه شروع خوبی باشه!مثلا مثال اول رو در نظر بگیرید که مستطیل طولی برابر با ۱۳ و عرضی برابر با ۱۱ داره. اگر اولین مربع انتخابی به ضلع ۱۱ باشه٬ مستطیل باقیمانده ۲*۱۱ میشه که با پنج تا مربع ۲*۲ و دو مربع ۱*۱ کامل میشه اما همونطور که می‌بینید حداقل تعداد مربع‌ها می‌تونه کمتر از ۷تا باشه :مستطیل 11*13همون‌طور که اشاره شد٬ این جواب درست نیست ولی می‌تونه ما رو به جواب درست برسونه. چرا؟ چون مربع بزرگ‌تری نمی‌تونیم قرار بدیم پس باید حالت‌های دیگه رو امتحان کنیم تا شاید جواب بهتری رو پیدا کنیم. در نتیجه روش ایده زدن ما به این صورته که نقطه شروع بزرگ‌ترین مربع ممکن و به ترتیب امتحان کردن مربع‌های کوچک‌تر از اونه.یعنی اول یه مربع به ضلع x رو انتخاب می‌کنم و اون رو قرار می‌دم. دقت کنید به یک روشی نیاز داریم که بتونیم این استیت رو نگه داریم. یعنی بدونیم با قرار دادن مربع x چه خونه‌هایی از مستطیل اصلی پر شده و چه خونه‌هایی خالیه.دید کلی به این سوال بازگشتی بود. اما تعدادی از فراخوانی‌های بازگشتی که انجام میشه نیازی به ادامه دادن ندارند. یعنی با حالت‌های پایه‌ای بهینه‌تر می‌تونیم درخت جستجوی حالت‌ها رو هرس کنیم.اما چطور باید حالت‌های مختلف بررسی بشن؟فکر کنید یک مورچه قرار دادین که خونه‌های مستطیل رو دونه دونه جلو می ‌ره. اگر مستطیل رو یک ماتریس فرض کنید که دارای r ردیف و c ستون هست٬ اگر مورچه در ردیف r و ستون صفرم باشه در هر فراخوانی یک ستون به جلو میره تا زمانی که در ستون آخر قرار بگیره که در این صورت فراخوانی باید برای ردیف بعدی انجام بشه. همون‌طور که دقت کردید به یکی از base caseها یا حالت پایه اشاره شد.در هر فراخوانی مختصات خاصی در نظر گرفته شده یعنی در یک فراخوانی چه ردیف و ستونی باید بررسی بشه. اگر در یک فراخوانی ردیف بزرگ‌تر از r بشه به این معنیه که کار تمام شده و اگر جواب بهتری از قبلی بدست آوردیم آپدیت می‌کنیم.اما چطور جواب‌ها رو هرس می‌کنیم؟‌ مثلا بار اولی که ‌می‌خوایم سوال رو برای m=13 و n=11 حل کنیم جواب ۷ بدست میاد. اما می‌دونیم که این بهترین جواب نیست. در هر صورت باید سایر جواب‌ها رو کنترل کنیم تا بهترین جواب رو پیدا کنیم. فرض کنید شما واقعا مربع های گوناگونی دارید که می‌تونید با اونها این مستطیل رو پر کنید. وقتی یک راه حل پیدا کردید٬ دوباره از آخرین مربع که قرار دادید شروع می‌کنید به برداشتن و چک کردن اینکه آیا این امکان وجود داشت که مربع دیگری قرار بدین؟فرض کنید در حل همین حالت٬ شما از آخرین مربع 1*1 شروع کنید. اولی رو برمی‌دارید و مربع دیگری نمی‌تونید قرار بدید. به یک مرحله قبل‌تر برمی‌گردید و مربع 1*1 بعدی رو حذف می‌کنید باز به همین ترتیب. باز یک مرحله عقب‌تر برمی‌گردیم و به یک مربع 2*2 می‌رسیم. اگه مربع 2*2 رو حذف کنم٬ چه مربعی می‌تونم قرار بدم؟ می‌تونم این فضا رو با چهار مربع 1*1 پر کنم اما اینکه بدتر شد! پس زمان این فراخوانی می‌دونم که تعداد جواب‌های فعلیم بیشتر از ۷ شده٬ در نتیجه این مسیر رو ادامه نمی‌دم و باید تعداد مرحله بیشتری به عقب برگردم. همین روند برای دو مربع 2*2 دیگه تکرار می‌شه. می‌رسیم به مربع ۱۱*۱۱ . با حذف این مربع می‌شه یک مربع 10*10 قرار داد. اما خب همون‌طور که‌ ‌مشاهده می‌شه تعداد مربع‌های بیشتری از بهترین جواب فعلی بدست اومده. البته همون‌طور که اشاره شد٬ هرس اتفاق میفته و ‌نمی‌ذاره مورچه این راه اشتباه رو تا آخر ادامه بده و بعد پشیمون شه!بلکه در اولین فراخوانی که تعداد جواب از ۷ بیشتر شده از این راه صرف نظر می‌کنه و برمی‌گرده عقب. (می‌تونین فکر کنین چطور برمی‌گرده عقب و در حین قرار دادن کدوم مربع این تصمیم رو می‌گیره؟) مشابه حالت قبلی دوباره میرسه به مربع 11*11 و با حذف اون مربع ۱۰ رو انتخاب می‌کنه. همین روال تکرار میشه و می‌تونین این حالت رو روی کاغذ بکشید و ببینید که بازم جواب بهتری بدست نمیاد. به همین شکل ادامه می‌ده تا به مربع ۷ می‌رسه و جواب کمتری از جواب قبلی بدست میاره.اگه با توضیحات بالا متوجه روش عقب‌گرد نشدید حتما تو کامنت‌ها عنوان کنید تا با مثال‌های ساده‌تری توضیح بدم. هم‌چنین کشیدن درخت این مثال خیلی مفصل میشه اما میشه برای سوال‌های ساده‌تر٬ برای فهم بهتر عقب‌گرد رو روی درخت تصمیم نمایش داد. حالا شاید بپرسید چرا این مثال رو انتخاب کردم که عددهای بزرگی داره نسبتا چون تو این مثال هست که شما نقض انتخاب بزرگترین مربع ممکن بعنوان جواب کارآمد رو می‌بینید.توضیحات تکمیلی:دقت داشته باشید که در هر فراخوانی ما خونه به خونه جلو می‌ریم و برای کاهش تعداد فراخوانی‌ها می‌تونیم به جای یک خونه جلو رفتن kتا خونه به جلو بریم و k ضلع مربعی هست که انتخاب شده تا در این مرحله مستطیل رو پوشش بده. این حرکت و هرس کردن حالت‌هایی که بیشتر از جواب فعلی میشن و ادامه ندادن اونها٬ مثال‌های از بهینه سازی این راه حله. اما یک کار دیگه هم میشه کرد که من فقط عنوان می‌کنم و اگر فکر کردید نیازه تو کامنت‌ها بگید توضیح بدم. اینکه میشه به جای نگه داشتن یک ماتریس Boolean برای فهمیدن اینکه چه خونه‌ای قبلا پر شده میشه از یک آرایه به طول ردیف‌هامون استفاده کرد و استیت رو به شکل یک bitmask نگهداری کرد. به این ترتیب در هر ردیف تعدادی از ستون‌های اون ردیف پر هستند و تعداد خالی. مثلا اگر ۴ ردیف و ۵ ستون داشته باشیم و یک مربع ۳*۳ رو طوری قرار بدیم که گوشه بالا و چپ روی (0,0) ماتریس باشه٬ ردیف‌های صفرم٬ اول و دوم تعدادی ستون پر دارند. چه ستون‌هایی؟ ستون‌های صفرم و اول و دوم پر هستند. [111,111,111,000] یعنی ردیف صفرم٬ اول و دوم سه ستون پر دارند و ردیف سوم هیچ ستون پری نداره.

حل سوال 1915 لیت کد

نسیم نژند — Thu, 09 May 2024 23:43:31 +0330

هفته پیش یکی از سوالات روزانه لیت کد سوالی بود با عنوان Number of wonderful substrings. اگر با این سوال آشنایی ندارین حتما یک بار سوال و مثال هاش رو بخونید و بعد برگردید. من درباره این سوال توضیح های متنوعی خوندم اما اون طور که باید نتونستم با هیچ کدوم ارتباط بگیرم و بگم آهان! کاملا قابل فهمه. برای همین خودم سعی کردم به جواب برسم و با زبان خودم توضیح بدم.این سوال در واقع مثل یک راه حل brute force قرار نیست تمام حالات ممکن رو ایجاد کنه و بعد از بین اونها انتخاب کنه یا حتی بهینه تر فکر کنه و صرفا حرص بیشتری انجام بده. درباره این سوال کلا باید شکل دیگری فکر کرد. چرا؟‌چون طول رشته میتونه حداکثر ده به توان پنج باشه پس حتما باید به فکر یه راه حل خطی یا نزدیک به خطی باشیم. سوال از ما میخواد تعداد زیر رشته هایی که حداکثر یک تکرار فرد رو دارند رو پیدا کنیم. در قدم اول خود این یعنی مسئله در دو قسمت باید حل شه.· رشته ای بدون تکرار فرد. یعنی همه کارکترها فقط زوج بار تکرار شده باشند مثل “aabb”· رشته ای فقط با یک تکرار فرد. یعنی فقط یک کاراکتر اجازه داره فرد بار تکرار شه. مثل “aba”وقتی میخوایم مثال بزنیم فرقی نداره هر مثالی میشه زد و فقط زوجیت و فرد بودن تکرارها حائز اهمیته. مثلا چه بگیم “abaaabb” چه بگیم “aba” در هر دو٬ حرف a زوج بار تکرار شده و حرف b فرد بار تکرار شده. پس وقتی هم بخوایم بفهمیم تا یک پوزیشن مشخص از رشته چه زیررشته هایی میشه ساخت کافیه بفهمیم با چه پترنی رو به رو هستیم. در ادامه بیشتر این بخش توضیح داده میشه.تا همین قسمت یک نکته جالب وجود داره. ما با یک مشخصه مثل زوج یا فرد سر کار داریم. هر عددی یا زوجه یا فرد پس به سادگی میتونیم نگاه بیتی بهش داشته باشیم و بگیم زوج بار تکرار رو صفر در نظر میگیریم و فرد بار تکرار رو یک. چرا؟ چون اگه مثلا اگر یک رشته خالی داشته باشیم و بخوایم اون رو به صورت بیتی نشون بدیم صفر کافیه چون صفر بار تکرار زوجه. چرا حالت پایه رو رشته خالی در نظر گرفتیم؟ چون همیشه برای حالت پایه آسون ترین حالت رو در نظر میگیریم.یه ویژگی خوب دیگه در این سوال اینه که گفته حروف a تا j در هر رشته وجود دارند. یعنی در کل به ده تا پوزیشن مختلف نیاز داریم. میتونیم بگیم ده تا بیت. بیت اول رو برای a در نظر میگیریم٬ بیت دوم برای b و به همین ترتیب.مثال: اگر بخوایم تعداد تکرار حروف در رشته “abaecebb” رو به این روش نشون بدیم باید بگیم:e d c b a2 0 1 3 20 0 1 1 0بقیه کاراکترهایی که وجود ندارند هم صفر هستند. در قدم اول همه بیت ها صفر هستند و ما به هر حرفی که برسیم میتونیم بیتش رو برعکس کنیم.حالا یک نکته وجود داره جالب تر از همه نکات قبلی! اینکه ما میتونیم برای حالت ها الگو پیدا کنیم. دوتا حالت برای ما مطلوبه:‌۱) همه کاراکترها زوج تکرار ۲) فقط یکی از کاراکترها فرد تکرارقبول دارین که اگر در یک رشته همه کاراکترها زوج بار تکرار شن بیت متناظر همه شون صفر میشه؟‌ اگر قبول ندارین هم اشکالی نداره میتونین یه مثال برای خودتون روی کاغذ بزنین. به ویژگی xor هم نیاز داریم. اگر شما هر چیزی رو با صفر xor کنید به زیبایی همون بیت اولی رو مشاهده میکنین. پس اگر مثلا تا یک ایندکسی به پترن 010 رسیدم و در یک ایندکسی بعد از این هم به پترن 010 رسیدم یعنی این بین یک بخش تماما زوج تکرار داشتم که خوشحالم میکنه و بخشی از جوابه. به تصویر دقت کنید‌:الگوی زوج تکراربه بیان بهتر٬ اگر من یک الگوی تکراری ببینم پس بخشی از جواب رو پیدا کردم. در نتیجه هر پترنی رو ببینم ذخیره میکنم.شاید اگر به همین روش فکر کردن ادامه بدیم بتونیم بقیه جواب رو هم به دست بیاریم. شرایط بعدی رشته ای که میتونه جواب باشه چیه؟‌ فقط یک کاراکتر فرد بار تکرار شه. واقعا عالیه پس کافیه دوتا الگو در یک بیت متفاوت باشند. برای اینکه بهتر منظورم رو متوجه شین لطفا به تصویر زیر دقت کنید:الگوی یک حرف با فرد بار تکراربرای اینکه بهتر بتونین باهاش ارتباط برقرار کنید لطفا از قلم و کاغذ استفاده کنید تا خودتون با چندتا مثال تجربه کنید واقعا این حالت ها برقراره.پس این الگو هم که ببینیم پترنی که در یک ایندکس ایجاد شده با چندتا از پترن های قبلی در یک بیت تفاوت داره٬ به درد میخوره.حالا تا حدی با ایده آشنا شدیم بیاین برای یک مثال دست به تریس شیم و ادامه بدیم. سعی کنید از روی تریس کدش رو بزنید.در هر مرحله منظور از mask همون الگویی هست که در هر مرحله از iteration بهش میرسیم. همونطور که بالاتر توضیح دادم الگوهایی که می بینیم رو لازم داریم و به همین دلیل اونها رو در یک map یا آرایه ذخیره میکنیم. متغیر ans هم مشخصا مقدار جواب هست که اگر شرایطی که توضیح دادم پیش بیاد آپدیت میشه.مثال رو برای رشته aabb شروع میکنیم. توجه کنید در هر مرحله اول چک میکنیم اگر این الگو رو قبلا دیدیم پس پترن همه تکرار زوج وجود داره. در ادامه چک میکنیم آیا قبلا الگویی دیدیم که فقط یک حرف فرد بار تکرار شده باشه؟لطفا بعد از اینکه خودتون سعی کردین به کد زیر هم نگاهی بندازین.https://gist.github.com/NasimNajand/592eb6858ffaa89a2df1df93308b29c3هر سوالی داشتین حتما تو کامنت ها بپرسین.

حل قدم به قدم مسئله هانوی

نسیم نژند — Thu, 22 Dec 2022 13:12:00 +0330

وقتی میخواین بازگشتی رو برای کسی توضیح بدین شاید اولین مثالی که به ذهن شما میرسه مسئله هانوی نباشه ولی قطعا یکی از مثال های معروف هست. اما شاید برای کسی که تازه میخواد این مفهوم رو یاد بگیره توضیح ساده ای وجود نداشته باشه. مسئله هانوی دو تا قانون اصلی داره:۱.در هر مرحله فقط مجاز به جابجایی یک دیسک هستیم.۲.هیچ دیسکی با شعاع بزرگتر نباید روی دیسکی با شعاع کوچکتر قرار بگیره.با رعایت این دو قانون باید بازی رو ادامه بدیم و با کمترین تعداد جابجایی n دیسک رو از استک مبدا با استفاده از استک کمکی٬ به استک مقصد ببریم.در این پست میخوام به شکل ساده تری براتون توضیح بدم در مسیر حل این مسئله به روش recursive دقیقا چه اتفاقی میفته. میتونین از سایت mathisfun استفاده کنید و با استفاده از سه میله و n دیسک دلخواه حالت های مختلف رو امتحان کنید. اولین قدمی که در حل این سوال به فکرمون میرسه حل کردن به کمک اعداد کوچکه.مثلا اگر فقط یک دیسک داشته باشیم راه حل ساده ست. کافیه این دیسک رو از استک مبدا به مقصد منتقل کنیم و تمام. اگر دو دیسک داشته باشیم چی؟ بذارین دیسک ها رو به ترتیب بزرگی شعاع٬ با عدد مشخص کنیم٬ به این ترتیب که کوچک ترین دیسک رو با عدد یک و بزرگ ترین دیسک رو با عدد n شماره گزاری کنیم. دیسک ۱ رو به میله کمکی میبریم. به این ترتیب در استک مبدا یک دیسک باقی میمونه و میتونیم به سادگی دیسک ۲ رو به مقصد منتقل کنیم. در آخرین قدم هم دیسک ۱ رو از کمکی به مقصد میبریم.حالتی که سه دیسک داشته باشیم تعداد حرکت ها بیشتر میشه. در تصویر زیر هر مرحله رسم شده. به جابجایی هر دیسک در هر مرحله توجه کنید.هم در حالتی که دو دیسک داریم و هم در حالتی که سه دیسک داریم در واقع تلاش میکنیم بزرگترین دیسک در مبدا تنها بشه چرا که وقتی به این مرحله برسیم٬ مثل وقتی که یک دیسک داریم میتونیم بزرگترین دیسک رو به مقصد منتقل کنیم. این مرحله یک ویژگی دیگه هم داره. n-1 دیسک در میله کمکی قرار میگیرند. ابتدا بزرگ ترین دیسک رو به مقصد منتقل میکنیم و بعد n-1 دیسکی که روی کمکی قرار گرفتند رو به مقصد میبریم.در واقع این مسئله از سه قسمت اصلی تشکیل میشه :ساختن n-1 دیسک روی استک کمکیانتقال بزرگ ترین دیسک به مقصدانتقال n-1 دیسکی که روی میله کمکی ساختیم به میله مقصدحالا میتونیم همین سه خط رو به کد تبدیل کنیم. مادامی که میله مبدا یک دیسک نداره n-1 دیسک رو از مبدا به کمکی منتقل می کنیم. چرا n-1 ؟ چون میخوایم بزرگترین دیسک در مبدا تنها بشه تا به مقصد منتقل شه. بعد از این مرحله کافیه n-1 دیسک رو از کمکی به مقصد ببریم.void T(char from, char to, char help, int n){ if (n == 1) { cout << n << ' ' << from << ' ' << to << '\n'; return; } // first recursive call T(from, help, to, n-1); cout << n << ' ' << from << ' ' << to << '\n'; // second recursive call T(help, to, from, n-1);}برای اینکه این کد و نحوه فراخوانی های بازگشتی واضح بشه با هم مسئله رو برای n=4 تریس میکنیم. از روی تصویر زیر قدم به قدم با هم پیش میریم. قبل از ادامه دقت کنید وقتی میخوایم مبدا و مقصد و کمکی رو در هر مرحله مشخص کنیم٬ برای مرحله n به مرحله n+1 توجه میکنیم. یعنی در مرحله n+1 چه ستونی مبدا، چه ستونی مقصد و کدوم کمکی هست. مثلا وقتی (T(2,a,c,b کال شده و میخوایم نسخه های n=1 رو بسازیم٬ مرجع فراخوانی n=2 میشه٬ که در اون کمکی b هست و چون ما میخوایم اولین فراخوانی بازگشتی رو بسازیم باید n-1 دیسک رو به استک کمکی ببریم. با دونستن این نکته ادامه ادامه میدیم.اولین نسخه از فراخوانی متد (T(4,a,c,b هست که یعنی میخوایم ۴ دیسک رو از مبدا a به مقصد c با کمک b ببریم. به ترتیب:a: مبداc: مقصدb: کمکیاین نسخه از فراخوانی متد در استک ساخته میشه. اول چک میکنه ایا تعداد دیسک ها برابر با یک شده. اگر نه باید اولین فراخوانی بازگشتی کال بشه. یعنی (T(3,a,b,c یا بهتر بگم n-1 دیسک رو از a ببر به b به کمک c.‍خب این نسخه از متد هم ساخته میشه و دوباره متد خط به خط پیش میره تا میرسه به اولین فراخوانی بازگشتی. قراره یکی از تعداد دیسک ها کم بشه اما دقت کنید وقتی n=3 بود مبدا a و مقصد b بود. پس در اولین فراخوانی بازگشتی برای n=2 فراخوانی میشه: (T(2,a,c,b. باید دیسک ها رو از مبدا به کمکی ببریم یعنی از a به c به کمک b.این نسخه هم اجرا میشه و چون هنوز تعداد دیسک های این فراخوانی برابر با یک نشده ادامه میدیم و میرسیم به فراخوانی بازگشتی اول. باز هم دقت کنید وقتی به این خط میرسیم در نسخه ای قرار داریم که میخواد دو دیسک رو از a به c ببره. در نتیجه این بار با چه مقادیری تابع فراخوانی میشه؟‌ بله درسته (T(1,a,b,c که به سادگی میگه n-1 دیسک رو از مبدا ببر به کمکی. مبدا کیه؟ در این مرحله a کمکی؟‌bاین نسخه هم متد رو فراخوانی میکنه. عالی شد n=1 هست و base case برقرار شد. پس مسئله برای (T(1,a,b,c حل شد و از استک پاپ میشه. نسخه ای که در استک زیر این فراخوانی قرار داشته: (T(2,a,c,bاین متد تا خطی که اولین فراخوانی بازگشتی رو انجام میده اجرا شده پس میره سراغ بقیه لاین ها. دستور بعدی چاپ مبدا و مقصد جابجایی انجام شده هست. یعنی دومین جابجایی که چاپ میشه برابر با a->c هست. بریم سراغ دومین فراخوانی بازگشتی در این نسخه. یکی از تعداد دیسک ها کم میکنیم و میشه یک دیسک. اما از کدوم ستون به کدوم ستون میریم. در این مرحله ابتدا دیسک ها رو از a به c بردیم حالا باید از c به مقصد ببریم. مقصد رو با مقصد اولیه که موقع اولین فراخوانی متد در نظر گرفتیم اشتباه نکنید. مرجع شما در این مرحله n=2 هست که میخواسته دو دیسک رو از a به c ببره به کمک b.پس دومین فراخوانی بازگشتی باید n-1 دیسکی که از مبدا به کمکی رفته رو از کمکی به مقصد ببره. (سه مرحله کلی که برای حل سوال مشخص کردیم رو به یاد دارید؟) در نتیجه این فراخوانی هست T(1,b,c,a)چون در این فراخوانی تعداد دیسک ها برابر با یک هست وارد شرط پایه میشیم و جابجایی چاپ میشه این زیرمسئله هم حل میشه. با حل شدن این استپ (T(2,a,c,bفراخوانی هم از استک پاپ میشه و روترین نسخه از فراخوانی ها که باقی مونده٬ (T(3,a,b,c هست. حالا شما ادامه مسیر رو با توضیحاتی که دادم تریس کنید و هم چنین مسئله رو برای n متفاوتی حل کنید.پیشنهاد میکنم این مسئله رو به صورت غیربازگشتی هم حل کنید و اگر دوست داشتید در کامنت ها بگین که یک مقاله هم در این باره بنویسم.