امروز ما در مورد سری محبوب مشکلات LeetCode مربوط به خرید و فروش سهام بحث خواهیم کرد. با نگاهی به این مشکلات ، به ما کمک می کند تا درک کنیم که چگونه آنها با یکدیگر تفاوت دارند و چگونه برای حل آنها باید نزدیک شویم. بیشتر آنها تحت برنامه نویسی پویا در Leetcode برچسب گذاری شده اند. من از Python 3 برای همه راه حل ها استفاده کرده ام. بدون هیچ تاخیری ، ما به آنجا می رویم.

121. بهترین زمان برای خرید و فروش سهام

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

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

آیا یک راه حل پاس وجود دارد؟

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

122. بهترین زمان برای خرید و فروش سهام II

پیوند مشکل آنچه جدید است این است که در این مشکل می توانیم چندین سهام (بدون حد بالایی) بخریم تا سود را بر خلاف تنها یک مورد در گذشته به حداکثر برسانیم. اما حداکثر یک سهام می تواند همیشه در دست باشد.

جالب اینجاست که مشکل را می توان فقط به عنوان محاسبه Uplopes مشاهده کرد. بنابراین فقط مجموع اختلافات بین قله ها و دره ها. o با استفاده از برخی موارد آزمایش دیگر ، می فهمیم که Upslopes را می توان به جمع بسیاری از فرازهای کوچکتر تقسیم کرد. به نمودار زیر مراجعه کنید ، از مقاله LeetCode گرفته شده است.

از این شکل می توانیم ببینیم که a+b+c = d. بنابراین اگر ما A ، B ، C و غیره را محاسبه کنیم و به آنها اضافه کنیم ، در نهایت باید مجموع دامنه های سربالایی را بدست آوریم. برای ورودی مورد تست فوق [1 ، 7 ، 2 ، 3 ، 6 ، 7 ، 6 ، 7] خروجی مورد انتظار 12 است زیرا 6+0+1+3+1+0+1 = 12. فقط انتقال این ایده ساده به کد ما دریافت می کنیم.

123. بهترین زمان برای خرید و فروش سهام III

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

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

سود نهایی = (سود اولیه— قیمت خرید )+ قیمت فروش

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

First Buy > First Sell > Second Buy >فروش دومبهترین راه برای فروش سهام دوم (فروش دوم) =سود نهایی

می توانیم آرایه را پردازش کنیم و فرض کنیم که در هر مورد بهترین نتیجه را برای متغیر قبلی در دنباله داریم. بر این اساس می توانیم الگوریتمی را طراحی کنیم که در زیر نشان داده شده است.

ابتدا تمام متغیرها را مقداردهی اولیه می کنیم. سپس آرایه قیمت ها را تکرار می کنیم و بررسی می کنیم که آیا می توانیم سهام فعلی را بخریم تا سود را به حداکثر برسانیم. سپس بررسی می کنیم که آیا می توانیم آن را فوراً بفروشیم یا پس از آن، بنابراین قیمت سهام را اضافه می کنیم و بررسی می کنیم که آیا می توانیم اولین معامله را به حداکثر برسانیم. بر اساس تراکنش اول، تراکنش دوم را ادامه می دهیم و به طور مشابه با آن کار می کنیم. به جدول زیر که برای ورودی تولید شده است نگاه کنید [3،3،5،0،0،3،1،4]

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

188. بهترین زمان برای خرید و فروش سهام IV

