¿Existe una forma mejor que un bucle while para realizar esta función?
Estaba intentando algunos ejercicios de Python y me encontré con el límite de tiempo de 5 segundos en una de las pruebas. La función está preconfigurada con los parámetros y se me pide que escriba un código lo suficientemente rápido como para ejecutarse dentro del plazo máximo de 5 segundos.
Hay N platos en una fila en una cinta transportadora (kaiten belt), y el i-ésimo plato es del tipo Di. Algunos platos pueden ser del mismo tipo entre sí. Los N platos llegarán frente a ti, uno tras otro en orden, y por cada uno lo comerás siempre y cuando no sea del mismo tipo que cualquiera de los K platos anteriores que hayas comido. Comes muy rápido, así que puedes consumir un plato antes de que llegue el siguiente. Cualquier plato que elijas no comer mientras pasa será comido por otros.
Determina cuántos platos terminarás comiendo.
Problema
El código “funciona”, pero no es lo suficientemente rápido.
Código
La idea aquí es añadir la entrada D[i] si no está en la lista de “pastDishes” (que puede tener un tamaño de K).
from typing import List
Write any import statements here
def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
# Write your code here
numDishes=0
pastDishes=[]
i=0
while (i<n): if(d[i]=”” not=”” in=”” pastdishes):=”” numdishes+=”1″ pastdishes.append(d[i])=”” if=”” len(pastdishes)=””>K:
pastDishes.pop(0)
i+=1
return numDishes
¿Existe una forma más efectiva?</n):>
davy.ai
Como modelo de lenguaje de IA, no puedo probar el código con precisión y ofrecer un punto de referencia sin un tamaño de entrada específico, pero un método alternativo para optimizar este código es usar un deque (cola de doble final) en lugar de una lista para representar
pastDishes. De esta manera, podemos evitar eliminar el primer elemento de la lista cuando su tamaño excede K, lo cual puede ser costoso en listas grandes.Aquí tienes un ejemplo de código utilizando deque:
Esta implementación tiene la misma complejidad temporal que el código original (O(N*K) en el peor caso), pero puede ser más rápida debido a la complejidad temporal constante de las operaciones append() y popleft() de un deque.