عادامس

سلام

یه تعداد کمی سوال ازین داده ساختارای ابتدایی میذارم، ملاکم هم برای انتخابشون چیز خاصی نبوده :D یه تعدادیشون قشنگ بودن، یه تعدادیشون هم به عنوان زیرمسئله توی یه سری سوالای برنامه نویسی مطرح میشن گاهی. حلشون کنید، کدشونم بزنید، باشد که رستگار شویم :-)

۱- یه Stack رو با استفاده از ۲ تا Queue پیاده سازی کنید. اگه n تا عنصر توی stack ریخته بشن، اول یه الگوریتم از O(n²) بدید، بعدش یه الگوریتم بدید از O(n).

۲- یه Queue رو با استفاده از ۲ تا Stack پیاده سازی کنید. اردرش هم مثله سوال اول باشه :دی

(پیاده سازی کردن داده ساختار X یعنی این که فرض کنید سی پلاس پلاس X رو نداره و شما با ابزاری که بهتون داده شده باید یه دونه X بسازید)

۳-

الف) توی آرایه ی A با سایز n، به ازای هر اندیس مجاز i، بزرگترین j رو پیدا کنید که

j < i     &     a[j] < a[i]

please O(n) :D

ب) یه ماتریس N * M از اعداد صفر و یک بهتون داده شده. بزرگترین زیرمستطیل رو توش پیدا کنید که همه ی خونه هاش صفر باشن.

O(N * M) :D

ج) سوال 547B کدفورسز

۴- یه رشته S به طول n از کاراکتر های ')' و '(' به شما داده شده.

الف) بگید که آیا S یه پرانتز گذاری معتبر هست یا نه

O(n)

ب) طول بزرگترین زیر رشته از S که پرانتز گذاری معتبر هست رو پیدا کنید. اردر زمان اجرای الگوریتمتون مثل قسمت الف باشه.

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

د) سوال 223A کدفورسز

ه) سوال 5C کدفورسز

۵- Monotonic Queue: یه آرایه ی A شامل n عدد دارید.

الف) عدد k رو به شما میدیم و میخایم که به ازای هر k خانه ی متوالی از آرایه، عنصر بیشینه را چاپ کنید.

O(n)

ب) q تا کوئری بهتون میدیم. هر کوئری یه بازه است و شما باید عنصر بیشینه ی اون بازه از آرایه ی A رو چاپ کنید. یه محدودیت روی کوئری ها داریم و اون اینه که خونه ی ابتدایی بازه ی هر کوئری، بعد از خونه ی ابتدایی کوئری قبلی هستش و خونه ی انتهای هر کوئری، بعد از خونه ی انتهای کوئری قبلیه. به عبارت دیگه اگه هر کوئری رو با L_i و R_i نشون بدیم، L_i >= L_{i - 1} و R_i >= R_{i - 1}

O(n + q)

ج) سوال 487B کدفورسز

د) سوال 372C کدفورسز