Reverse Nodes in k-Group

Q: Qual è la complessità temporale e spaziale dell’inversione dei nodi in gruppi di k?

Richiede un tempo O(L) per una lista di L nodi: ogni nodo viene contato una volta e invertito una volta. La versione in loco usa O(1) di memoria aggiuntiva; copiare i valori in un array usa O(L).

Q: Che cosa succede all'ultimo gruppo se contiene meno di k nodi?

Mantiene l’ordine originale. Conta i nodi k prima di invertire ciascun gruppo; se raggiungi prima la fine della lista, lascia il resto così com’è.

DifficileLista concatenata

+10

Una lista concatenata semplice è memorizzata in due array della stessa lunghezza. Il nodo i contiene values[i] e punta al nodo next[i]; -1 termina la lista e la testa è il nodo 0. I nodi possono essere memorizzati in qualsiasi ordine, quindi segui i collegamenti, non l’ordine degli array.

Inverti la lista in gruppi di k nodi: i primi k nodi vengono invertiti, poi i successivi k e così via. L’ultimo gruppo, se contiene meno di k nodi, mantiene il proprio ordine. Restituisci i valori nel nuovo ordine della lista.

Funzione

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

nextinteger-array: l'indice del nodo a cui è collegato ciascun nodo, oppure -1 per l'ultimo nodo
valuesinteger-array: il valore contenuto in ciascun nodo
kinteger: il numero di nodi in ciascun gruppo da invertire
Restituisceinteger-array: i valori nel nuovo ordine dell’elenco

Vincoli

1 ≤ L ≤ 5000, dove L è la lunghezza di next e di values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Ogni next[i] è -1 oppure un indice di nodo da 0 a L-1.
Partendo dal nodo 0, la lista visita ogni nodo esattamente una volta e poi raggiunge -1. Non c'è alcun ciclo.

Esempi

Input: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Output: [2, 1, 4, 3, 5]
Spiegazione: La lista legge 1, 2, 3, 4, 5 (nodi 0, 2, 4, 1, 3). Le coppie 1, 2 e 3, 4 sono invertite, e 5 da solo è più corto di k = 2, quindi rimane in fondo.

Input: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Output: [30, 20, 10, 60, 50, 40, 70, 80]
Spiegazione: La lista contiene 10, 20, ..., 80. I gruppi 10, 20, 30 e 40, 50, 60 sono invertiti. 70, 80 è più corto di k = 3, quindi mantiene il suo ordine.

Input: next = [2, -1, 1]values = [7, 9, 3]k = 3
Output: [9, 3, 7]
Spiegazione: L'array contiene 7, 9, 3, ma la lista contiene 7, 3, 9. Con k uguale alla lunghezza, l'intera lista è un gruppo e risulta invertita: 9, 3, 7.

Per approfondire

Riesci a scriverlo in modo ricorsivo, invertendo un gruppo e applicando la ricorsione al resto della lista? Quanta memoria aggiuntiva usa?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Invertire un'intera lista richiede un solo passaggio di inversioni dei collegamenti. Qui le inversioni si fermano ogni k nodi e ogni gruppo invertito deve essere collegato alla parte che lo precede e ai nodi che lo seguono. Puoi copiare i valori in un array e invertire i blocchi, oppure ricollegare ogni gruppo sul posto usando O(1) memoria aggiuntiva.

Copia i valori e inverti ogni blocco

Intuizione

Percorri la lista a partire dal nodo 0 con node = next[node] e copia i valori in un array nell’ordine della lista. I gruppi sono ora i blocchi di indici da 0 a k-1, da k a 2k-1 e così via: inverti ogni blocco completo e lascia invariato l’ultimo blocco, se è più corto. Questo richiede tempo O(L) e memoria aggiuntiva O(L), e non tocca mai un collegamento.

Algoritmo

Procedi dal nodo 0 fino a -1 e aggiungi values[node] a un array.
Per start = 0, k, 2k, ... finché start + k ≤ L: inverti il blocco dall’indice start a start+k-1.
Lascia invariato l’ultimo blocco, se è più corto.
Restituisci l’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

Inverti ciascun gruppo sul posto ricollegando

Intuizione

Per invertire un’intera lista, la percorri con prev e node e imposti next[node] = prev. Un gruppo è lo stesso ciclo eseguito k volte, con prev che inizia da after, il nodo subito dopo il gruppo. Il primo nodo del gruppo diventa l’ultimo e punta a after, così il resto della lista rimane collegato.

Conta k nodi prima di invertirli: se raggiungi prima -1, il resto è un gruppo più corto e rimane invariato. Dopo l’inversione, prev è il nuovo primo nodo del gruppo. Collega a esso l’ultimo nodo del gruppo precedente oppure, se è il primo gruppo, rendilo la testa. Il vecchio primo nodo del gruppo è ora l’ultimo nodo della parte completata.

Ogni nodo viene visitato due volte, una per contare e una per invertire: tempo O(L) e pochi interi di memoria (O(L) in R, che copia il vettore dei collegamenti alla prima modifica).

Algoritmo

Inizia con head = 0, prevTail = -1, groupStart = 0.
Percorri k passi da groupStart a after; se raggiungi prima -1, vai al passaggio 5.
Con prev = after e node = groupStart, ripeti k volte: salva next[node], imposta next[node] = prev, fai avanzare entrambi.
Se prevTail è -1, imposta head = prev; altrimenti imposta next[prevTail] = prev. Imposta prevTail = groupStart, groupStart = after; vai al passaggio 2.
Raccogli i valori a partire da 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

Trappole e casi limite

Invertire l'ultimo gruppo più corto. Conta k nodi prima di invertire; un collegamento invertito non può essere ripristinato senza un altro passaggio.
Iniziare l'inversione con prev = -1, come in un'inversione completa. Una coda corta quindi si stacca: il primo esempio restituisce 2, 1, 4, 3.
Non collegare l'ultimo nodo del gruppo precedente al nuovo primo nodo. Continua a puntare al vecchio primo nodo, quindi k-1 nodi scompaiono.
Leggere la risposta dal nodo 0 o leggere values da sinistra a destra. Una volta invertito un gruppo di k ≥ 2, il nodo 0 non è la testa e l'ordine dell'array non è mai stato l'ordine della lista.
Usare indici a partire da 0 in Lua e R, i cui array iniziano da 1. Mantieni gli indici dei nodi a base 0 e leggi next[node + 1].

Domande frequenti3

Qual è la complessità temporale e spaziale dell’inversione dei nodi in gruppi di k?

Richiede un tempo O(L) per una lista di L nodi: ogni nodo viene contato una volta e invertito una volta. La versione in loco usa O(1) di memoria aggiuntiva; copiare i valori in un array usa O(L).

Che cosa succede all'ultimo gruppo se contiene meno di k nodi?

Mantiene l’ordine originale. Conta i nodi k prima di invertire ciascun gruppo; se raggiungi prima la fine della lista, lascia il resto così com’è.

Perché le soluzioni a questo problema usano un nodo fittizio?

Con gli oggetti nodo, un nodo fittizio prima della testa dà al primo gruppo un nodo davanti, così una sola riga collega ogni gruppo alla parte completata. Con un array di collegamenti, un prevTail che rimane -1 finché il primo gruppo non è completo svolge lo stesso compito.

def reverseKGroup(next, values, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

[2, 1, 4, 3, 5]