Richest Customer Wealth
Un banco mantiene una cuadrícula accounts con m filas, una por cliente, y n columnas, una por banco: accounts[i][j] es el dinero que el cliente i tiene en el banco j. La riqueza de un cliente es el total de su fila. Devuelve la riqueza del cliente más rico.
Función
- accountsinteger-2d-array
- la cuadrícula de saldos, una fila por cliente y una columna por banco
- Devuelveinteger
- el total de fila más grande
Restricciones
1 ≤ accounts.length ≤ 1001 ≤ accounts[i].length ≤ 100, y todas las filas tienen la misma longitud.0 ≤ accounts[i][j] ≤ 104
Ejemplos
- Entrada
- accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
- Salida
- 14
- Explicación
- Las filas suman
2 + 8 + 1 = 11,5 + 5 + 4 = 14y7 + 0 + 3 = 10. El cliente del medio tiene la mayor suma,14, aunque el saldo individual más grande,8, pertenece a otra persona.
- Entrada
- accounts = [[3], [9], [4]]
- Salida
- 9
- Explicación
- Cada cliente usa un banco, así que los totales son
3,9y4, y la respuesta es9.
+14 pruebas ocultas al enviar
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Qué números pertenecen a un cliente: una fila de la cuadrícula o una columna?
Suma cada fila para obtener la riqueza de un cliente. Nunca necesitas dos filas al mismo tiempo.
Conserva una variable para el total más grande hasta el momento. Suma una fila, compara y pasa a la siguiente fila.
Solución
Cada saldo pertenece exactamente a un cliente, así que debes leer toda la cuadrícula: ningún enfoque supera el tiempo O(m × n). La elección es cuánto conservas mientras lees. Una lista con todos los totales funciona, pero solo importa el total más grande visto hasta el momento, así que basta con un número.
Enumera todos los totales y después elige el mayor
Intuición
Divide la tarea en dos partes. Primero, recorre cada fila y suma sus saldos, guardando un total por cliente. Para el primer ejemplo, eso da [11, 14, 10]. Después, recorre esa lista para encontrar su valor más grande, 14.
El trabajo está bien: cada uno de los m × n saldos se suma una vez, y la segunda pasada lee m totales. Para una cuadrícula de 100 × 100, son 10^4 sumas. El costo es la propia lista, m números adicionales que guardas solo para descartar todos menos uno.
Algoritmo
- Crea una lista vacía
totals. - Para cada fila, suma sus saldos y añade la suma a
totals. - Inicia
richestcon el primer total. - Sustituye
richestpor cualquier total mayor y después devuélvelo.
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 richestMantén un máximo acumulado
Intuición
Una vez que se conoce el total de una fila, la única pregunta es si supera el mejor total hasta el momento. Así que compáralo de inmediato y conserva un número, richest. En el primer ejemplo, richest pasa por 0 → 11 → 14 y se mantiene en 14 cuando la última fila suma 10.
Empieza richest en 0. Es seguro porque ningún saldo es negativo, así que todos los totales son al menos 0, y una cuadrícula de ceros devuelve correctamente 0. Si los saldos pudieran ser negativos, empezarías con el total de la primera fila.
El total máximo posible es 100 × 10^4 = 10^6, así que un entero de 32 bits puede almacenar cualquier suma.
Algoritmo
- Establece
richesten0. - Para cada fila, suma sus saldos en
wealth. - Si
wealth > richest, establecerichestenwealth. - Después de la última fila, devuelve
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
Errores comunes y casos límite
Los bucles son cortos. Los errores se deben a confundir la dirección en la que se recorre a cada cliente.
- Sumar columnas en lugar de filas. Una columna es un banco para todos los clientes; su total responde a una pregunta diferente. En el primer ejemplo, las columnas suman
14,13y8, y la primera solo coincide con la respuesta correcta por casualidad. - Devolver el saldo individual más grande.
8es el número más grande de la primera cuadrícula, pero su propietario tiene11en total, menos que los14del cliente que no tiene ningún saldo superior a5. - Restablecer el total de la fila en el lugar equivocado. Establece
wealthen0dentro del bucle de filas, antes del bucle interno. Si lo estableces una sola vez fuera, cada cliente hereda el dinero del anterior.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Richest Customer Wealth?
O(m × n) para m clientes y n bancos, porque cada saldo se suma una vez. Ningún algoritmo puede omitir una celda, ya que cualquier saldo omitido podría ser el que hiciera que su propietario fuera el más rico. El máximo acumulado usa O(1) de espacio adicional.
¿Cómo encuentras la suma máxima de una fila de una matriz 2D?
Recorre las filas, suma cada una y guarda la suma más grande en una variable. Muchos lenguajes acortan el bucle interno con una función sum integrada, como max(sum(row) for row in accounts) en Python. De cualquier manera, lees cada celda una vez.
¿Pueden las sumas desbordar un entero de 32 bits?
No aquí. Una fila tiene como máximo 100 saldos de como máximo 10^4, así que el total es como máximo 10^6, muy por debajo de 2^31 - 1. Con límites mayores, sumarías en un entero de 64 bits.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def maximumWealth(accounts):
# Escribe el código aquíCaso 1
Caso 2
Entrada
accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Esperado
14