Reverse Nodes in k-Group

Q: k'lı gruplar halinde düğümleri tersine çevirmenin zaman ve uzay karmaşıklığı nedir?

L düğümden oluşan bir liste için O(L) zamanda çalışır: her düğüm bir kez sayılır ve bir kez ters çevrilir. Yerinde çalışan sürüm O(1) ek bellek kullanır; değerleri bir diziye kopyalamak O(L) bellek kullanır.

Q: Son grupta k düğümden daha az düğüm varsa ne olur?

Orijinal sırasını korur. Her grubu ters çevirmeden önce k düğüm say; listenin sonuna önce ulaşırsan geri kalanını olduğu gibi bırak.

ZorBağlı liste

+10

Tek yönlü bağlı liste, aynı uzunluktaki iki dizide saklanır. i düğümü values[i] değerini taşır ve next[i] düğümüne bağlanır; -1 listenin sonunu belirtir ve baş düğüm 0'dır. Düğümler herhangi bir sırada saklanabilir; bu yüzden dizi sırasını değil, bağlantıları takip et.

Listeyi k düğümlük gruplar hâlinde tersine çevir: ilk k düğüm ters sırada gelir, ardından sonraki k düğüm gelir ve bu şekilde devam eder. k düğümden az düğüm içeren son grup sırasını korur. Değerleri yeni liste sırasına göre döndür.

Fonksiyon

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

nextinteger-array: her düğümün bağlantı verdiği düğümün indeksi veya son düğüm için -1
valuesinteger-array: her düğümün tuttuğu değer
kinteger: tersine çevrilecek her gruptaki düğüm sayısı
Döndürürinteger-array: yeni listedeki sıraya göre değerler

Kısıtlar

1 ≤ L ≤ 5000; burada L, next ve values uzunluğudur.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Her next[i], -1 ya da 0 ile L-1 arasında bir düğüm indeksidir.
0 düğümünden başlayarak liste her düğümü tam olarak bir kez ziyaret eder ve ardından -1 düğümüne ulaşır. Döngü yoktur.

Örnekler

Girdi: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Çıktı: [2, 1, 4, 3, 5]
Açıklama: Liste 1, 2, 3, 4, 5 şeklindedir (düğümler 0, 2, 4, 1, 3). 1, 2 ve 3, 4 çiftleri ters çevrilir ve yalnızca 5, k = 2 değerinden daha kısa olduğundan sonda kalır.

Girdi: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Çıktı: [30, 20, 10, 60, 50, 40, 70, 80]
Açıklama: Liste 10, 20, ..., 80 şeklinde okunur. 10, 20, 30 ve 40, 50, 60 gruplarının sırası ters çevrilir. 70, 80, k = 3 değerinden daha kısa olduğu için sırasını korur.

Girdi: next = [2, -1, 1]values = [7, 9, 3]k = 3
Çıktı: [9, 3, 7]
Açıklama: Dizi 7, 9, 3 sırasını izler, ancak liste 7, 3, 9 sırasını izler. k uzunluğa eşit olduğunda, listenin tamamı tek bir grup olur ve ters çevrilmiş olarak çıkar: 9, 3, 7.

Ek soru

Bunu, bir grubu tersine çevirip listenin geri kalanı üzerinde özyinelemeli çağrı yaparak yazabilir misin? Bu ne kadar ek bellek kullanır?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Tüm bir listeyi tersine çevirmek, bağlantıları bir kez çevirmekten ibarettir. Burada çevirmeler her k düğümde durur ve ters çevrilen her grup, öncesindeki parçaya ve sonrasındaki düğümlere bağlanmalıdır. Değerleri bir diziye kopyalayıp blokları tersine çevirebilir veya her grubu O(1) ek bellek kullanarak yerinde yeniden bağlayabilirsiniz.

Değerleri kopyalayın ve her bloğu tersine çevirin

Sezgi

node = next[node] ile 0 düğümünden başlayarak ilerleyin ve değerleri liste sırasıyla bir diziye kopyalayın. Gruplar artık 0 ile k-1, k ile 2k-1 arasındaki indeks blokları ve bu şekilde devam eder: tam olarak sığan her bloğu ters çevirin ve daha kısa olan son bloğu olduğu gibi bırakın. Bu işlem O(L) zaman ve O(L) ek bellek gerektirir ve hiçbir bağlantıya dokunmaz.

Algoritma

