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
מהי סיבוכיות הזמן של Richest Customer Wealth?
O(m × n) עבור m לקוחות ו-n בנקים, מכיוון שכל יתרה מתווספת פעם אחת. שום אלגוריתם לא יכול לדלג על תא, מכיוון שכל יתרה שעליה מדלגים עשויה להיות זו שהופכת את בעליה לעשיר ביותר. המקסימום המצטבר משתמש ב-O(1) מקום נוסף.
איך מוצאים את סכום השורה המרבי במערך דו־ממדי?
עבור על השורות, סכם כל אחת מהן ושמור את הסכום הגדול ביותר במשתנה. שפות רבות מקצרות את הלולאה הפנימית באמצעות פונקציית sum מובנית, כמו 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