1. Problema de la Gasolinera

Imagina que te encuentras en una ruta circular con n estaciones de servicio. En cada estación i, dispones de gas[i] litros de combustible. Para desplazarte de la estación i a la estación i+1, tu vehículo consume cost[i] litros.

Tu coche tiene un depósito de combustible de capacidad ilimitada y comienzas con el depósito vacío. El objetivo es determinar el índice de la estación de servicio desde la cual debes iniciar tu recorrido para completar una vuelta completa al circuito. Si existe una solución, se garantiza que es única. Si no es posible completar el circuito, debes retornar -1.

Ejemplo 1:

<strong>Entrada:</strong> gas = [1,2,3,4,5], cost = [3,4,5,1,2]
<strong>Salida:</strong> 3
<strong>Explicación:
</strong>Saliendo de la estación 3 (índice 3), obtienes 4 litros. Tanque = 0 + 4 = 4.
Viajas a la estación 4. Tanque = 4 - 1 + 5 = 8.
Viajas a la estación 0. Tanque = 8 - 2 + 1 = 7.
Viajas a la estación 1. Tanque = 7 - 3 + 2 = 6.
Viajas a la estación 2. Tanque = 6 - 4 + 3 = 5.
Para regresar a la estación 3, necesitas 5 litros, lo cual es justo lo que tienes.
Por lo tanto, el índice inicial es 3.

Análisis y Estrategia

Para resolver este problema, podemos emplear una estrategia voraz. Primero, es crucial entender que si la suma total de combustible disponible en todas las estaciones es menor que el consumo total requerido para recorrer todo el circuito, entonces es imposible completar la vuelta, sin importar el punto de partida. En este caso, retornamos -1.

Si el combustible total es suficiente, una solución siempre existirá. La clave está en encontrar el punto de partida. Si durante el recorrido acumulamos un déficit de combustible (es decir, el tanque se vacía antes de llegar a la siguiente estación), significa que el punto de partida actual no es válido. En ese caso, debemos intentar iniciar desde la estación siguiente a aquella donde el déficit ocurrió, reiniciando el contador de combustible acumulado.

Este enfoque funciona porque si llegamos a una estación con combustible negativo, cualquier estación anterior en el segmento que llevó a ese negativo tampoco podría haber sido el punto de partida. Al reiniciar desde la estación siguiente, estamos buscando un nuevo segmento donde la acumulación de combustible sea positiva desde el inicio.

class SolucionGasolinera:
    def puedeCompletarCircuito(self, combustible, gasto):
        litros_totales = 0  # Combustible total acumulado a lo largo de todo el circuito
        tanque_actual = 0   # Combustible en el tanque desde el último punto de partida potencial
        indice_inicio = 0   # Índice del punto de partida potencial

        num_estaciones = len(combustible)

        for i in range(num_estaciones):
            diferencia_combustible = combustible[i] - gasto[i]
            tanque_actual += diferencia_combustible
            litros_totales += diferencia_combustible

            # Si el tanque se vacía (o tiene menos de cero), este punto de partida no es válido
            if tanque_actual < 0:
                indice_inicio = i + 1  # El siguiente punto de partida potencial es la estación actual + 1
                tanque_actual = 0      # Reiniciar el tanque para el nuevo intento
        
        # Si el combustible total acumulado es negativo, no hay solución posible
        if litros_totales < 0:
            return -1
        else:
            return indice_inicio # De lo contrario, el último indice_inicio encontrado es la solución

2. Distribución de Dulces

Se tienen n niños formados en una fila, y se te proporciona un arreglo de enteros calificaciones que representa la puntuación de cada niño.

Debes repartir dulces a estos niños siguiendo estas reglas:

• Cada niño debe recibir al menos un caramelo.
• Si dos niños adyacentes tienen diferentes calificaciones, el niño con la calificación más alta debe recibir más dulces.

Calcula y retorna la cantidad mínima de dulces necesaria para satisfacer todas las condiciones.

Ejemplo 1:

<strong>Entrada:</strong> calificaciones = [1,0,2]
<strong>Salida:</strong> 5
<strong>Explicación:</strong> Se pueden distribuir 2, 1, 2 dulces respectivamente.

Análisis y Estrategia

Este problema se puede resolver con un algoritmo voraz en dos pasadas. La clave es abordar las condiciones de forma independiente para evitar contradicciones. Si intentamos considerar ambas condiciones (comparar con el vecino izquierdo y el vecino derecho) al mismo tiempo, podríamos anular un requisito mientras intentamos satisfacer el otro.