0 düğümünden başlayıp -1 değerine kadar ilerleyin ve values[node] değerini bir diziye ekleyin.
start = 0, k, 2k, ... için, start + k ≤ L olduğu sürece: start indeksinden start+k-1 indeksine kadar olan bloğu tersine çevirin.
Sondaki daha kısa bloğu olduğu gibi bırakın.
Diziyi döndürün.

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

Her grubu bağlantıları yeniden düzenleyerek yerinde tersine çevirin

Sezgi

Tüm bir listeyi tersine çevirmek için prev ve node ile üzerinden geçer ve next[node] = prev olarak ayarlarsın. Bir grup, prev grubun hemen sonrasındaki düğüm olan after ile başlayacak şekilde aynı döngünün k kez çalıştırılmasıdır. Grubun ilk düğümü son düğümü olur ve after düğümüne bağlanır; böylece listenin geri kalanı bağlı kalır.

Tersine çevirmeden önce k düğüm say: önce -1 değerine ulaşırsan, kalan kısım kısa bir gruptur ve olduğu gibi kalır. Tersine çevirme sonrasında prev, grubun yeni ilk düğümüdür. Önceki grubun son düğümünü ona bağla ya da ilk grupsa baş düğüm yap. Grubun eski ilk düğümü artık tamamlanan kısmın son düğümüdür.

Her düğüm iki kez ziyaret edilir: bir kez saymak, bir kez tersine çevirmek için. Zaman karmaşıklığı O(L), bellek kullanımı birkaç tamsayıdır (R'de O(L); çünkü R, bağlantı vektörünü ilk değişikliğinde kopyalar).

Algoritma

head = 0, prevTail = -1, groupStart = 0 ile başla.
groupStart noktasından after noktasına kadar k adım ilerle; önce -1 değerine ulaşırsan 5. adıma geç.
prev = after ve node = groupStart olacak şekilde, k kez tekrarla: next[node] değerini kaydet, next[node] = prev olarak ayarla ve ikisini de ilerlet.
prevTail değeri -1 ise head = prev olarak ayarla; değilse next[prevTail] = prev olarak ayarla. prevTail = groupStart, groupStart = after olarak ayarla; 2. adıma geç.
Değerleri head üzerinden topla.

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

Tuzaklar ve uç durumlar

Sondaki kısa grubu ters çevirmek. Çevirmeden önce k düğümü say; çevrilen bir bağlantı başka bir geçiş olmadan geri alınamaz.
Tam ters çevirmede olduğu gibi, çevirmeye prev = -1 ile başlamak. Kısa kuyruk o zaman kopar: ilk örnek 2, 1, 4, 3 sonucunu verir.
Önceki grubun son düğümünü yeni ilk düğüme bağlamamak. Hâlâ eski ilk düğümü gösterir, bu yüzden k-1 düğüm kaybolur.
Yanıtı 0 düğümünden okumak veya values değerlerini soldan sağa okumak. k ≥ 2 büyüklüğündeki bir grup ters çevrildiğinde 0 düğümü artık baş değildir ve dizi sırası hiçbir zaman liste sırası olmamıştır.
Dizileri 1'den başlayan Lua ve R'de 0'dan indekslemek. Düğüm indekslerini 0 tabanlı tut ve next[node + 1] değerini oku.

Sıkça sorulan sorular3

k'lı gruplar halinde düğümleri tersine çevirmenin zaman ve uzay karmaşıklığı nedir?

L düğümden oluşan bir liste için O(L) zamanda çalışır: her düğüm bir kez sayılır ve bir kez ters çevrilir. Yerinde çalışan sürüm O(1) ek bellek kullanır; değerleri bir diziye kopyalamak O(L) bellek kullanır.

Son grupta k düğümden daha az düğüm varsa ne olur?

Orijinal sırasını korur. Her grubu ters çevirmeden önce k düğüm say; listenin sonuna önce ulaşırsan geri kalanını olduğu gibi bırak.

Bu probleme yönelik çözümlerde neden kukla düğüm kullanılır?

Düğüm nesnelerinde, baş düğümden önceki bir kukla düğüm ilk grubun önüne bir düğüm koyar; böylece tek bir satır her grubu tamamlanmış kısma bağlar. Bağlantı dizisinde ise ilk grup tamamlanana kadar -1 değerinde kalan bir prevTail aynı işi görür.

def reverseKGroup(next, values, k):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

[2, 1, 4, 3, 5]