Invertir cada bloque de k
La misión
Problema
Dada una lista y un entero positivo k, invierte el orden de los valores dentro de cada bloque consecutivo de k valores: los primeros k, luego los siguientes k, y así sucesivamente. Si la longitud no es múltiplo de k, el último bloque es más corto que k y queda como está. Trabaja in-place (sin memoria extra) con O(1) de espacio extra y devuelve la misma lista.
Ejemplos
Input: nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 7, 8]
Por qué: se invierten dos bloques completos; 7 y 8 forman un bloque corto
Input: nums = [1, 2, 3, 4], k = 4
Output: [4, 3, 2, 1]
Por qué: un solo bloque cubre toda la lista
Input: nums = [5, 6], k = 3
Output: [5, 6]
Por qué: caso límite: no hay ningún bloque completo
Pistas
0 / 3
Divide mentalmente la lista en fragmentos de k a partir del índice 0. Cada fragmento completo es su propia pequeña inversión, independiente de las demás.
Una inversión in-place solo necesita dos índices que intercambian valores y avanzan el uno hacia el otro. Lo que queda por resolver es dónde empieza y termina cada fragmento.
Recorre los inicios de bloque 0, k, 2k, etc., y detente antes de un inicio cuyo bloque se pasaría del final. En cada bloque, intercambia los valores de sus dos extremos y mueve ambos índices hacia adentro hasta que se encuentren.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- k is a positive integer
- a final block shorter than k stays as it is
- in place with O(1) extra space
Solución
Los inicios de bloque son 0, k, 2k, etc., y un bloque solo se invierte cuando existen sus k valores, algo que garantiza el límite del rango len(nums) - k + 1. Cada bloque se invierte con dos índices que intercambian valores y se encuentran en el medio, así que no se construye una segunda lista. Cada valor se intercambia como máximo una vez. El tiempo es O(n) y el espacio es O(1).
def reverse_blocks(nums, k):
for start in range(0, len(nums) - k + 1, k): # full blocks only
lo, hi = start, start + k - 1
while lo < hi: # swap the ends, walk inward
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
return nums
print(reverse_blocks([1, 2, 3, 4, 5, 6, 7, 8], 3)) # -> [3, 2, 1, 6, 5, 4, 7, 8]
print(reverse_blocks([1, 2, 3, 4], 4)) # -> [4, 3, 2, 1]
print(reverse_blocks([5, 6], 3)) # -> [5, 6]¿Lo que te frena es la idea y no el código? Inversión in-place lo explica.