Richest Customer Wealth

Q: Apa kompleksitas waktu dari Richest Customer Wealth?

O(m × n) untuk m pelanggan dan n bank, karena setiap saldo dijumlahkan satu kali. Tidak ada algoritma yang bisa melewatkan sel, karena saldo yang dilewatkan bisa saja membuat pemiliknya menjadi yang terkaya. Nilai maksimum yang terus diperbarui menggunakan ruang tambahan O(1) .

Q: Apakah jumlahnya dapat melampaui batas bilangan bulat 32-bit?

Bukan di sini. Satu baris memiliki paling banyak 100 saldo, masing-masing paling banyak 10^4 , jadi totalnya paling banyak 10^6 , jauh di bawah 2^31 - 1 . Dengan batas yang lebih besar, kamu akan menjumlahkannya ke dalam bilangan bulat 64-bit.

PemulaArray dan string

+10

Sebuah bank menyimpan grid accounts dengan m baris, satu untuk setiap nasabah, dan n kolom, satu untuk setiap bank: accounts[i][j] adalah jumlah uang yang dimiliki nasabah i di bank j. Kekayaan seorang nasabah adalah total nilai pada barisnya. Kembalikan kekayaan nasabah terkaya.

Fungsi

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: tabel saldo, satu baris untuk setiap pelanggan dan satu kolom untuk setiap bank
Mengembalikaninteger: total baris terbesar

Batasan

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, dan setiap baris memiliki panjang yang sama.
0 ≤ accounts[i][j] ≤ 10⁴

Contoh

Input: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Output: 14
Penjelasan: Jumlah setiap baris adalah 11, 14, dan 10. Pelanggan di tengah memiliki kekayaan terbesar dengan 14, meskipun saldo tunggal terbesar, 8, dimiliki orang lain.

Input: accounts = [[3], [9], [4]]
Output: 9
Penjelasan: Setiap pelanggan menggunakan satu bank, jadi totalnya adalah 3, 9, dan 4, dan jawabannya adalah 9.

Solusi

Setiap saldo hanya dimiliki oleh satu pelanggan, jadi kamu harus membaca seluruh grid: tidak ada pendekatan yang lebih cepat daripada waktu O(m × n). Pilihannya adalah seberapa banyak yang kamu simpan saat membaca. Hanya total terbesar yang ditemukan sejauh ini yang penting, jadi satu angka sudah cukup.

Daftarkan semua total, lalu pilih yang terbesar

Intuisi

Telusuri setiap baris, jumlahkan saldo di dalamnya, lalu simpan satu total untuk setiap pelanggan: [11, 14, 10] untuk contoh pertama. Lalu telusuri list itu untuk mencari nilai terbesarnya, 14.

Setiap saldo dari m × n dijumlahkan satu kali, jadi waktunya tidak masalah. Biayanya adalah list tersebut, m angka tambahan yang kamu simpan hanya untuk membuang semua kecuali satu.

Algoritma

Buat list kosong totals.
Untuk setiap baris, jumlahkan saldonya dan tambahkan hasilnya ke totals.
Mulai dengan richest yang berisi total pertama.
Ganti richest dengan total yang lebih besar, lalu kembalikan nilainya.

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

Pertahankan nilai maksimum saat ini

Intuisi

Setelah total suatu baris diketahui, satu-satunya pertanyaan adalah apakah total itu lebih besar daripada total terbaik sejauh ini. Segera bandingkan dan simpan satu angka, richest. Pada contoh pertama, nilai richest berubah menjadi 0 → 11 → 14 dan tetap 14 saat jumlah baris terakhir adalah 10.

Memulai richest dari 0 aman karena tidak ada saldo yang negatif, jadi setiap total setidaknya 0 dan grid yang berisi nol akan menghasilkan 0. Jika saldo bisa negatif, kamu akan memulai dari total baris pertama.

Algoritma

Atur richest ke 0.
Untuk setiap baris, jumlahkan semua saldonya ke dalam wealth.
Jika wealth > richest, atur richest ke wealth.
Setelah baris terakhir, kembalikan 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

Jebakan dan kasus tepi

Menjumlahkan kolom, bukan baris. Satu kolom mewakili satu bank untuk semua pelanggan. Dalam contoh pertama, jumlah setiap kolom adalah 14, 13, dan 8, dan jumlah kolom pertama cocok dengan jawaban hanya karena kebetulan.
Mengembalikan saldo tunggal terbesar. 8 adalah angka terbesar dalam grid pertama, tetapi pemiliknya memiliki total 11, lebih kecil daripada 14 milik pelanggan yang saldo di satu bank pun tidak lebih dari 5.
Mengatur ulang total baris di tempat yang salah. Atur wealth menjadi 0 di dalam perulangan baris, sebelum perulangan bagian dalam. Atur sekali di luar perulangan, dan setiap pelanggan akan mewarisi uang pelanggan sebelumnya.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Richest Customer Wealth?

O(m × n) untuk m pelanggan dan n bank, karena setiap saldo dijumlahkan satu kali. Tidak ada algoritma yang bisa melewatkan sel, karena saldo yang dilewatkan bisa saja membuat pemiliknya menjadi yang terkaya. Nilai maksimum yang terus diperbarui menggunakan ruang tambahan O(1).

Bagaimana cara mencari jumlah baris maksimum dari array 2D?

Lakukan perulangan pada setiap baris, jumlahkan setiap baris, lalu simpan jumlah terbesar dalam sebuah variabel. Banyak bahasa mempersingkat perulangan bagian dalam dengan sum bawaan, seperti max(sum(row) for row in accounts) dalam Python. Apa pun caranya, kamu membaca setiap sel satu kali.

Apakah jumlahnya dapat melampaui batas bilangan bulat 32-bit?

Bukan di sini. Satu baris memiliki paling banyak 100 saldo, masing-masing paling banyak 10^4, jadi totalnya paling banyak 10^6, jauh di bawah 2^31 - 1. Dengan batas yang lebih besar, kamu akan menjumlahkannya ke dalam bilangan bulat 64-bit.

def maximumWealth(accounts):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Output yang diharapkan