Inverter cada bloco de k
A missão
Problema
Dada uma lista e um inteiro positivo k, inverta a ordem dos valores dentro de cada bloco consecutivo de k valores: os k primeiros, depois os k seguintes e assim por diante. Se o tamanho não for múltiplo de k, o último bloco é menor que k e fica como está. Trabalhe in-place, com espaço extra O(1), e retorne a mesma lista.
Exemplos
Input: nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 7, 8]
Por quê: dois blocos completos são invertidos; 7 e 8 formam um bloco curto
Input: nums = [1, 2, 3, 4], k = 4
Output: [4, 3, 2, 1]
Por quê: um bloco cobre a lista inteira
Input: nums = [5, 6], k = 3
Output: [5, 6]
Por quê: edge case: não existe nenhum bloco completo
Dicas
0 / 3
Divida mentalmente a lista em pedaços de k a partir do índice 0. Cada pedaço completo é uma pequena inversão própria, independente das outras.
Uma inversão in-place só precisa de dois índices que trocam valores e se aproximam um do outro. A pergunta que resta é onde cada pedaço começa e termina.
Percorra os inícios de bloco 0, k, 2k e assim por diante, parando antes de um início cujo bloco passaria do fim. Em cada bloco, troque os valores das duas pontas e mova os dois índices para dentro até eles se encontrarem.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- k is a positive integer
- a final block shorter than k stays as it is
- in place with O(1) extra space
Solução
Os blocos começam em 0, k, 2k e assim por diante, e um bloco só é invertido quando todos os seus k valores existem, o que o limite do range, len(nums) - k + 1, garante. Cada bloco é invertido por dois índices que trocam valores e se encontram no meio, então nenhuma segunda lista é criada. Cada valor é trocado no máximo uma vez. O tempo é O(n) e o espaço é 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]Travou na ideia, e não no código? Inversão in-place explica isso.