2270. عدد من الطرق لتقسيم المصفوفة

الصعوبة: متوسطة

الموضوعات: صفيف ، بادئة مجموع

يتم إعطاؤك 0-indexed integer مجموعة من الطول n.

nums يحتوي على تقسيم صالح في الفهرس i إذا كان ما يلي صحيحًا:

• مجموع العناصر الأولى i 1 هو أكبر من أو يساوي مجموع العناصر الأخيرة n - i - 1.
• هناك عنصر واحد على الأقل على يمين i. هذا هو ، 0

إرجاع عدد تقسيم صحيح في عدد .

مثال 1:

• الإدخال: nums = [10،4 ، -8،7]
• الإخراج: 2
• شرح: هناك ثلاث طرق لتقسيم الأرقام إلى جزأين غير فارغين:
  • تقسيم الأرقام في الفهرس 0. ثم ، الجزء الأول هو [10] ، ومجموعه هو 10. الجزء الثاني هو [4 ، -8،7] ، ومجموعه هو 3. منذ 10> = 3 ، i = 0 هو تقسيم صالح.
  تقسيم الأرقام في الفهرس 1. ثم ، الجزء الأول هو [10،4] ، ومجموعه هو 14. الجزء الثاني هو [-8،7] ، ومجموعه هو -1. منذ 14> = -1 ، i = 1 هو تقسيم صالح.
  تقسيم الأرقام في الفهرس 2. ثم ، الجزء الأول هو [10،4 ، -8] ، ومجموعه هو 6. الجزء الثاني هو [7] ، ومجموعه هو 7. منذ 6 وهكذا ، فإن عدد الانقسامات الصحيحة في العدد هو 2.

مثال 2:

الإدخال:
• nums = [2،3،1،0]
الإخراج:
• 2
شرح:
• هناك انشقاق صحيحان في العدد: تقسيم الأرقام في الفهرس 1. ثم ، الجزء الأول هو [2،3] ، ومجموعه هو 5. الجزء الثاني هو [1،0] ، ومجموعه هو 1. منذ 5> = 1 ، i = 1 هو تقسيم صالح.
  تقسيم الأرقام في الفهرس 2. ثم ، الجزء الأول هو [2،3،1] ، ومجموعه هو 6. الجزء الثاني هو [0] ، ومجموعه هو 0. منذ 6> = 0 ، i = 2 هو تقسيم صالح.
قيود:

2 5

• ^-10 5
5 تَلمِيح:

لأي فهرس i ، كيف يمكننا العثور على مجموع العناصر الأولى (i 1) من مجموع العناصر الأولى؟

إذا كان المجموع الإجمالي للمصفوفة معروفًا ، فكيف يمكننا التحقق مما إذا كان مجموع العناصر الأولى (i 1) أكبر من العناصر المتبقية أو تساويها؟
2. حل:

يمكننا التعامل معها باستخدام الخطوات التالية:

يقترب:

بادئة مجموع

: أولاً ، نحسب المبلغ التراكمي للمصفوفة من اليسار ، مما يساعد في التحقق من مجموع العناصر الأولى الأولى.
1. المجموع الإجمالي
: حساب إجمالي مجموع الصفيف ، وهو أمر مفيد في التحقق مما إذا كان مجموع العناصر المتبقية أقل من أو يساوي مجموع العناصر الأولى الأولى.
2. تكرار عبر الصفيف
: لكل فهرس صالح I (حيث 0 الكفاءة : بدلاً من إعادة حساب المبالغ مرارًا وتكرارًا ، استخدم مجموع البادئة والمبلغ الكلي للمقارنات الفعالة.
3. لننفذ هذا الحل في PHP: 2270. عدد الطرق لتقسيم المصفوفة

توضيح:

$ totalsum

: يخزن هذا المتغير مجموع جميع العناصر في صفيف NUMS.

1. $ prepixsum : هذا المتغير يتبع المبلغ التراكمي للعناصر من اليسار (حتى الفهرس الأول).
2. $ تبقى : هذا هو مجموع العناصر المتبقية من الفهرس الأول إلى نهاية المصفوفة. يتم حسابه عن طريق طرح البادئة $ من $ totalsum.
3. فحص تقسيم صالح : لكل فهرس i ، نتحقق مما إذا كان مجموع البادئة أكبر من أو يساوي المبلغ المتبقي.
4. تعقيد الوقت:

o (n)

: نقوم بتدوين الصفيف مرة واحدة لحساب المبلغ ومرة ​​أخرى للتحقق من انقسامات صالحة. لذلك ، فإن التعقيد الزمني خطي فيما يتعلق بطول الصفيف.

• تعقيد الفضاء:

o (1)

: نحن نستخدم فقط عدد قليل من المتغيرات الإضافية ($ totalsum ، precipixsum $ ، $ payingingsum) ، وبالتالي فإن تعقيد الفضاء ثابت.

• ارتباطات الاتصال

إذا وجدت هذه السلسلة مفيدة ، فيرجى التفكير في إعطاء المستودع إن دعمك يعني الكثير بالنسبة لي!

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

LinkedIn

• github