Richest Customer Wealth
Bir banka, her müşteri için bir satır ve her banka için bir sütun içeren accounts ızgarasını tutar; burada accounts[i][j], i müşterisinin j bankasında tuttuğu paradır. Bir müşterinin serveti, satırındaki değerlerin toplamıdır. En zengin müşterinin servetini döndürün.
Fonksiyon
- accountsinteger-2d-array
- müşteri başına bir satır ve banka başına bir sütun olacak şekilde bakiye tablosu
- Döndürürinteger
- en büyük satır toplamı
Kısıtlar
1 ≤ accounts.length ≤ 1001 ≤ accounts[i].length ≤ 100ve her satır aynı uzunluktadır.0 ≤ accounts[i][j] ≤ 104
Örnekler
- Girdi
- accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
- Çıktı
- 14
- Açıklama
- Satırların toplamı
2 + 8 + 1 = 11,5 + 5 + 4 = 14ve7 + 0 + 3 = 10eder. En yüksek toplam,14ile ortadaki müşterinindir; tek başına en büyük bakiye olan8ise başka birine aittir.
- Girdi
- accounts = [[3], [9], [4]]
- Çıktı
- 9
- Açıklama
- Her müşteri bir banka kullanır, bu nedenle toplamlar
3,9ve4olur ve yanıt9'dur.
Gönderirken +14 gizli test
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir müşteriye ait sayılar ızgaranın bir satırında mı, yoksa bir sütununda mı yer alır?
Bir müşterinin servetini bulmak için her satırdaki değerleri toplayın. Aynı anda iki satıra hiçbir zaman ihtiyacınız olmaz.
Şimdiye kadarki en büyük toplamı tutmak için bir değişken kullan. Bir satırın toplamını hesapla, karşılaştır ve sonraki satıra geç.
Çözüm
Her bakiye tam olarak bir müşteriye ait olduğundan, tüm ızgarayı okumalısınız: hiçbir yaklaşım O(m × n) zaman karmaşıklığını aşamaz. Seçim, okurken ne kadar bilgi tutacağınızdır. Tüm toplamların bir listesini tutmak işe yarar, ancak şu ana kadar görülen en büyük toplam önemlidir; bu yüzden tek bir sayı yeterlidir.
Her toplamı listeleyin, ardından en büyüğünü seçin
Sezgi
Görevi ikiye böl. Önce her satırda ilerleyip bakiyeleri topla ve her müşteri için bir toplam sakla. İlk örnek için sonuç [11, 14, 10] olur. Ardından bu listedeki en büyük değeri bul: 14.
İşlem uygundur: m × n bakiyenin her biri bir kez toplanır ve ikinci geçişte m toplam okunur. 100 × 100 boyutunda bir ızgara için bu, 10^4 toplama işlemidir. Bedeli ise listenin kendisidir: yalnızca içlerinden biri dışında hepsini atacağın m fazladan sayıyı bellekte tutarsın.
Algoritma
- Boş bir
totalslistesi oluşturun. - Her satır için bakiyelerini toplayın ve toplamı
totalslistesine ekleyin. richestdeğerini ilk toplam olarak başlatın.richestdeğerini daha büyük herhangi bir toplamla değiştirin, ardından onu döndürün.
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Şu ana kadarki en büyük değeri tut
Sezgi
Bir satırın toplamı bilindiğinde, tek soru şu ana kadarki en iyi toplamı geçip geçmediğidir. Bu yüzden hemen karşılaştır ve richest adlı tek bir sayı tut. İlk örnekte richest değeri 0 → 11 → 14 olur ve son satırın toplamı 10 olduğunda 14 olarak kalır.
richest değerini 0 olarak başlat. Bu güvenlidir çünkü hiçbir bakiye negatif değildir; dolayısıyla her toplam en az 0 olur ve sıfırlardan oluşan bir ızgara doğru şekilde 0 döndürür. Bakiyeler negatif olabilseydi, ilk satırın toplamıyla başlatırdın.
Mümkün olan en büyük toplam 100 × 10^4 = 10^6 olduğundan, 32 bitlik bir tamsayı tüm toplamları tutar.
Algoritma
richestdeğerini0olarak ayarla.- Her satır için bakiyelerini toplayarak
wealthdeğerini hesapla. wealth > richestiserichestdeğeriniwealtholarak ayarla.- Son satırdan sonra
richestdeğerini döndür.
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
Tuzaklar ve uç durumlar
Döngüler kısa. Hatalar, müşterilerin hangi yönde ilerlediğinin karıştırılmasından kaynaklanır.
- Satırlar yerine sütunları toplamak. Bir sütun, tüm müşterilerdeki tek bir bankadır; toplamı farklı bir soruyu yanıtlar. İlk örnekte sütunların toplamı
14,13ve8olur ve ilk sütun doğru yanıtı yalnızca şans eseri verir. - En büyük tek bakiyeyi döndürmek. İlk tablodaki en büyük sayı
8, ancak sahibinin toplamı11eder; bu, bakiyesi5'i aşmayan müşterinin14toplamından azdır. - Satır toplamını yanlış yerde sıfırlamak. İç döngüden önce, satır döngüsünün içinde
wealthdeğerini0olarak ayarla. Bunu döngünün dışında bir kez ayarlarsan her müşteri, önceki müşterinin parasını devralır.
Sıkça sorulan sorular3
En Zengin Müşteri Serveti'nin zaman karmaşıklığı nedir?
O(m × n) m müşteri ve n banka için, çünkü her bakiye bir kez eklenir. Atlanan herhangi bir bakiye, sahibini en zengin yapan bakiye olabileceğinden hiçbir algoritma bir hücreyi atlayamaz. Çalışma sırasındaki maksimum değer O(1) ek alan kullanır.
2 boyutlu bir dizinin en büyük satır toplamını nasıl bulursunuz?
Satırlar üzerinde döngü kurun, her birini toplayın ve en büyük toplamı bir değişkende tutun. Python'daki max(sum(row) for row in accounts) gibi birçok dil, yerleşik bir sum işleviyle iç döngüyü kısaltır. Her iki durumda da her hücreyi bir kez okursunuz.
Toplamlar 32 bitlik bir tamsayıyı aşabilir mi?
Burada değil. Bir satırda en fazla 100 bakiye bulunur ve her biri en fazla 10^4 olduğundan toplam en fazla 10^6 olur; bu da 2^31 - 1 değerinden çok daha küçüktür. Daha büyük sınırlar olsaydı, toplamı 64 bitlik bir tamsayıya eklerdin.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def maximumWealth(accounts):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Beklenen
14