860. تغيير عصير الليمون

الصعوبة: سهل

المواضيع: المصفوفة، الجشع

في كشك بيع عصير الليمون، تبلغ تكلفة عصير الليمون الواحد 5 دولارات. يقف العملاء في طابور للشراء منك ويطلبون واحدًا تلو الآخر (بالترتيب المحدد في الفواتير). سيشتري كل عميل عصير ليمونة واحد فقط ويدفع بفاتورة بقيمة 5 دولارات أو 10 دولارات أو 20 دولارًا. يجب عليك تقديم التغيير الصحيح لكل عميل بحيث يكون صافي المعاملة هو أن يدفع العميل 5 دولارات.

ملاحظة أنه ليس لديك أي تغيير في متناول اليد في البداية.

بالنظر إلى عدد صحيح من الفواتير حيث Bills[i] هي الفاتورة التي يدفعها العميل i^{، قم بإرجاع} صحيح إذا كان بإمكانك تزويد كل عميل بالتغيير الصحيح، أو خطأ بخلاف ذلك .

مثال 1:

• الإدخال: الفواتير = [5,5,5,10,20]
• الإخراج: صحيح
• توضيح:
  من أول 3 عملاء، نقوم بجمع ثلاث فواتير بقيمة 5 دولارات بالترتيب.
  من العميل الرابع، نجمع فاتورة بقيمة 10 دولارات ونعيد لها 5 دولارات.
  من العميل الخامس، نعطيه فاتورة بقيمة 10 دولارات وفاتورة بقيمة 5 دولارات.
  بما أن جميع العملاء حصلوا على التغيير الصحيح، فإننا ننتج صحيحًا.

مثال 2:

• الإدخال: الفواتير = [5,5,10,10,20]
• الإخراج: خطأ
• توضيح:
  من أول عميلين بالترتيب، نقوم بتحصيل فاتورتين بقيمة 5 دولارات.
  بالنسبة للعميلين التاليين بالترتيب، نقوم بجمع فاتورة بقيمة 10 دولارات وإرجاع فاتورة بقيمة 5 دولارات.
  بالنسبة للعميل الأخير، لا يمكننا إعادة المبلغ المتبقي وقدره 15 دولارًا لأنه ليس لدينا سوى فاتورتين بقيمة 10 دولارات.
  نظرًا لعدم حصول كل العملاء على التغيير الصحيح، فإن الإجابة خاطئة.

قيود:

5
الفواتير[i] هي إما 5 أو 10 أو 20.

حل:

نحتاج إلى محاكاة عملية توفير التغيير للعملاء بناءً على الفواتير التي يستخدمونها للدفع. المفتاح هو تتبع عدد الأوراق النقدية بقيمة 5 دولارات و10 دولارات لديك، حيث إنها ضرورية لتوفير التغيير للفواتير الأكبر حجمًا

لننفذ هذا الحل بلغة PHP:

860. تغيير عصير الليمون

توضيح:

1. التهيئة: نبدأ بخمسة دولارات وعشرة دولارات مضبوطة على 0، مما يمثل عدد الأوراق النقدية التي لدينا من 5 دولارات و10 دولارات.

2. معالجة كل فاتورة:

   • إذا دفع العميل بفاتورة بقيمة 5 دولارات: نقوم ببساطة بزيادة عدد الفواتير بقيمة 5 دولارات.
   • إذا كان العميل يدفع بفاتورة بقيمة 10 دولارات: نحتاج إلى إعادة فاتورة واحدة بقيمة 5 دولارات كتغيير، لذلك نقوم بتقليل عدد الفواتير بقيمة 5 دولارات وزيادة عدد الفواتير بقيمة 10 دولارات. إذا لم يكن لدينا أي أوراق نقدية بقيمة 5 دولارات، قم بإرجاعها كاذبة.
   • إذا كان العميل يدفع بفاتورة بقيمة 20 دولارًا أمريكيًا: فإننا نعطي الأولوية لإعطاء فاتورة واحدة بقيمة 10 دولارات أمريكية وفاتورة واحدة بقيمة 5 دولارات أمريكية كتغيير. إذا لم يكن ذلك ممكنًا، فسنحاول إعطاء ثلاث أوراق نقدية بقيمة 5 دولارات. إذا لم يكن أي من الخيارين متاحا، قم بإرجاع خطأ.

3. الفحص النهائي: إذا نجحنا في معالجة جميع العملاء دون نفاد التغيير، فسيتم إرجاع صحيح.

حالات الحافة:

يجب أن تتعامل الوظيفة مع السيناريوهات التي يكون من المستحيل فيها إجراء التغيير الصحيح، مثل عندما تتلقى فاتورة بقيمة 10 دولارات أو 20 دولارًا في وقت مبكر جدًا دون أن تكون لديك الفاتورة (الفواتير) اللازمة بقيمة 5 دولارات.
يجب أن يتعامل بكفاءة مع أحجام المدخلات الكبيرة بسبب القيود (ما يصل إلى 100000 عميل). يعمل الحل بتعقيد زمني O(n)، مما يجعله الحل الأمثل لهذه المشكلة.

روابط الاتصال

إذا وجدت هذه السلسلة مفيدة، فيرجى التفكير في منح

المستودع نجمة على GitHub أو مشاركة المنشور على شبكات التواصل الاجتماعي المفضلة لديك؟. دعمكم سيعني الكثير بالنسبة لي!

إذا كنت تريد المزيد من المحتوى المفيد مثل هذا، فلا تتردد في متابعتي:

• لينكد إن
• جيثب