لینک مشکل این بار ما مجاز به خرید حداکثر k سهام هستیم. بیایید در مورد تفاوت این مشکل با مشکل قبلی (#123) فکر کنیم. قبلا هم همین هدف را داشتیم اما می توانستیم حداکثر دو سهم بخریم. اکنون به تعمیم آن برای K سهام فکر کنید. دقیقاً به k متغیرهایی فکر کنید که حالت های قبلی ما را نگه می دارند. ساختار داده فوری که در ذهن ما می آید یک آرایه است. ما می توانیم از دو آرایه به طول k برای پیگیری سود خرید و فروش استفاده کنیم. ما منطق را یکسان نگه می داریم و قسمت داخل حلقه را تعمیم می دهیم.

توجه کنید که چگونه ما یک چک اضافی را برای رسیدگی به پرونده اضافه کردیم که K = 0 (حداکثر می توانیم سهام صفر بخریم). همچنین ، بررسی کنید که چگونه من Zeroth Buy و Sell را در خارج از حلقه داخلی انجام دادم تا کد ساده و تمیز نگه داشته شود زیرا نمی توانم در هنگام J 0 به فروش [J-1] دسترسی پیدا کنم ، که از نظر فنی باید صفر باشد. راه دیگر برای رسیدگی به این امر خواهد بود.

خرید [j] = حداکثر (خرید [j] ، (sell[j-1] if j>0 other 0) -Prices [i])فروش [j] =. همان چیزی که در تصویر بالا نشان داده شده است. 

به اندازه کافی منصفانه! ما فقط راه حل خود را از #123 از K = 2 تا K = هر چیزی تعمیم دادیم. اگر سعی کنید این موضوع را ارسال کنید ، اگرچه منطق ما صحیح است ، ما از خطای زمان/حافظه فراتر می رود. بیایید این را درک کنیم

در مورد بررسی پرونده آزمون ، متوجه می شویم که ارزش k 1000000000 است. ما نمی توانیم دو آرایه را بسیار بزرگ تعریف کنیم ، به هیچ وجه!

بگذارید عقلانی فکر کنیم ، اگر با توجه به اینکه چه تعداد معاملات حداکثر می توانیم انجام دهیم؟… این کف (n/2) است. باور نکن؟خوب

روز 1 را بخرید ، در روز 2 بفروشیدروز 3 را بخرید ، در روز 4 بفروشید. . روز n-1 را بخرید ، در روز n بفروشیدواضح است ، کف (n/2) معاملات کامل

بنابراین ، هنگامی که مقدار K از N/2 بیشتر باشد ، مشکل شبیه به شماره 122 است زیرا قسمت بالایی بی نهایت است و می توانیم چندین سهام را بخریم و بفروشیم (پیروی از محدودیت: پس از فروش قبلی سهام بخرید).

این همه 211 مورد آزمایش را با حاشیه خوب می گذراند. یااای

309. بهترین زمان برای خرید و فروش سهام با Cooldown

پیوند مشکل این مشکل شبیه به شماره 122 است که در آن می توانیم در چندین معاملات شرکت کنیم. یکی دیگر از شرایط اضافی جدید این مشکل این است که پس از فروش سهام اکنون به شما اجازه می دهید تا 1 روز آینده سهام خریداری کنید که از آن به عنوان Cooldown یاد می شود.

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

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

مواردی که باید از راه حل فوق توجه داشته باشید:

1) در زمان خطی و فضای خطی اجرا می شود 2) خرید [0] ب ه-Prices [0] (منهای قیمت سهام اول) آغاز می شود ، زیرا ما فرض می کنیم اولین سهام را در پایان روز اول 3 خریداری کرده ایم) خرید [i] = حداکثر (خرید [i-1] ، فروش [i-2] -prices [i]) این نشان می دهد که ما نمی توانیم سهام جدیدی بخریم (باقی مانده است که بخرید [i-1]) در روز 'من با توجه به اینکه روز گذشته برای Cooldown (فروش [I-2]+قیمت) از آن استفاده می شود ، سهام خریداری می کنم. 4) چنین شرایطی برای فروش وجود ندارد زیرا ما می توانیم پس از خرید بلافاصله روز بعد سهام را بفروشیم (خرید [I-1]+قیمت) یا فقط روز را پرش کنیم (بفروشید [I-1]).

آیا راهی برای بهینه سازی راه حل وجود دارد؟