El enfoque consiste en:

1. Inicializar a cada niño con un caramelo.
2. Primera pasada (de izquierda a derecha): Recorrer los niños desde el segundo hasta el último. Si la calificación del niño actual es mayor que la de su vecino izquierdo, el niño actual debe recibir un caramelo más que su vecino izquierdo. Esto asegura la condición para las relaciones "derecha > izquierda".
3. Segunda pasada (de derecha a izquierda): Recorrer los niños desde el penúltimo hasta el primero. Si la calificación del niño actual es mayor que la de su vecino derecho, el niño actual debe tener más caramelos que su vecino derecho. En este punto, el niño actual ya tiene una cantidad de caramelos asignada de la primera pasada. Debemos tomar el máximo entre la cantidad ya asignada y (caramelos_del_vecino_derecho + 1). Esto es crucial para satisfacer ambas condiciones si un niño es mejor calificado que ambos vecinos.

Este proceso garantiza que ambas condiciones se satisfagan con el mínimo número de dulces, ya que solo aumentamos los dulces cuando es estrictamente necesario.

class SolucionDulces:
    def distribuirDulces(self, calificaciones):
        num_ninos = len(calificaciones)
        
        # Cada niño empieza con al menos un dulce
        conteo_dulces = [1] * num_ninos

        # Primera pasada: de izquierda a derecha
        # Asegura que si calificaciones[i] > calificaciones[i-1], entonces conteo_dulces[i] > conteo_dulces[i-1]
        for i in range(1, num_ninos):
            if calificaciones[i] > calificaciones[i-1]:
                conteo_dulces[i] = conteo_dulces[i-1] + 1
        
        # Segunda pasada: de derecha a izquierda
        # Asegura que si calificaciones[i] > calificaciones[i+1], entonces conteo_dulces[i] > conteo_dulces[i+1]
        # Y toma el máximo para mantener la condición de la primera pasada si ya se había asignado más.
        for i in range(num_ninos - 2, -1, -1):
            if calificaciones[i] > calificaciones[i+1]:
                conteo_dulces[i] = max(conteo_dulces[i], conteo_dulces[i+1] + 1)
        
        # La suma total de los dulces distribuidos
        return sum(conteo_dulces)

3. Cambio de Limonada

En un puesto de limonada, cada vaso se vende por 5 dólares. Los clientes pagan en orden con billetes de 5, 10 o 20 dólares. Debes dar el cambio exacto a cada cliente, de modo que la transacción neta sea siempre de 5 dólares por vaso.

Al inicio, no tienes cambio. Se te proporciona un arreglo de enteros pagos, donde pagos[i] es el billete que paga el i-ésimo cliente. Determina si puedes dar el cambio corretco a todos los clientes. Retorna True si es posible, False en caso contrario.

Ejemplo 1:

<strong>Entrada:</strong> pagos = [5,5,5,10,20]
<strong>Salida:</strong> true
<strong>Explicación:
</strong>Los primeros 3 clientes pagan con $5. Tenemos tres billetes de $5.
El 4º cliente paga con $10. Damos un billete de $5 de cambio. Nos quedan dos $5 y un $10.
El 5º cliente paga con $20. Damos un billete de $10 y uno de $5 de cambio.
Como todos los clientes reciben cambio, el resultado es true.

Análisis y Estrategia

Este problema se presta a una solución voraz, donde la clave es cómo manejar el cambio para los billetes de 20 dólares. Necesitamos mantener un registro del número de billetes de 5 y 10 dólares que tenemos disponibles.

• Si un cliente paga con 5 dólares: Simplemente lo aceptamos y aumentamos nuestro conteo de billetes de 5. No se necesita dar cambio.
• Si un cliente paga con 10 dólares: Necesitamos dar un billete de 5 dólares de cambio. Si tenemos uno disponible, lo usamos y aumentamos nuestro conteo de billetes de 10. Si no tenemos billetes de 5, no podemos dar cambio, y la respuesta es False.
• Si un cliente paga con 20 dólares: Necesitamos dar 15 dólares de cambio. Aquí es donde entra la estrategia voraz:
  • Preferimos dar un billete de 10 dólares y uno de 5 dólares (10 + 5 = 15). Esta es la opción óptima porque los billetes de 5 dólares son más "versátiles" y pueden ser necesarios para futuros cambios de billetes de 10.
  • Si no podemos dar un billete de 10 y uno de 5, intentaremos dar tres billetes de 5 dólares (5 + 5 + 5 = 15). Esta es nuestra segunda opción.
  • Si ninguna de las opciones anteriores es posible, no podemos dar cambio, y la respuesta es False.

