8.5 Problemas de práctica

Problema 1: Arrays - Suma máxima de subarreglo

Problema: Dado un array de enteros nums, encuentra el subarreglo contiguo (que contenga al menos un número) que tenga la suma más grande y devuelve su suma.

Solución: Podemos resolver este problema utilizando el algoritmo de Kadane. Aquí tienes un código en Python para este problema.

def max_subarray(nums):
    if not nums:
        return 0

    curr_sum = max_sum = nums[0]

    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problema 2: Listas enlazadas - Invertir una lista enlazada

Problema: Dado el nodo inicial de una lista enlazada simple, invierte la lista y devuelve la lista invertida.

Solución: Podemos resolver este problema invirtiendo iterativamente los punteros de la lista enlazada.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Problema 3: Pilas - Paréntesis válidos

Problema: Dada una cadena s que contiene solo los caracteres '(', ')', '{', '}', '[' y ']', determina si la cadena de entrada es válida. Una cadena de entrada es válida si: Los corchetes abiertos deben cerrarse con el mismo tipo de corchetes, y los corchetes abiertos deben cerrarse en el orden correcto.

Solución: Este problema se puede resolver utilizando una pila.

def isValid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

print(isValid("()[]{}"))  # output: True

Problema 4: Árboles - Profundidad máxima de un árbol binario

Problema: Dado el nodo raíz de un árbol binario, devuelve su profundidad máxima. La profundidad máxima de un árbol binario es el número de nodos a lo largo del camino más largo desde el nodo raíz hasta el nodo hoja más lejano.

Solución: Este problema se puede resolver utilizando un algoritmo de búsqueda en profundidad (DFS, por sus siglas en inglés).

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_height = maxDepth(root.left)
        right_height = maxDepth(root.right)
        return max(left_height, right_height) + 1

Recuerda tomarte un tiempo para entender estos problemas y sus soluciones. La práctica es la clave para dominar el uso de estas estructuras de datos. ¡Feliz codificación!