ما نمی توانیم زمان اجرا را بهبود بخشیم (بدون علامت) ، اما با نگاهی به آرایه می بینیم که ما واقعاً از کل آرایه در هر نمونه از زمان در الگوریتم استفاده نمی کنیم. ما فقط به خرید [i-1] دسترسی پیدا می کنیم ، [i-2] را هنگام پردازش [i] می فروشیم و [i-1] را هنگام پردازش فروش [i] می فروشیم. واضح است که می توانیم با استفاده از متغیرها ، فضای مصرفی الگوریتم خود را کاهش دهیم. بیایید نگاهی به الگوریتم جدید بیندازیم ، هرچند که قبلاً زیبا نیست.

ما از متغیرهای buy_0 ، sell_0 ، buy_1 ، sell_1 ، sell_2 استفاده کردیم تا از ایالات قبلی برای معاملات مربوطه پیگیری کنیم. روش های مختلفی برای انجام این بهینه سازی فضا وجود دارد ، هر آنچه برای شما طبیعی به نظر می رسد ، باید با آن پیش بروید. برای کد من ، ایدئولوژی بود

خرید [i-0] = buy_0خرید [i-1] = buy_1فروش [i-0] = sell_0فروش [i-1] = sell_1فروش [i-2] = sell_2از آنجا که این تنها کشورهایی هستند که ما در حال ذخیره و استفاده مجدد هستیم ، بله بدیهی است که DP است.(برنامه نویسی پویا)

714. بهترین زمان برای خرید و فروش سهام با هزینه معامله

چه چیز جدیدی در مورد این مشکل وجود دارد؟تفاوت آن با موارد قبلی چگونه است.

هزینه پنالتی در ارتباط با هر سهام دیگری که خریداری می کنید جدا از قیمت سهام است. شما مجاز به خرید چندین سهام (بی نهایت) با حداکثر یک سهام در دست هستید.

شما ممکن است در مورد تکرار کد از شماره 122 با این اصلاح فکر کنید.

سود += حداکثر ((قیمت [i] -Prices [i-1])-با ، 0)

اما ، بگذارید بحث کنیم که چرا این کار نمی کند.

پیش از این در شماره 122 ما هیچ هزینه ای در ارتباط با هر معامله نداشتیم. ما فقط مجبور شدیم سود (در صورت وجود) را بین هر معامله متوالی محاسبه کنیم. ما قبلاً بحث کردیم که چرا محاسبه سود متوالی در پایان به سود بزرگی می افزاید. اما در اینجا ، این یک چیز مشابه نیست ، در برخی شرایط هزینه مرتبط با یک معامله می تواند بیشتر از سود خود باشد. این ما را از استفاده از رویکرد #122 مستلزم آن می کند. در عوض ، ما روی راه حل شماره 309 کار می کنیم و آن را برای این مشکل اصلاح می کنیم. در زیر کد است.

توجه داشته باشید ، از آنجا که هیچ Cooldown در ارتباط نیست ، ما می توانیم بلافاصله پس از فروش یکی از سهام را خریداری کنیم (بنابراین S [I-1] -Prices [i] -fee). این یک زمان خطی و راه حل خطی است ، اجازه دهید سعی کنیم آن را به یک راه حل فضای ثابت بهینه کنیم ، همانطور که قبلاً در شماره 309 انجام دادیم.

بینگو! ما همه این کار را کردیممن مطمئن هستم که اکنون شما با چنین مشکلاتی کمی اعتماد به نفس دارید. چه می شود اگر ما مجبور شدیم بعد از این سؤال دیگری را در این سری از بهترین زمان برای خرید و فروش سهام طراحی کنیم. به نظر شما چه چیزی باید باشد؟

در زیر بنویسید ، دوست دارم تعامل داشته باشم. همچنین ، من از چند چاشنی بسیار قدردانی می کنم.:) برنامه نویسی مبارک!

Liked reading my stories? If you are in the mood to buy me a beer>>buymeacoffee. com/amitrajit