Plantilla
La ventana corrediza es una técnica de algoritmo útil para los escenarios típicos. El uso de la plantilla puede simplificar enormemente la lógica del algoritmo. Hay una premisa: debemos determinar si es adecuado para nuestro escenario particular, y necesitamos hacer una abstracción razonable. Esta plantilla está inspirada en estas dos discusiones en LeetCode:
La plantilla de la ventana corrediza es un poco difícil de entender. Así que empezaremos con una versión simple, que se centra sólo en los dos punteros. Usamos los punteros de inicio y final para crear una ventana. Luego movemos estos dos punteros para hacer que la ventana se deslice.
1234567891011121314151617# start & fin de la ventana corrediza: |start-&; ... end|;|# versión corta de la ventana corredera, foco en dos punterossdefstart_end_sliding_window(self, seq): start, end =0,0while end <len(seq):# puntero final crece en el bucle exterior end +=1# puntero de inicio crece con algún restrictivo self. start_condition(start):# lógica del proceso antes de los punteros movimiento self.process_logic1(start, end)# inicio crece en el bucle interior inicio +=1# o lógica del proceso después de los punteros movimiento self.process_logic2(start, end)
Python
De la plantilla y el diagrama anteriores, podemos ver que el puntero final crece en el bucle exterior mientras que el puntero inicial crece en el bucle interior. La lógica de la ventana corrediza debe ser procesada antes de que el puntero de inicio crezca o al final del bucle exterior. Discutiremos la lógica específica en la siguiente plantilla.
Aquí hay una versión más específica de la ventana corrediza:
1234567891011121314151617181920212223242526272829303132333435363738394041# versión más específica de la ventana corrediza# s - secuencia de la fuente, p - patrón o restringir la secuencia de la ventana corrediza_plantilla_con_ejemplos(s, p): # inicializar el mapa hash# contador se usa para registrar el estado actual, normalmente usa Counter o defaultdict counter = Counter(p)# dos punteros, límite de inicio de la ventana corredera, end =0,0# verificador de condición, actualizarlo cuando se disparan algunos cambios de clave# el valor inicial depende de su situación count =0# resultado, return int (como max o min) o list (como all index) res =0# bucle la secuencia de origen desde el principio hasta el final counter[s[end]]+=1# actualiza el conteo basado en alguna condicionif counter[s[end]];1: count +=1# end el puntero crece en el extremo del bucle externo +=1# condición de conteo, la condición puede ser diferente mientras count >0: $0027$0027$0027 update res here if finding minimum $0027$0027$0027# aumentar el puntero de inicio para hacerlo inválido o válido de nuevo counter[s[start]]-=1# actualizar la cuenta en base a alguna condicionif counter[s[start]]>0: count -=1# el puntero de inicio crece en el bucle interior start +=1$0027$0027$0027 update res here if finding maximum $0027$0027$0027# la lógica del resultado puede ser diferente res =max(res, end - start)return res
pitón
Basándonos en la primera versión, hemos añadido más componentes lógicos en esta plantilla.
- El contador se suele definir como un mapa de hachís (por defecto o contador en Python). Se utiliza para registrar el estado actual.
- El recuento funciona como un comprobador de la condición. Lo actualizamos cuando se activan algunos cambios clave. Se utiliza principalmente para la condición del bucle interno.
- res representa el resultado a lograr. El tipo de datos de res depende del requisito, como int (máximo o mínimo) o lista (obtener todo el índice).
Para hacer el proceso más claro, hice un diagrama de flujo:
Desde la perspectiva del flujo de procesos, el algoritmo se divide en el bucle exterior y el bucle interior.
- Como mencionamos antes, el puntero final crece en cada iteración externa mientras que el puntero inicial crece en cada iteración interna.
- El bucle exterior maneja la lógica del puntero final. Actualizamos el contador[s[end]], lo que afecta a la actualización de la cuenta. De esa manera, afectará al bucle interior indirectamente.
- El bucle interno maneja la lógica del puntero de inicio. Actualizamos el contador y contamos de la misma manera.
- Si encontramos el mínimo, actualizamos la lógica de la res al principio del bucle interior. Si encontramos el máximo, actualizamos la lógica de la res al final del bucle exterior.
Cabe señalar que esta plantilla es sólo para los procesos más comunes. Demuestra la idea central del algoritmo, pero necesita ser reformada o decorada para una escena más compleja. Muchas partes necesitan ser ajustadas de acuerdo con el escenario real, como la definición de la condición del bucle interno, la forma de actualizar el contador y cómo calcular la res.
Ejemplos
Tal vez aún estés confundido sobre cómo usar la técnica de la ventana corrediza. No se preocupe. Nos familiarizaremos con ella a través de un par de ejemplos típicos con variaciones.
La técnica de la ventana corrediza se utiliza principalmente para resolver el problema de la búsqueda de subcadenas. En primer lugar, veamos un ejemplo de búsqueda mínima. Como muestra la plantilla, deberíamos poner la lógica del resultado al principio del bucle interior.
123456789101112131415161718192021# [76] https://leetcode.com/problems/minimum-window-substring/defminWindow(s:str, t:str)-[str: counter = contador(t) cuenta, inicio, fin, res =len(t),0,0,[float($0027inf$0027),0]while end <len(s): counter[s[end]]-=1# considera caracteres duplicados en tif counter[s[end]]=0: cuenta -=1 fin +=1# válido en whilewhile count ==0: # actualizar mínimo aquí, interior while loopif end - start < res[0]: res =(end - start, start) counter[s[start]]+=1if counter[s[start]];0: count +=1 start +=1 return s[res[1]:res[0]+ res[1]]if res[0]! =flota($0027inf$0027)else$0027$0027
pitón
Aquí hay un ejemplo sin patrón involucrado:
123456789101112131415161718# [3] https://leetcode. com/problemas/sustitución más larga-sin-carácteres repetidos/deflecto-de-sustitución más larga(s:str)-;int:# crear un dict por defecto para mantener el estado counter = defaultdict(int) count, start, end, res =0,0,0,0while end <len(s): counter[s[end]]+=1if counter[s[end]];1: count +=1 end +=1while count >0: counter[s[start]]-=1if counter[s[start]]>0: count -=1 start +=1# actualizar máximo aquí res =max(res, end - start)return res
pitón
Además de los problemas de subcadena, también podemos aplicar la ventana corrediza a otros escenarios similares.
En este problema, necesitamos encontrar la longitud del subconjunto más largo con no más de dos números enteros distintos (tipos de fruta).
1234567891011121314151617# [904] https://leetcode. com/problemas/fruta-en-cestas/deftotalFruta(árbol:$0027List[int]$0027)- >int: counter = defaultdict(int) count, start, end, res =0,0,0,0while end <len(árbol): counter[tree[end]]+=1if counter[tree[end]]==1: count +=1 end +=1while count >2: counter[tree[start]]-=1if counter[tree[start]]==0: count -=1 start +=1 res =max(res, end - start)return res
pitón
Un ejemplo más complejo con una política compleja de partidos:
123456789101112131415161718192021222324252627282930# [30] https://leetcode. com/problemas/sustitución-con-concentración-de-todas-las-palabras/deffindSubstring(s:str, palabras:$0027List[str]$0027)- >$0027List[int]$0027:ifnot palabras:return[] word_len, res =len(palabras[0]),[]# inicio desplazamiento de 0 a word_len, y el paso es word_lenfor i inrange(word_len): # reset state every epoch counter = Counter(words) start,<len<, count = i, i,len(words)while end <len(s): cur_word = s[end:end + word_len]# check is not necessary here, just for performanceif cur_word in counter: counter[cur_word]-=1if counter[cur_word]>=0: count -=1 end += word_len if count ==0: res. append(start)# no usar un rato, usar restricción de longitud para asegurar palabras consecutivasif end - start == word_len *len(words): cur_word = s[start:start + word_len]if cur_word in counter: counter[cur_word]+=1if counter[cur_word]>0: count +=1 start += word_len return res
pitón
A partir de los ejemplos anteriores, podemos ver que la técnica de la ventana corrediza simplifica la complejidad del problema del algoritmo y lo descompone en partes lógicas de la plantilla.