Cheat Sheet:
Estructuras de Datos y Algoritmos
En esta sección se mostrarán la definición básica y ejemplos de la implementación de las estructuras de datos y algoritmos más conocidas. En la barra de la izquierda puedes seleccionar la estructura.
Stack (Pila)
- Descripción. Estructura LIFO, último en entrar, primero en salir
- Operaciones clave. append() para push, pop() para pop.
# Implementación básica
stack = [] # Creamos una lista vacía que funcionará como pila
stack.append(1) # Push: Añadimos 1 a la pila → [1]
stack.append(2) # Push: Añadimos 2 a la pila → [1, 2]
print(stack.pop()) # Pop: Elimina y retorna el último elemento (2) → [1]
# Ejemplo típico 1: Verificar si una cadena con paréntesis está balanceada y correctamente anidada.
def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in pairs.values(): # Si es un paréntesis de apertura
stack.append(char) # Se agrega a la pila
elif char in pairs: # Si es un paréntesis de cierre
if not stack or stack[-1] != pairs[char]: # Si la pila está vacía o no coincide con el par esperado
return False
stack.pop() # El par coincide, lo eliminamos
return not stack # Si la pila está vacía al final, es válido
# Ejemplo visual
s = "({[]})"
stack = []
# '(' → stack = ['(']
# '{' → stack = ['(', '{']
# '[' → stack = ['(', '{', '[']
# ']' → cierra '[' → stack = ['(', '{']
# '}' → cierra '{' → stack = ['(']
# ')' → cierra '(' → stack = []
# stack vacío → ✅ válido
###########################################################################################
# Ejemplo típico 2: Evaluar RPN (Reverse Polish Notation)
from typing import List
def evaluateRPN(tokens: List[str]) -> int:
stack = []
for token in tokens:
if token not in '+-*/':
stack.append(int(token)) # Agregar número a la pila
else:
b, a = stack.pop(), stack.pop() # Sacar los dos últimos operandos
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
else: stack.append(int(a / b)) # División entera
return stack[0]
# Ejemplo visual
tokens = ["2", "1", "+", "3", "*"]
# Stack inicial: []
# "2" → stack = [2]
# "1" → stack = [2, 1]
# "+" → pop 1 y 2 → 2 + 1 = 3 → stack = [3]
# "3" → stack = [3, 3]
# "*" → pop 3 y 3 → 3 * 3 = 9 → stack = [9]
# Resultado final: 9
Queue (Cola)
- Descripción. Estructura FIFO (primero en entrar, primero en salir).
# Implementación básica
from collections import deque # Importamos deque para eficiencia
queue = deque() # Creamos una cola vacía
queue.append(1) # Enqueue: Añadimos 1 → deque([1])
queue.append(2) # Enqueue: Añadimos 2 → deque([1, 2])
print(queue.popleft()) # Dequeue: Extraemos el primer elemento (1) → deque([2])
# Ejemplo típico 1: BFS (Breadth-First Search) en un árbol
from collections import deque
def bfs(root):
if not root: # Caso base: árbol vacío
return []
queue = deque([root]) # Inicializamos la cola con la raíz
result = [] # Aquí almacenaremos el recorrido BFS
while queue: # Mientras haya nodos por procesar
node = queue.popleft() # Extraemos el primer nodo de la cola
result.append(node.val) # Añadimos su valor al resultado
# Añadimos hijos izquierdo y derecho a la cola si existen
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Ejemplo visual
# Árbol:
# 1
# / \
# 2 3
# / \ /
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
# Al aplicar bfs
# queue = [1] → result = [1]
# queue = [2, 3] → result = [1, 2, 3]
# queue = [4, 5, 6] → result = [1, 2, 3, 4, 5, 6]
###########################################################################################
# Ejemplo típico 2:
# Casa
# / \
# Tienda Trabajo
# \ /
# Gimnasio
# Definimos el grafo como un diccionario de listas de adyacencia
grafo = {
'Casa': ['Tienda', 'Trabajo'], # Casa está conectada a Tienda y Trabajo
'Tienda': ['Casa', 'Gimnasio'], # Tienda está conectada a Casa y Gimnasio
'Trabajo': ['Casa', 'Gimnasio'], # Trabajo está conectada a Casa y Gimnasio
'Gimnasio': ['Tienda', 'Trabajo'] # Gimnasio está conectada a Tienda y Trabajo
}
def bfs_camino_mas_corto(grafo, inicio, fin):
queue = deque([(inicio, [inicio])]) # Cola: (nodo_actual, camino_hasta_ahora)
visitados = set([inicio]) # Nodos ya visitados
while queue:
nodo_actual, camino = queue.popleft()
if nodo_actual == fin:
return camino # ¡Encontramos el camino!
for vecino in grafo[nodo_actual]:
if vecino not in visitados:
visitados.add(vecino)
queue.append((vecino, camino + [vecino])) # Añadimos el vecino al camino
return None # No hay camino (aunque en este caso siempre existe)
# Ejecutamos BFS desde 'Casa' hasta 'Trabajo'
camino = bfs_camino_mas_corto(grafo, 'Casa', 'Trabajo')
# 1. Inicialización:
### queue = deque([('Casa', ['Casa'])]) (empezamos en 'Casa').
### visitados = {'Casa'}.
# 2. Primera iteración:
### Sacamos: ('Casa', ['Casa']) de la cola.
### Vecinos de 'Casa': 'Tienda' y 'Trabajo'.
### Añadimos a la cola: ('Tienda', ['Casa', 'Tienda']) y ('Trabajo', ['Casa', 'Trabajo'])
### Cola ahora: [('Tienda', [...]), ('Trabajo', [...])]
### Visitados: {'Casa', 'Tienda', 'Trabajo'}.
# 3. Segunda iteración:
### Sacamos: ('Tienda', ['Casa', 'Tienda']).
### Vecinos de 'Tienda': 'Casa' (ya visitado) y 'Gimnasio'.
### Añadimos a la cola: ('Gimnasio', ['Casa', 'Tienda', 'Gimnasio']).
### Cola ahora: [('Trabajo', [...]), ('Gimnasio', [...])].
# 4. Tercera iteración:
### Sacamos: ('Trabajo', ['Casa', 'Trabajo']).
### ¡Este es el objetivo! Retornamos el camino ['Casa', 'Trabajo'].
print("Camino más corto:", camino)
# -> Camino más corto: ['Casa', 'Trabajo']
Deque (Double-Ended Queue)
# Implementación basica
from collections import deque
dq = deque() # Crea un deque vacío
dq.append(1) # Añade 1 por la derecha → deque([1])
dq.appendleft(2) # Añade 2 por la izquierda → deque([2, 1])
dq.pop() # Elimina y retorna el último elemento (1)
dq.popleft() # Elimina y retorna el primer elemento (2)
# Ejemplo típico: Sliding Window Máximo
def maxSlidingWindow(nums, k):
dq, res = deque(), [] # dq guarda ÍNDICES, no valores
for i, n in enumerate(nums):
# 1. Elimina índices fuera de la ventana actual (izquierda)
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Elimina elementos menores que el actual (derecha)
while dq and nums[dq[-1]] < n:
dq.pop()
# 3. Añade el índice actual al deque
dq.append(i)
# 4. Añade el máximo (dq[0]) al resultado si la ventana está completa
if i >= k - 1:
res.append(nums[dq[0]])
return res
# Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
# Output: [3, 3, 5, 5, 6, 7] (máximos de [1,3,-1], [3,-1,-3],..., [6,7]).
Linked List
# Implementación básica
class Node:
def __init__(self, val=0, next=None):
self.val = val # Valor del nodo
self.next = next # Referencia al siguiente nodo
# Creamos una lista: 1 → 2 → 3
head = Node(1, Node(2, Node(3)))
# Ejemplo típico 1: Invertir lista
def reverse_list(head):
prev = None # Nodo previo inicialmente es None
curr = head # Empezamos en la cabeza de la lista
while curr: # Mientras no lleguemos al final
next_node = curr.next # Guardamos el siguiente nodo
curr.next = prev # Invertimos el enlace
prev = curr # Movemos prev al nodo actual
curr = next_node # Movemos curr al siguiente nodo
return prev # prev ahora es la nueva cabeza
# Imprimir lista invertida
def print_list(node):
while node:
print(node.val, end=" → ")
node = node.next
print("None")
# Ejemplo visual:
print_list(head)
# Original: 1 → 2 → 3 → None
new_head = reverse_list(head)
# paso 0: prev = None, curr = 1 → next=2
# Paso 1: next_node = 2, 1.next = None → prev=1, curr=2
# Paso 2: next_node = 3, 2.next = 1 → prev=2, curr=3
# Paso 3: next_node = None, 3.next=2 → prev=3, curr=None
print_list(new_head)
# Resultado: 3 → 2 → 1 → None
###########################################################################################
# Ejemplo típico 2: Tenemos dos listas enlazadas ordenadas: list1 y list2. Queremos unirlas en una nueva lista ordenada también, sin crear nodos nuevos si no es necesario.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def print_list(self, node: Optional[ListNode]):
while node:
print(node.val, end=" → ")
node = node.next
print("None")
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
self.print_list(dummy)
return dummy.next
head1 = ListNode(1, ListNode(2, ListNode(4)))
head2 = ListNode(1, ListNode(3, ListNode(4)))
sol = Solution().mergeTwoLists(head1, head2)
# Output: 0 → 1 → 1 → 2 → 3 → 4 → 4 → None
Hash Table (Diccionario)
# Implementación básica
d = {} # Creamos un diccionario vacío
d["key1"] = 10 # Insertamos un valor con clave "key1"
print(d.get("key1")) # Obtenemos el valor asociado a "key1" → 10
# Ejemplo típico 1: Contador de frecuencias
def count_freq(arr):
freq = {} # Diccionario para almacenar frecuencias
for num in arr: # Recorremos cada número en el arreglo
# Incrementamos el contador del número (o lo inicializamos en 0 si no existe)
freq[num] = freq.get(num, 0) + 1
return freq
# Ejemplo:
print(count_freq([1, 2, 2, 3])) # {1: 1, 2: 2, 3: 1}
###########################################################################################
# Ejemplo típico 2: Agrupar anagramas
def groupAnagrams(strs):
anagrams = {}
for word in strs:
key = tuple(sorted(word))
anagrams.setdefault(key, []).append(word)
return list(anagrams.values())
palabras = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams(palabras))
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Set
# Implementación básica
nums = [1, 2, 2, 3]
unique = set(nums) # {1, 2, 3}
print(2 in unique) # True
# Ejemplo típico: Substring más larga sin repetir caracteres
def lengthOfLongestSubstring(s):
seen = set()
left = res = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
res = max(res, right - left + 1)
return res
lengthOfLongestSubstring("abcabcbb")
# output: 3 (subcadenas como "abc" o "bca").
Array
# Implementación básica
arr = [1, 2, 3]
arr.append(4)
arr[1] = 10
print(arr) # [1, 10, 3, 4]
# Ejemplo típico: Mover ceros al final
def moveZeroes(nums: List[int]):
pos = 0
for num in nums:
if num != 0:
nums[pos] = num
pos += 1
for i in range(pos, len(nums)):
nums[i] = 0
aux = [0, 1, 0, 3, 12]
moveZeroes(aux)
print(aux)
# Output: [1, 3, 12, 0, 0]
###########################################################################################
# Ejemplo típico 2: Dado un arreglo de enteros nums ordenado en orden no decreciente, elimina los elementos duplicados en el mismo arreglo (in-place), de forma que cada elemento único aparezca una sola vez.
# El orden relativo de los elementos únicos debe mantenerse igual al original.
# Debes devolver el número k, que representa la cantidad de elementos únicos.
# Además, los primeros k elementos de nums deben contener los elementos únicos en el mismo orden en que aparecían originalmente.
# El resto de los elementos después del índice k no importa.
from typing import List
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
return i + 1
# Input: [0,0,1,1,1,2,2,3,3,4]
# Output: [0,1,2,3,4]
Heap (Montículo)
# Implementación basica
import heapq
min_heap = [] # Lista que funcionará como min-heap
heapq.heappush(min_heap, 3) # Insertamos 3 → [3]
heapq.heappush(min_heap, 1) # Insertamos 1 → [1, 3] (se reordena automáticamente)
print(heapq.heappop(min_heap)) # Extraemos el mínimo → 1, heap queda [3]
# Ejemplo típico: K elementos más grandes
import heapq
def k_largest(nums, k):
min_heap = [] # Usamos un min-heap para mantener los k más grandes
for num in nums: # Recorremos cada número
heapq.heappush(min_heap, num) # Añadimos el número al heap
if len(min_heap) > k: # Si el heap excede k elementos
heapq.heappop(min_heap) # Eliminamos el más pequeño
return min_heap # Al final, tendremos los k más grandes
# Ejemplo:
print(k_largest([4, 1, 7, 3, 8, 5], 3)) # [5, 7, 8]
Binary Tree
from collections import deque # Importamos deque para una cola eficiente
class TreeNode:
def __init__(self, val, left=None, right=None):
# Constructor del nodo del árbol:
# - val: valor del nodo (ej: 'A', 'B', etc.)
# - left: hijo izquierdo (por defecto None)
# - right: hijo derecho (por defecto None)
self.val = val
self.left = left
self.right = right
def bfs_tree(root):
# Verificamos si el árbol está vacío
if not root:
return [] # Si no hay raíz, retornamos lista vacía
# Inicializamos la cola con el nodo raíz
queue = deque([root])
# Lista para almacenar el orden de recorrido BFS
result = []
# Mientras haya nodos en la cola:
while queue:
# Sacamos el primer nodo de la cola (FIFO)
node = queue.popleft()
# Añadimos su valor al resultado
result.append(node.val)
# Si existe hijo izquierdo, lo añadimos a la cola
if node.left:
queue.append(node.left)
# Si existe hijo derecho, lo añadimos a la cola
if node.right:
queue.append(node.right)
# Retornamos el resultado del recorrido
return result
# Construimos el árbol de ejemplo:
# A
# / \
# B C
# / \ / \
# D E F G
root = TreeNode('A',
TreeNode('B',
TreeNode('D'),
TreeNode('E')),
TreeNode('C',
TreeNode('F'),
TreeNode('G')))
# Ejecutamos BFS e imprimimos el resultado
print("Recorrido BFS del árbol:", bfs_tree(root))
# Salida esperada: ['A', 'B', 'C', 'D', 'E', 'F', 'G']
Graph
from collections import deque # Importamos deque para una cola eficiente
def bfs_graph(graph, start, end):
# Inicializamos la cola con una tupla:
# - Primer elemento: nodo actual (start)
# - Segundo elemento: camino recorrido hasta ahora (inicia con [start])
queue = deque([(start, [start])])
# Conjunto para evitar revisitar nodos
visited = set([start])
# Mientras haya nodos por procesar en la cola:
while queue:
# Extraemos el primer elemento de la cola
node, path = queue.popleft()
# Si el nodo actual es el objetivo (end), retornamos el camino
if node == end:
return path
# Recorremos todos los vecinos del nodo actual
for neighbor in graph[node]:
# Si el vecino no ha sido visitado:
if neighbor not in visited:
visited.add(neighbor) # Lo marcamos como visitado
# Añadimos a la cola el vecino y el camino actualizado
queue.append((neighbor, path + [neighbor]))
# Si no se encuentra el objetivo, retornamos None
return None
# Definimos el grafo como diccionario de listas de adyacencia:
# - Las claves son nodos.
# - Los valores son listas de nodos conectados (vecinos).
graph = {
'A': ['B', 'C'], # 'A' está conectado a 'B' y 'C'
'B': ['A', 'D'], # 'B' está conectado a 'A' y 'D' (grafo no dirigido)
'C': ['A', 'D', 'E'],
'D': ['B', 'C', 'E'],
'E': ['C', 'D']
}
# Ejemplo: Buscamos el camino más corto de 'A' a 'E'
print("Camino más corto de A a E:", bfs_graph(graph, 'A', 'E'))
# Salida esperada: ['A', 'C', 'E']
Recursión
Una función recursiva es aquella que se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños.
# Estructura básica
def funcion_recursiva(parámetros):
if caso_base:
return resultado_base
else:
return llamada_recursiva(modificación_de_parámetros)
# Ejemplo típico 1: Factorial
def factorial(n: int) -> int:
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
### Forma iterativa
def factorial_iter(n: int) -> int:
result = 1
for i in range(2, n + 1):
result *= i
return result
# Ejemplo típico 2: Fibonacci
def fibonacci(n: int) -> int:
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
### Forma iterativa
def fibonacci_iter(n: int) -> int:
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Esta manera de resolver este problema se conoce como ingenua porque no guarda resultados anteriores (sin memoization), por lo que recalcula los mismos valores muchas veces.
# Además Tiene una complejidad exponencial: 𝑂(2ⁿ), lo que la hace impráctica para valores grandes de n.
# Ejemplo típico 3: Potencia (x^n)
def power(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
return 1 / power(x, -n)
if n % 2 == 0:
half = power(x, n // 2)
return half * half
else:
return x * power(x, n - 1)
### Forma iterativa
def power_iter(x: float, n: int) -> float:
result = 1.0
abs_n = abs(n)
while abs_n > 0:
if abs_n % 2 == 1:
result *= x
x *= x
abs_n //= 2
return result if n >= 0 else 1 / result
Búsqueda Lineal
- La búsqueda lineal o búsqueda secuencial es un algoritmo de búsqueda simple que recorre una colección elemento por elemento hasta encontrar el valor deseado o hasta que se haya recorrido todo sin éxito.
- Empieza desde el primer elemento de la colección.
- Compara ese elemento con el valor buscado.
- Si coinciden, se retorna su índice o posición.
- Si no, se avanza al siguiente elemento.
- Repite hasta encontrar el valor o llegar al final.
- Si no se encuentra, devuelve un indicador (por ejemplo, -1).
# Ejemplo típico 1
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Éxito: devuelve el índice
return -1 # Fallo: no encontrado
nums = [5, 3, 8, 2, 9]
print(linear_search(nums, 8)) # Output: 2
print(linear_search(nums, 7)) # Output: -1
###########################################################################################
# Ejemplo típico 2: Dado un arreglo de enteros nums ordenado en orden ascendente y un valor objetivo target, retorna el índice si target se encuentra en el arreglo.
# Si no se encuentra, retorna el índice en el que debería insertarse para mantener el orden.
# Se debe implementar un algoritmo con una complejidad de tiempo O(log n).
# Búsqueda lineal (más lenta)
from typing import List
def linear_search_insert(nums: List[int], target: int) -> int:
if nums[0] > target:
return 0
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)
### Lógica:
#### Si el primer elemento es mayor que el target → lo insertamos al inicio.
#### Recorremos toda la lista.
#### Si encontramos uno igual o mayor, lo insertamos ahí.
#### Si ninguno lo es, lo insertamos al final.
### Complejidad:
#### Tiempo: O(n) revisa elemento por elemento.
#### Espacio: O(1)
Búsqueda Binaria
- La búsqueda binaria es un algoritmo eficiente para buscar un valor dentro de una lista ordenada. Funciona reduciendo el espacio de búsqueda a la mitad en cada paso, comparando el valor objetivo con el elemento central de la colección.
- Selecciona el elemento central del arreglo o colección.
- Compara este elemento con el valor que estás buscando (el "objetivo").
- Si el elemento central es igual al objetivo, la búsqueda termina y se retorna su índice.
- Si el elemento central es mayor que el objetivo, continúa la búsqueda en la mitad izquierda.
- Si el elemento central es menor que el objetivo, continúa en la mitad derecha.
- Repite los pasos 2 a 5 hasta encontrar el elemento o agotar la búsqueda (cuando los límites se cruzan).
# Ejemplo típico 1: Dado un arreglo de enteros nums ordenado en orden ascendente y un valor objetivo target, retorna el índice si target se encuentra en el arreglo.
# Si no se encuentra, retorna el índice en el que debería insertarse para mantener el orden.
# Se debe implementar un algoritmo con una complejidad de tiempo O(log n).
# Búsqueda lineal (más lenta)
from typing import List
def linear_search_insert(nums: List[int], target: int) -> int:
if nums[0] > target:
return 0
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)
### Lógica:
#### Si el primer elemento es mayor que el target → lo insertamos al inicio.
#### Recorremos toda la lista.
#### Si encontramos uno igual o mayor, lo insertamos ahí.
#### Si ninguno lo es, lo insertamos al final.
### Complejidad:
#### Tiempo: O(n) revisa elemento por elemento.
#### Espacio: O(1)
# Bpusqueda Binaria (más rápida)
def binary_search_insert(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
### Lógica:
#### Empezamos con left al inicio y right al final.
#### Calculamos mid como el punto medio.
#### Si encontramos el target → devolvemos mid.
##### Si no:
##### Si es menor → buscamos en la mitad derecha.
##### Si es mayor → buscamos en la mitad izquierda.
##### Si no está → left es el índice de inserción.
### Complejidad:
#### Tiempo: O(log n) divide el problema a la mitad en cada iteración.
#### Espacio: O(1)
###########################################################################################
# Ejemplo típico 2: Calculo de la raíz cuadrada
def mySqrt(self, x: int) -> int:
if x < 2:
return x # Si x es 1 o 0 no hay más que hacer
left, right = 1, x // 2 # La raíz cuadrada nunca es mayor que la mitad del número
while left <= right:
mid = (left + right) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right # Cuando left > right, right es el entero más cercano tal que right*right <= x