Reverse Nodes in k-Group

Q: Qual é a complexidade de tempo e espaço para inverter nós em grupos de k?

Ele é executado em tempo O(L) para uma lista de L nós: cada nó é contado uma vez e invertido uma vez. A versão in-place usa O(1) de memória extra; copiar os valores para um array usa O(L).

Q: O que acontece com o último grupo se ele tiver menos de k nós?

Ele mantém a ordem original. Conte os nós k antes de inverter cada grupo; se você chegar primeiro ao fim da lista, deixe o restante como está.

DifícilLista ligada

+10

Uma lista simplesmente encadeada é armazenada em dois arrays de mesmo tamanho. O nó i contém values[i] e aponta para o nó next[i]; -1 encerra a lista, e a cabeça é o nó 0. Os nós podem ser armazenados em qualquer ordem, então siga os ponteiros, não a ordem dos arrays.

Inverta a lista em grupos de k nós: os primeiros k nós ficam invertidos, depois os próximos k, e assim por diante. Um último grupo com menos de k nós mantém sua ordem. Retorne os valores na nova ordem da lista.

Função

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: o índice do nó ao qual cada nó está ligado, ou -1 para o último nó
valuesinteger-array: o valor armazenado por cada nó
kinteger: o número de nós em cada grupo a inverter
Retornainteger-array: os valores na nova ordem da lista

Restrições

1 ≤ L ≤ 5000, onde L é o comprimento de next e de values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Cada next[i] é -1 ou um índice de nó de 0 a L-1.
Começando no nó 0, a lista visita cada nó exatamente uma vez e então chega a -1. Não há ciclo.

Exemplos

Entrada: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Saída: [2, 1, 4, 3, 5]
Explicação: A lista é lida como 1, 2, 3, 4, 5 (nós 0, 2, 4, 1, 3). Os pares 1, 2 e 3, 4 estão invertidos, e apenas 5 é menor que k = 2, então permanece no final.

Entrada: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Saída: [30, 20, 10, 60, 50, 40, 70, 80]
Explicação: A lista fica 10, 20, ..., 80. Os grupos 10, 20, 30 e 40, 50, 60 são invertidos. 70, 80 é menor que k = 3, então mantém sua ordem.

Entrada: next = [2, -1, 1]values = [7, 9, 3]k = 3
Saída: [9, 3, 7]
Explicação: O array lê 7, 9, 3, mas a lista lê 7, 3, 9. Com k igual ao comprimento, a lista inteira forma um grupo e sai invertida: 9, 3, 7.

Para ir além

Você consegue escrevê-lo recursivamente, invertendo um grupo e chamando a recursão para o restante da lista? Quanta memória extra isso usa?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Inverter uma lista inteira exige uma passagem de inversões de links. Aqui, as inversões param a cada k nós, e cada grupo invertido precisa ser conectado à parte anterior e aos nós seguintes. Você pode copiar os valores para um array e inverter os blocos, ou religar cada grupo no próprio lugar usando memória extra O(1).

Copie os valores e inverta cada bloco

Intuição

Percorra a partir do nó 0 com node = next[node] e copie os valores para um array na ordem da lista. Os grupos agora são os blocos de índices 0 a k-1, k a 2k-1 e assim por diante: inverta cada bloco completo e deixe o último bloco, se for mais curto, como está. Isso leva tempo O(L) e usa O(L) de memória extra, e nunca toca em um link.

Algoritmo

Percorra a partir do nó 0 até -1 e acrescente values[node] a um array.
Para start = 0, k, 2k, ... enquanto start + k ≤ L: inverta o bloco do índice start até start+k-1.
Deixe um bloco menor no final como está.
Retorne o array.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

Inverta cada grupo no próprio lugar religando os nós

Intuição

Para inverter uma lista inteira, percorra-a com prev e node e defina next[node] = prev. Um grupo usa o mesmo loop executado k vezes, com prev começando em after, o nó logo após o grupo. O primeiro nó do grupo passa a ser o último e aponta para after, mantendo o restante da lista conectado.

Conte k nós antes de inverter: se você chegar a -1 primeiro, o restante é um grupo curto e permanece como está. Após a inversão, prev é o novo primeiro nó do grupo. Conecte a ele o último nó do grupo anterior ou faça dele a cabeça no primeiro grupo. O primeiro nó original do grupo agora é o último nó da parte concluída.

Cada nó é visitado duas vezes, uma para contar e outra para inverter: tempo O(L) e alguns inteiros de memória (O(L) em R, que copia o vetor de links na primeira alteração).

Algoritmo

Comece com head = 0, prevTail = -1, groupStart = 0.
Percorra k passos de groupStart até after; se chegar primeiro a -1, vá para a etapa 5.
Com prev = after e node = groupStart, repita k vezes: salve next[node], defina next[node] = prev e avance ambos.
Se prevTail for -1, defina head = prev; caso contrário, defina next[prevTail] = prev. Defina prevTail = groupStart, groupStart = after; vá para a etapa 2.
Reúna os valores a partir de head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Armadilhas e casos extremos

Inverter o último grupo curto. Conte k nós antes de inverter; um elo invertido não pode ser desfeito sem outra passagem.
Começar a inversão com prev = -1, como em uma inversão completa. Uma cauda curta então se perde: o primeiro exemplo retorna 2, 1, 4, 3.
Não ligar o último nó do grupo anterior ao novo primeiro nó. Ele ainda aponta para o antigo primeiro nó, então k-1 nós desaparecem.
Ler a resposta a partir do nó 0 ou percorrer values da esquerda para a direita. Quando um grupo de k ≥ 2 é invertido, o nó 0 não é o início da lista, e a ordem do array nunca foi a ordem da lista.
Usar indexação a partir de 0 em Lua e R, cujos arrays começam em 1. Mantenha os índices dos nós baseados em 0 e leia next[node + 1].

Perguntas frequentes3

Qual é a complexidade de tempo e espaço para inverter nós em grupos de k?

Ele é executado em tempo O(L) para uma lista de L nós: cada nó é contado uma vez e invertido uma vez. A versão in-place usa O(1) de memória extra; copiar os valores para um array usa O(L).

O que acontece com o último grupo se ele tiver menos de k nós?

Ele mantém a ordem original. Conte os nós k antes de inverter cada grupo; se você chegar primeiro ao fim da lista, deixe o restante como está.

Por que as soluções para este problema usam um nó fictício?

Com objetos de nó, um nó fictício antes do início dá ao primeiro grupo um nó à sua frente, então uma única linha conecta cada grupo à parte concluída. Com um array de links, um prevTail que permanece -1 até que o primeiro grupo esteja concluído faz o mesmo trabalho.

def reverseKGroup(next, values, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Saída Esperada

[2, 1, 4, 3, 5]