Richest Customer Wealth
يحتفظ أحد البنوك بشبكة accounts تضم m صفوف، صفًا واحدًا لكل عميل، وn أعمدة، عمودًا واحدًا لكل بنك: تمثل accounts[i][j] الأموال التي يملكها العميل i في البنك j. ثروة العميل هي مجموع الأموال في صفه. أعد ثروة العميل الأثرى.
الدالة
- accountsinteger-2d-array
- شبكة الأرصدة، صف واحد لكل عميل وعمود واحد لكل بنك
- تُرجعinteger
- أكبر مجموع للصفوف
القيود
1 ≤ accounts.length ≤ 1001 ≤ accounts[i].length ≤ 100، ولكل صف الطول نفسه.0 ≤ accounts[i][j] ≤ 104
أمثلة
- المدخلات
- accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
- المخرجات
- 14
- الشرح
- يبلغ مجموع الصفوف
2 + 8 + 1 = 11و5 + 5 + 4 = 14و7 + 0 + 3 = 10. لدى العميل الأوسط أكبر مجموع، وهو14، رغم أن أكبر رصيد منفرد، وهو8، يعود إلى شخص آخر.
- المدخلات
- accounts = [[3], [9], [4]]
- المخرجات
- 9
- الشرح
- يستخدم كل عميل بنكًا واحدًا، لذا تكون المجاميع
3و9و4، والإجابة هي9.
+14 اختبارات مخفية عند الإرسال
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أيّ الأرقام تخصّ عميلًا واحدًا: صفّ من الشبكة أم عمود؟
اجمع كل صف للحصول على ثروة أحد العملاء. لن تحتاج أبدًا إلى صفين في الوقت نفسه.
احتفظ بمتغير واحد لأكبر مجموع حتى الآن. اجمع صفًا، وقارن، ثم انتقل إلى الصف التالي.
الحل
كل رصيد يخصّ عميلًا واحدًا بالضبط، لذا عليك قراءة الشبكة بأكملها: لا توجد طريقة تتفوق على زمن O(m × n). يكمن الاختيار في مقدار ما تحتفظ به أثناء القراءة. تنجح قائمة بكل الإجماليات، لكن المهم هو أكبر إجمالي رأيته حتى الآن، لذا يكفي رقم واحد.
اسرد كل الإجماليات، ثم اختر الأكبر
الفكرة
قسّم المهمة إلى جزأين. أولًا، مرّ على كل صف واجمع أرصدته، مع تخزين مجموع واحد لكل عميل. في المثال الأول، يعطي ذلك [11, 14, 10]. ثم ابحث في تلك القائمة عن أكبر قيمة فيها، وهي 14.
العمل جيد: يُضاف كل رصيد من الأرصدة m × n مرة واحدة، وتقرأ المرحلة الثانية m من المجاميع. بالنسبة إلى شبكة 100 × 100، فهذا يعني 10^4 عملية جمع. التكلفة هي القائمة نفسها: m أعداد إضافية تحتفظ بها فقط لتتخلص من جميعها ما عدا واحدًا.
الخوارزمية
- أنشئ قائمة فارغة
totals. - لكل صف، اجمع أرصدته وأضف المجموع إلى
totals. - ابدأ بقيمة
richestالتي تساوي الإجمالي الأول. - استبدل
richestبأي إجمالي أكبر، ثم أعده.
def maximumWealth(accounts):
# First pass: every customer's total wealth.
totals = []
for customer in accounts:
wealth = 0
for money in customer:
wealth += money
totals.append(wealth)
# Second pass: the largest total.
richest = totals[0]
for wealth in totals:
if wealth > richest:
richest = wealth
return richestاحتفِظ بأكبر قيمة حتى الآن
الفكرة
بعد معرفة مجموع صفٍّ ما، يكون السؤال الوحيد هو ما إذا كان يتجاوز أكبر مجموع حتى الآن. لذا قارنه فورًا واحتفظ برقم واحد، richest. في المثال الأول، تتغير قيمة richest على النحو التالي: 0 → 11 → 14، وتبقى عند 14 عندما يكون مجموع الصف الأخير 10.
ابدأ قيمة richest من 0. هذا آمن لأنه لا يوجد رصيد سالب، لذا فإن كل مجموع لا يقل عن 0، كما أن شبكة من الأصفار تعيد 0 على نحو صحيح. لو كان من الممكن أن تكون الأرصدة سالبة، لبدأت من مجموع الصف الأول بدلًا من ذلك.
أكبر مجموع ممكن هو 100 × 10^4 = 10^6، لذا فإن عددًا صحيحًا من 32 بت يستوعب كل مجموع.
الخوارزمية
- عيّن
richestإلى0. - لكل صف، اجمع أرصدته في
wealth. - إذا كان
wealth > richest، فعيّنrichestإلىwealth. - بعد الصف الأخير، أعد
richest.
def maximumWealth(accounts):
richest = 0 # money is never negative, so 0 is a safe start
for customer in accounts:
richest = max(richest, sum(customer))
return richest
أخطاء شائعة وحالات حدّية
الحلقات قصيرة. تنشأ الأخطاء من الخلط بين الاتجاه الذي تسير فيه بيانات العميل.
- جمع الأعمدة بدلًا من الصفوف. يمثّل العمود مصرفًا واحدًا لجميع العملاء؛ ويجيب مجموعه عن سؤال مختلف. في المثال الأول، مجاميع الأعمدة هي
14و13و8، والأول منها يطابق الإجابة الصحيحة بالمصادفة فقط. - إرجاع أكبر رصيد منفرد.
8هو أكبر رقم في الشبكة الأولى، لكن مجموع أرصدة صاحبه هو11، وهو أقل من14التي يملكها العميل الذي لا يتجاوز أيٌّ من أرصدته5. - إعادة تعيين مجموع الصف في الموضع الخطأ. عيّن
wealthإلى0داخل حلقة الصفوف، قبل الحلقة الداخلية. أما إذا عيّنته مرة واحدة خارجها، فسيَرِث كل عميل أموال العميل السابق.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة أغنى ثروة لعميل؟
O(m × n) لـ m من العملاء وn من البنوك، لأن كل رصيد يُضاف مرة واحدة. لا يمكن لأي خوارزمية تخطي خلية، لأن أي رصيد يتم تخطيه قد يكون الرصيد الذي يجعل صاحبه الأغنى. يستخدم الحد الأقصى الجاري مساحة إضافية O(1).
كيف تجد أكبر مجموع لصف في مصفوفة ثنائية الأبعاد؟
كرّر المرور على الصفوف، واجمع عناصر كل صف، واحتفظ بأكبر مجموع في متغيّر. تختصر لغات كثيرة الحلقة الداخلية باستخدام دالة جمع مضمّنة، مثل max(sum(row) for row in accounts) في Python. في كلتا الحالتين، تقرأ كل خلية مرة واحدة.
هل يمكن أن تتجاوز المجاميع نطاق عدد صحيح ذي 32 بت؟
ليس هنا. يحتوي الصف على 100 رصيد كحد أقصى، قيمة كل منها 10^4 كحد أقصى، لذا فإن المجموع لا يتجاوز 10^6، وهو أقل بكثير من 2^31 - 1. مع حدود أكبر، ستجمع القيم في عدد صحيح ذي 64 بت.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def maximumWealth(accounts):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
المتوقع
14