Simularemos las transacciones cliente por cliente y actualizaremos nuestros billetes disponibles. Si en algún momento no podemos dar el cambio, retornamos False. Si completamos todas las transacciones, retornamos True.

class SolucionCambioLimonada:
    def puedeDarCambio(self, pagos):
        cantidad_cinco = 0  # Billetes de 5 dólares disponibles
        cantidad_diez = 0   # Billetes de 10 dólares disponibles

        for pago_cliente in pagos:
            if pago_cliente == 5:
                cantidad_cinco += 1
            elif pago_cliente == 10:
                # Para un pago de 10, necesitamos un billete de 5 de cambio
                if cantidad_cinco > 0:
                    cantidad_cinco -= 1
                    cantidad_diez += 1
                else:
                    return False
            else: # pago_cliente == 20
                # Para un pago de 20, necesitamos 15 de cambio
                # Priorizamos dar un billete de 10 y uno de 5
                if cantidad_diez > 0 and cantidad_cinco > 0:
                    cantidad_diez -= 1
                    cantidad_cinco -= 1
                # Si no podemos con 10 y 5, intentamos con tres billetes de 5
                elif cantidad_cinco >= 3:
                    cantidad_cinco -= 3
                else:
                    return False # No hay cambio posible
        
        return True # Todos los clientes recibieron su cambio correctamente

4. Reconstrucción de Cola por Altura

Se tiene una cola de personas con el orden desorganizado. El arreglo personas contiene atributos para algunas de estas personas, donde personas[i] = [altura_i, k_i] indica que la i-ésima persona tiene una altura altura_i y hay exactamente k_i personas delante de ella en la cola que tienen una altura mayor o igual que altura_i.

Tu tarea es reconstruir y retornar la cola original en el formato cola_reconstruida, donde cola_reconstruida[j] = [altura_j, k_j] representa los atributos de la j-ésima persona en la cola.

Ejemplo 1:

<strong>Entrada:</strong> personas = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
<strong>Salida:</strong> [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Análisis y Estrategia

Este problema es un clásico ejemplo donde una estrategia voraz de ordenamiento e inserción incremental funciona de maravilla. La clave está en cómo el valor k_i se ve afectado por la inserción de otras personas.

Si ordenamos a las personas de mayor a menor altura, y en caso de empate de altura, de menor a mayor k_i, podemos construir la cola de la siguiente manera:

1. Ordenar las personas:

   • Primero, ordenamos el arreglo personas en orden descendente por altura (altura_i).
   • Si dos personas tienen la misma altura, las ordenamos en orden ascendente por su valor k_i.

   ¿Por qué este ordenamiento? Al procesar a las personas más altas primero, el valor k_i de una persona P solo se ve afectado por otras personas que son tan altas o más altas que P. Si ya hemos insertado a todas las personas tan altas o más altas que P, entonces k_i simplemente indica la posición exacta donde P debe ser insertada en la cola parcial.

2. **Insertar en la cola:**Iteramos a través de la lista de personas ya ordenada. Para cada persona [altura, k], la insertamos en el índice k de nuestra cola resultante. Dado el ordenamiento, cuando insertamos a una persona P, todas las personas que ya están en la cola son más altas o de igual altura que P, por lo que el valor k para P cuenta con precisión cuántas de esas personas están delante de ella.

Las personas más bajas que aún no se han insertado no afectan el conteo k_i de las personas ya insertadas porque son más bajas.

class ReconstructorCola:
    def reconstruirCola(self, personas):
        # Primero, ordenar el arreglo de personas
        # Criterio de ordenamiento:
        #   1. Altura (h) descendente: las personas más altas primero
        #   2. Si alturas son iguales, k ascendente: entre personas de misma altura,
        #      aquellas con menos personas 'delante' van primero
        personas.sort(key=lambda p: (-p[0], p[1]))

        cola_final = []

        # Luego, insertar cada persona en la posición k-ésima
        # El índice k representa el número de personas con altura >= h delante de p
        for persona in personas:
            # Dado que las personas están ordenadas de h alta a baja,
            # cuando insertamos una persona en la posición k, todas las personas
            # ya en la cola son más altas o de igual altura, validando k.
            cola_final.insert(persona[1], persona)
        
        return cola_final