Plantilla
Otra idea es usar dos punteros como variables. En todo el proceso del algoritmo, las variables almacenan estados intermedios y participan en el cálculo para generar nuevos estados.
1234567# old & nuevo estado: old, new = new, cur_resultdefold_new_state(self, seq):# inicializar estado old, new = default_val1, default_val2 para el elemento en seq:# procesar elemento actual con estado old, new = new, self.process_logic(element, old)
Python
Para explicar mejor el principio del viejo y del nuevo estado, he dibujado un ejemplo de transición de estado.
En el diagrama de flujo, podemos ver que hay tres pasos de proceso en cada iteración:
- Calcular cur_resultado basado en el estado_antiguo y el cur_elemento de la secuencia.
- Antes de asignar cur_resultado a new_state, almacena primero el valor de new_state a old_state.
- Considerar el resultado como el nuevo estado.
Después de atravesar toda la secuencia, los resultados se calculan en base a old_state y new_state.
Al igual que el corredor lento y rápido, esta plantilla representa sólo el uso típico. La plantilla y el diagrama de flujo de arriba te ayudan a entender la idea. Cuando migras a un escenario complejo, necesitarás hacer algunas extensiones y reformas.
Ejemplos
Un ejemplo simple y clásico es el cálculo de un número de Fibonacci.
123456# [509] https://leetcode.com/problems/fibonacci-number/deffibonacci(n:int)-;int: a, b =0,1for i inrange(n +1): a, b = b, a + b return a
pitón
Un ejemplo con el elemento actual involucrado:
123456# [198] https://leetcode.com/problems/house-robber/defrob(nums:$0027List[int]$0027)- >int: last, now =0,0for i in nums: last, now = now,max(last + i, now)return now
pitón
En una definición más amplia, estas dos variables que mantenemos no son necesariamente la relación entre el primer estado y el segundo estado.
Aquí hay dos usos más generales de la técnica de los dos punteros.
12345678# [21] https://leetcode.com/problems/merge-two-sorted-lists/# primero asegúrate de que a es el "mejor" (lo que significa que b es Ninguno o tiene un valor mayor/igual). Luego fusiona los restos detrás de a.defmergeTwoLists(a:$0027ListNode$0027, b:$0027ListNode$0027)- >$0027ListNode$0027:ifnot a o b y a.val > b.val: a, b = b, a if a: a.next= mergeTwoLists2(a.next, b)return a
pitón
Un ejemplo más complejo con lógica ramificada y abstracción compleja:
12345678910111213141516# [91] https://leetcode. com/problemas/decodificar vías/defnumDecodificaciones(s:str)- >int:iflen(s)>0y s[0]>$00270$0027: a, b =1,1else:return0for i inrange(1,len(s)):if s[i]==$00270$0027: si s[i -1]>$00272$0027o s[i -1]==$00270$0027:return0 a, b =0, a elif s[i -1]==$00271$0027or(s[i -1]==$00272$0027y s[i]<$00277$0027): a, b = b, a + b else: a, b = b, b return b
pitón
A partir de los ejemplos anteriores, podemos ver que la técnica de los dos punteros simplifica la complejidad de los problemas de los algoritmos y los convierte en la definición y transformación de los estados.