كيف ولماذا يصطف على مداخن اثنين

مرحبا يا هبر!

كُتب هذا المنشور للمبتدئين في البرمجة الأولمبية ومطوري المبتدئين الذين يستعدون للخضوع لمقابلات خوارزمية. في نهاية لغز المكافأة. إذا كانت مهتمة ، أطلب قطة :)

أولاً ، دعنا نتذكر الأساسيات:

كومة

المكدس بتنفيذ مبدأ LIFO (المهندس. آخر في - أولاً ، "آخر يأتي ، يأتي أولاً").

يحتوي المكدس على عمليتين رئيسيتين:

• ادفع - ادفع عنصرًا إلى المكدس
• البوب ​​- الحصول على عنصر من المكدس

عادةً ما يتم تطبيق المكدس على صفيف (لا يزال ممكناً في قائمة مرتبطة). يمكنك قراءة المزيد حول المكدس وتنفيذه هنا.

تحويل

قائمة الانتظار هي بنية بيانات مع إمكانية الوصول إلى عناصر FIFO (أولاً في ، أولاً - "من يأتي أولاً ، أولاً")

قائمة الانتظار طريقتان رئيسيتان في واجهة:

• دفع - وضع عنصر في نهاية قائمة الانتظار
• pop - احصل على عنصر من مقدمة قائمة الانتظار

اقرأ المزيد عن قائمة الانتظار العادية هنا .

عادة ما تنظر في طريقتين أساسيتين لتنفيذ قائمة الانتظار:

1. على مجموعة
2. على قائمة مرتبطة

لماذا هو المكدس أكثر برودة من الخط

تخيل أن بنية بياناتنا يجب أن تدعم مجموعة العمليات التالية:

• الحد الأدنى من الدعم (دقيقة)
• أقصى دعم (كحد أقصى)
• دعم Gcd (الإنجليزية أكبر المقسومات المشتركة - أكبر المقسوم المشترك)
• دعم LCM (المضاعفات المشتركة الأقل)

كل هذه العمليات مرتبطة ببعضها البعض (تشكل مجموعة شبه) ، لكن أياً منها لا يحتوي على عنصر معكوس (لا يشكل مجموعة).

للمكدس ، يمكنك ببساطة دعم أي من العمليات التالية: فقط قم بتخزين زوجين في قمته:

$$

$$(element، operationResult)$$

حيث العنصر الثاني من الزوج هو نتيجة العملية المطبقة على جميع عناصر المكدس.

فيما يلي مثال لتطبيق الحد الأدنى من دعم المكدس في بيثون:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

الآن فكر في كيفية القيام بنفس الخدعة مع قائمة الانتظار؟ إذا حاولت استخدام قائمة انتظار كلاسيكية مرتبة على صفيف ، فمن غير المحتمل أن ينجح شيء ما. هذا يرجع إلى حقيقة أن الحد الأدنى من العملية لا يحتوي على العملية العكسية (مثل عملية الإضافة لديها عملية الطرح ، على سبيل المثال). كما كنت قد خمنت ، ثم سأتحدث عن التنفيذ غير الكلاسيكي لقائمة انتظار على مجموعتين.

قائمة انتظار مكدس اثنين

الشرط الرئيسي الذي يجب الوفاء به هو أن جميع العمليات يجب أن يتم تنفيذها للإطفاء O (1).

خذ مكدسين: s1 و s2.

سيتم دائمًا تنفيذ عملية الدفع على مكدس s1.

سيتم تنظيم العملية المنبثقة على النحو التالي: إذا كانت مكدس s2 فارغة ، فنحن ننقل جميع العناصر من s1 إلى s2 عن طريق مكالمات متتالية إلى pop و push. الآن يحتوي مكدس s2 على عناصر بالترتيب العكسي (العنصر الأعلى هو العنصر الأول في دورنا).

إذا لم تكن s2 فارغة ، فنحن نحصل عليها بغباء. بمجرد أن s2 فارغ مرة أخرى ، نكرر نفس العملية.

رمز بايثون:

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

وقت العمل

دفع العملية : نحن ندفع بغباء عنصر على مكدس s1. وقت التشغيل يا (1).

التشغيل المنبثق : بالنسبة لكل عنصر ، لا نقوم بأكثر من عملية نقل واحدة من المكدس إلى المكدس ، وبالتالي ، فإن وقت العمل المطفأ سيكون O (1).

get_min العملية : يُعرف minima بكميات s1 و s2 ، لذلك نحن نأخذ الحد الأدنى من minima. وقت التشغيل يا (1).

مكافأة التحدي

إعطاء سلسلة من الأرقام N. يتم إعطاء الرقم M <N ، وهو مطلوب في الوقت الخطي للعثور على قطعة طولها M يكون فيها المنتج min * max أقصى.

استنتاج

شكرا لك على القراءة حتى النهاية!

إذا كنت مهتمًا بالموضوع ، يمكنك قراءة كيفية إنشاء قائمة انتظار دائمة على مكدسين هنا ، أو انتظار إصدار موضوعي التالي.

اكتب في التعليقات ما هي المهام على مجموعتين كان عليك حلهما في المقابلات أو المسابقات.