Plantilla
Otro uso común es poner punteros en el lado más izquierdo y en el más derecho. Un puntero comienza desde el principio, mientras que el otro puntero comienza desde el final. Se mueven hacia el otro hasta que se encuentran en el medio.
123456789101112# left & right boundary: left- >-rightdefleft_right_boundary(self, seq): left, right =0,len(seq)-1while left < right:# el índice de la izquierda se mueve cuando se satisface la condiciónif self. left_condition(left): left +=1# índice de la derecha se mueve cuando se satisface la condiciónif self.right_condition(right): right -=1# lógica del proceso antes o después de los punteros movimiento self.process_logic(left, right)
Python
Para comprender mejor la teoría de los límites izquierdo y derecho, puede consultar el siguiente cuadro de ejemplo.
En general, el algoritmo puede ser usado de dos maneras basadas en esta tecnología:
- Los punteros izquierdo y derecho forman un intervalo para procesar.
- Estos dos punteros llevan información y manejan la lógica en cada iteración.
Ejemplos
El ejemplo más clásico y famoso es la búsqueda binaria. Encontramos el objetivo encogiendo los límites inferiores y superiores continuamente. Cortamos la mitad del intervalo en cada iteración. El siguiente ejemplo es una versión con los límites inferiores y superiores incluidos.
123456789101112# [lo, hi] versión, modifique a la versión [lo, hi] como necesitedefbinary_search(arr, target): lo, hi =0,len(arr)-1while lo <= hi: mid =(lo + hi)//2# encuentre el objetivo, cambie a su condición de comparación como necesiteif arr[mid]== target:breakelif arr[mid]< target: lo = mid +1else: hi = mid -1
pitón
Veamos un ejemplo práctico con dos punteros y una técnica de búsqueda binaria.
1234567891011# [167] https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/deftwoSum(numbers:$0027List[int]$0027, target:$0027int$0027)- >$0027List[int]$0027: left, right =0,len(numbers)-1while left < right:if numbers[left]+ numbers[right]== target:return[left +1, right +1]if numbers[left]+ numbers[right]< target: left +=1else: right -=1return[0,0]
pitón
Hagámoslo un poco más difícil. Sube el problema de las dos sumas a las cuatro sumas.
Idea : Con la ayuda del ejemplo anterior, la solución es muy clara. Podemos usar los límites izquierdo y derecho para encontrar el espacio de la solución. Podemos dividir el problema de cuatro sumas en tres sumas, y finalmente en dos sumas.
123456789101112131415161718192021222324252627282930313233343536373839404142434445# [18] https://leetcode. com/problems/4sum/deffourSum(nums:$0027List[int]$0027, target:int)- >$0027List[int]$0027: resultado, n =[],len(nums)if n <4:return result nums =sorted(nums)ifsum(nums[-4:])< target:return result for i inrange(n -3): # verificador del límite, detener earlyifsum(nums[i:i +4])> objetivo:romper# verificador del límite derecho nums[i]+sum(nums[-3:])< objetivo:continuar# saltarse el mismo elemento, pero mantener el primer oneif i >0y nums[i]== nums[i -1]: continue# simplifica el problema a tres suma target2 = target - nums[i]for j inrange(i +1, n -2):ifsum(nums[j:j +3])> target2 orsum(nums[-3:])< target2:breakif nums[j]+sum(nums[-2:])< target2: continueif j > i +1y nums[j]== nums[j -1]:continue# simplifican el problema a dos sumas target3 = target2 - nums[j] left = j +1 right = n -1while left < right:si nums[left]+ nums[right]== target3: resultado. append([nums[i], nums[j], nums[izquierda], nums[derecha]])mientras que la izquierda < derecha y nums[izquierda]== nums[izquierda +1]: izquierda +=1mientras que la izquierda < derecha y nums[derecha]== nums[derecha -1]: derecha -=1 izquierda +=1 derecha -=1elif nums[izquierda]+ nums[derecha]< target3: izquierda +=1else: derecha -=1resultado
pitón
He aquí un ejemplo en el que nos centramos en el intervalo.
Idea : Para ayudarte a entender, he dibujado un diagrama de ejemplo. Calculamos el área de agua por el intervalo formado por los límites izquierdo y derecho de la corriente.
12345678910111213141516171819202122# [11] https://leetcode. com/problemas/contenedor-con-la-mayor-agua/defmaxÁrea(altura:$0027List[int]$0027)-;int: izquierda, derecha =0,len(altura)-1 área_max =(derecha - izquierda)*min(altura[izquierda], altura[derecha])mientras que la izquierda < derecha: # juzgar qué lado decide el área (altura más corta)si altura[izquierda]<= altura[derecha]: last_height = altura[izquierda]# saltar toda la altura menos que la actual mientras altura[izquierda]<= last_height e izquierda < derecha: izquierda +=1else: last_height = height[right]# salta toda la altura menor que la actual mientras que height[right]<= last_height y left < right: right -=1if left >= right:return area_max area_max =max(area_max,(right - left)*min(height[left], height[right]))return area_max
pitón