Ejercicios Leetcode
Bibliografía
1. Ejercicios fáciles
Two sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
nums = [2, 7, 11, 15]
target = 9
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
Solución
def funcion1(lista: list[int], target: int) -> list[int]:
"""
Esta funcion es O(N^2) en tiempo, y O(1) en espacio.
"""
for i, vali in enumerate(lista):
for j, valj in enumerate(lista[i:]):
if valj + vali == target:
return [i, j]
def funcion2(lista: list[int], target: int) -> list[int]:
"""
Esta funcion es O(N) en tiempo y O(N) en espacio.
"""
diccionario = {}
for i, valor in enumerate(lista):
valor2 = target - valor
if valor2 in diccionario:
return [i, diccionario[valor2]]
else:
diccionario[valor] = i
Best time to buy and sell stock
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
Example:
nums = [7,1,5,3,6,4]
output = 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 -1 = 5. Not 7 - 1 = 6, as selling price needs to be larger than buying price.
Solución
def funcion(lista: list[int]) -> list[int]:
"""
O(N^2)
"""
max = lista[0]
for i, vali in enumerate(lista):
for j, valj in enumerate(lista[i:]):
diff = valj - vali
if diff > max:
max = diff
tupla = (i, j + 1)
return [tupla, max]
def funcion2(lista: list[int]) -> list[int]:
"""
O(N)
"""
## Almacenamos indice, valor
tupla_max = (0, float('-inf'))
tupla_min = (0, float('inf'))
for i, vali in enumerate(lista):
if vali < tupla_min[-1]:
tupla_min = (i, vali)
elif vali > tupla_max[-1] and i > tupla_min[0]:
tupla_max = (i, vali)
return [tupla_max[0], tupla_min[0], tupla_max[-1] - tupla_min[-1]]
Contains duplicate
Given an integer array nums, return true of any value appears at least twice in the array, and return false if every element is distinct.
Example:
nums = [1,2,3,1]
output = true
Solución
def funcion(lista: list[int]) -> bool:
"""
O(N^2)
"""
for i, vali in enumerate(lista):
for j, valj in enumerate(lista[i + 1:]):
if vali == valj:
return True
return False
def funcion2(lista: list[int]) -> bool:
"""
O(N)
"""
diccionario = {}
for i, vali in enumerate(lista):
if vali in diccionario:
return True
else:
diccionario[vali] = i
return False
Maximum subarray
Given an integer array nums, fin the contiguous subarray (containing at least one number) which has the larges sum and return its sum
Example:
nums = [-2,1,-3,4,-1,2,1,-5,4]
output = 6
Explanaation: [4,-1,2,1] has the largest sum = 6
Solución
def funcion(lista: list[int]) -> int:
"""
Maximo subarray
Kadane's algorithm O(N)
"""
suma_act = lista[0]
suma_max = lista[0]
for i in range(1, len(lista)):
suma_act = max(lista[i], suma_act + lista[i])
suma_max = max(suma_act, suma_max)
return suma_max
2. Ejercicios medios
Product of array except self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(N) time and without using the division operation.
Example:
nums = [1,2,3,4]
output = [24,12,8,6]
Solucion
def funcion(lista: list[int]) -> bool:
"""
O(N^2), suponiendo que no tenemos las restricciones que nos imponen
"""
producto = 1
for i, vali in enumerate(lista):
producto *= vali
res = []
for i, vali in enumerate(lista):
res.append(int(producto / vali))
return res
def funcion2(lista: list[int]) -> bool:
"""
O(N^2), sin utilizar la division
"""
res = []
for i, vali in enumerate(lista):
if i == 0:
izq = []
else:
izq = lista[:i]
elif i == len(lista) - 1:
der = []
else:
der = lista[i + 1:]
new_lista = izq + der
producto = 1
for i, val in enumerate(new_lista):
producto *= val
res.append(producto)
return res
def funcion3(lista: list[int]) -> bool:
"""
O(N)
"""
n = len(lista)
## Inicializar las listas de productos a la izquierda y a la derecha
## Inicialmente todos los valores son 1, se crean tantos elementos
## como elementos tenga la lista original
izq = [1] * n
der = [1] * n
## Calcular el producto acumulativo a la izquierda de cada índice
for i in range(1, n):
izq[i] = izq[i - 1] * lista[i - 1]
## Calcular el producto acumulativo a la derecha de cada índice
for i in reversed(range(n - 1)):
der[i] = der[i + 1] * lista[i + 1]
## Calcular el producto de los elementos excepto el mismo
for i in range(n):
lista[i] = izq[i] * der[i]
return lista