[Leetcode] 0213. Ladrón de casas ii

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Eres un ladrón profesional que planea robar casas a lo largo de una calle. Cada casa tiene una cierta cantidad de dinero escondida. Todas las casas en este lugar están. dispuestos en círculo. Eso significa que la primera casa es vecina de la última, mientras que las casas adyacentes tienen un sistema de seguridad conectado y. Se pondrá en contacto automáticamente con la policía si dos casas adyacentes fueron asaltadas la misma noche..

Dada una matriz de enteros números representando la cantidad de dinero de cada casa, devolver la cantidad máxima de dinero que puedes robar esta noche sin alertar a la policía.

Ejemplo 1:

Aporte: números = [2,3,2]
Producción: 3
Explicación: No puedes robar la casa 1 (dinero = 2) y luego robar la casa 3 (dinero = 2), porque son casas adyacentes.

Ejemplo 2:

Aporte: números = [1,2,3,1]
Producción: 4
Explicación: Roba la casa 1 (dinero = 1) y luego roba la casa 3 (dinero = 3). Cantidad total que puedes robar = 1 + 3 = 4.

Ejemplo 3:

Aporte: números = [1,2,3]
Producción: 3

Restricciones:

1 <= números.longitud <= 100
0 <= números[i] <= 1000

Pitón

				
					Complejidad de tiempo de #: O(n) Complejidad de espacio de #: O(n) al escribir import List clase Solución: def rob(self, nums: List[int]) -> int: def robMoney(nums: List[int], start : int, fin: int) -> int: dp = [0] * (fin - inicio) dp[0] = nums[inicio] dp[1] = max(dp[0], nums[inicio + 1]) para i en el rango (inicio + 2, fin): dp[i-inicio] = max(nums[i] + dp[i-inicio - 2], dp[i-inicio - 1]) return dp[-1] n = len(nums) si n == 0: devuelve 0 si n == 1: devuelve nums[0] si n == 2: devuelve max(nums[0], nums[1]) money1 = robMoney(nums, 0, n - 1) dinero2 = robarDinero(nums, 1, n) return max(dinero1, dinero2) nums = [2, 3, 2] print(Solución().rob(nums)) nums = [1, 2, 3, 1] imprimir(Solución().rob(núms)) núms = [1, 2, 3] imprimir(Solución().rob(núms))

Medio

Pitón

Artículos relacionados