Richest Customer Wealth

Q: Qual è la complessità temporale di Richest Customer Wealth?

O(m × n) per m clienti e n banche, perché ogni saldo viene sommato una volta. Nessun algoritmo può saltare una cella, perché qualsiasi saldo saltato potrebbe essere quello che rende il suo proprietario il più ricco. Il massimo corrente usa O(1) di spazio aggiuntivo.

Q: Le somme possono causare un overflow di un intero a 32 bit?

Non qui. Una riga ha al massimo 100 saldi di al massimo 10^4 , quindi il totale è al massimo 10^6 , ben al di sotto di 2^31 - 1 . Con limiti più grandi, sommeresti usando un intero a 64 bit.

PrincipianteArray e stringhe

+10

Una banca conserva una griglia accounts con m righe, una per cliente, e n colonne, una per banca: accounts[i][j] è il denaro che il cliente i possiede nella banca j. La ricchezza di un cliente è il totale della sua riga. Restituisci la ricchezza del cliente più ricco.

Funzione

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

accountsinteger-2d-array: la griglia dei saldi, una riga per cliente e una colonna per banca
Restituisceinteger: il totale di riga più grande

Vincoli

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100 e ogni riga ha la stessa lunghezza.
0 ≤ accounts[i][j] ≤ 10⁴

Esempi

Input: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Output: 14
Spiegazione: Le righe sommano 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 e 7 + 0 + 3 = 10. Il cliente centrale ne ha di più, 14, anche se il saldo singolo più alto, 8, appartiene a qualcun altro.

Input: accounts = [[3], [9], [4]]
Output: 9
Spiegazione: Ogni cliente usa una banca, quindi i totali sono 3, 9 e 4, e la risposta è 9.

+14 test nascosti all’invio

Soluzione

Ogni saldo appartiene esattamente a un cliente, quindi devi leggere l'intera griglia: nessun approccio può essere più veloce di O(m × n). La scelta riguarda quanto conservare durante la lettura. Un elenco di tutti i totali funziona, ma conta solo il totale più alto visto finora, quindi basta un solo numero.

Elenca ogni totale, poi scegli quello più grande

Intuizione

Dividi il compito in due parti. Per prima cosa, percorri ogni riga e somma i suoi saldi, memorizzando un totale per cliente. Nel primo esempio si ottiene [11, 14, 10]. Poi esamina quella lista per trovare il suo valore più grande, 14.

Il lavoro va bene: ciascuno dei m × n saldi viene sommato una volta e il secondo passaggio legge m totali. Per una griglia 100 × 100 si tratta di 10^4 addizioni. Il costo è la lista stessa: m numeri aggiuntivi che conservi solo per poi scartarne tutti tranne uno.

Algoritmo

Crea una lista vuota totals.
Per ogni riga, somma i suoi saldi e aggiungi la somma a totals.
Imposta richest sul primo totale.
Sostituisci richest con qualsiasi totale maggiore, quindi restituiscilo.

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

Mantieni un massimo progressivo

Intuizione

Una volta noto il totale di una riga, l'unica domanda è se supera il totale migliore ottenuto finora. Quindi confrontalo subito e tieni un solo numero, richest. Nel primo esempio richest passa da 0 → 11 → 14 e rimane a 14 quando l'ultima riga dà come somma 10.

Inizializza richest a 0. È sicuro perché nessun saldo è negativo, quindi ogni totale è almeno 0 e una griglia di zeri restituisce correttamente 0. Se i saldi potessero essere negativi, inizieresti invece dal totale della prima riga.

Il totale massimo possibile è 100 × 10^4 = 10^6, quindi un intero a 32 bit può contenere ogni somma.

Algoritmo

Imposta richest a 0.
Per ogni riga, somma i suoi saldi in wealth.
Se wealth > richest, imposta richest a wealth.
Dopo l’ultima riga, restituisci 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

Trappole e casi limite

I cicli sono brevi. Gli errori derivano dal confondere la direzione in cui si procede tra i clienti.

Sommare le colonne anziché le righe. Una colonna rappresenta una banca per tutti i clienti; il suo totale risponde a una domanda diversa. Nel primo esempio, le colonne sommano 14, 13 e 8, e la prima corrisponde alla risposta giusta solo per caso.
Restituire il saldo singolo più alto. 8 è il numero più grande nella prima griglia, ma il suo proprietario ha un totale di 11, inferiore ai 14 del cliente che non ha alcun saldo superiore a 5.
Reimpostare il totale della riga nel punto sbagliato. Imposta wealth a 0 all'interno del ciclo delle righe, prima del ciclo interno. Impostalo una volta sola all'esterno e ogni cliente erediterà il denaro del precedente.

Domande frequenti3

Qual è la complessità temporale di Richest Customer Wealth?

O(m × n) per m clienti e n banche, perché ogni saldo viene sommato una volta. Nessun algoritmo può saltare una cella, perché qualsiasi saldo saltato potrebbe essere quello che rende il suo proprietario il più ricco. Il massimo corrente usa O(1) di spazio aggiuntivo.

Come trovi la somma massima di una riga di un array 2D?

Scorri le righe, somma ciascuna e conserva la somma più grande in una variabile. Molti linguaggi abbreviano il ciclo interno con una funzione sum integrata, come max(sum(row) for row in accounts) in Python. In entrambi i casi leggi ogni cella una sola volta.

Le somme possono causare un overflow di un intero a 32 bit?

Non qui. Una riga ha al massimo 100 saldi di al massimo 10^4, quindi il totale è al massimo 10^6, ben al di sotto di 2^31 - 1. Con limiti più grandi, sommeresti usando un intero a 64 bit.

Python

def maximumWealth(accounts):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso