Reverse Nodes in k-Group

Q: Apa yang terjadi pada grup terakhir jika jumlah node-nya kurang dari k?

Urutannya tetap seperti semula. Hitung node k sebelum membalik setiap kelompok. Jika kamu mencapai akhir list terlebih dahulu, biarkan sisanya seperti semula.

SulitLinked list

+10

Linked list satu arah disimpan dalam dua array dengan panjang yang sama. Node i menyimpan values[i] dan terhubung ke node next[i]; -1 menandai akhir list, dan head adalah node 0. Node dapat disimpan dalam urutan apa pun, jadi ikuti tautannya, bukan urutan array.

Balik urutan list dalam kelompok yang masing-masing terdiri dari k node: k node pertama menjadi terbalik, lalu k node berikutnya, dan seterusnya. Kelompok terakhir yang berisi kurang dari k node tetap mempertahankan urutannya. Kembalikan nilai-nilainya dalam urutan list yang baru.

Fungsi

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

nextinteger-array: indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir
valuesinteger-array: nilai yang disimpan oleh setiap node
kinteger: jumlah node yang perlu dibalik di setiap grup
Mengembalikaninteger-array: nilai-nilai dalam urutan daftar baru

Batasan

1 ≤ L ≤ 5000, dengan L adalah panjang next dan values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Setiap next[i] bernilai -1 atau indeks node dari 0 hingga L-1.
Dimulai dari simpul 0, list mengunjungi setiap simpul tepat satu kali lalu mencapai -1. Tidak ada siklus.

Contoh

Input: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Output: [2, 1, 4, 3, 5]
Penjelasan: list tersebut terbaca sebagai 1, 2, 3, 4, 5 (node 0, 2, 4, 1, 3). Pasangan 1, 2 dan 3, 4 dibalik, dan 5 sendiri lebih pendek daripada k = 2, jadi tetap di urutan terakhir.

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]
Penjelasan: list tersebut berbunyi 10, 20, ..., 80. Grup 10, 20, 30 dan 40, 50, 60 dibalik. 70, 80 lebih pendek dari k = 3, jadi urutannya tetap.

Input: next = [2, -1, 1]values = [7, 9, 3]k = 3
Output: [9, 3, 7]
Penjelasan: array berisi 7, 9, 3, tetapi list berisi 7, 3, 9. Dengan k sama dengan panjangnya, seluruh list menjadi satu kelompok dan hasilnya terbalik: 9, 3, 7.

Pertanyaan lanjutan

Bisakah kamu menulisnya secara rekursif, dengan membalik satu kelompok dan melakukan rekursi pada sisa list? Berapa banyak memori tambahan yang digunakan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Membalik seluruh list memerlukan satu kali lintasan untuk membalik tautan. Di sini, pembalikan berhenti setiap k node, dan setiap grup yang dibalik harus disambungkan ke bagian sebelumnya dan node-node setelahnya. Kamu bisa menyalin nilainya ke dalam array lalu membalik blok, atau menyambungkan ulang setiap grup langsung di tempat dengan memori tambahan O(1).

Salin nilainya dan balik urutan setiap blok

Intuisi

Telusuri dari node 0 dengan node = next[node] dan salin nilainya ke dalam array sesuai urutan list. Kelompoknya kini berupa blok indeks 0 sampai k-1, k sampai 2k-1, dan seterusnya: balik setiap blok yang ukurannya pas dan biarkan blok terakhir yang lebih pendek tetap seperti semula. Proses ini memerlukan waktu O(L) dan memori tambahan O(L), serta tidak pernah menyentuh link.

Algoritma

Telusuri dari node 0 hingga -1 dan tambahkan values[node] ke array.
Untuk start = 0, k, 2k, ... selama start + k ≤ L: balik urutan blok dari indeks start hingga start+k-1.
Biarkan blok yang lebih pendek di akhir tetap seperti semula.
Kembalikan 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

Balikkan setiap grup di tempatnya dengan menghubungkan ulang

Intuisi

Untuk membalik seluruh list, telusuri list dengan prev dan node, lalu tetapkan next[node] = prev. Satu grup menggunakan perulangan yang sama sebanyak k kali, dengan prev dimulai dari after, simpul tepat setelah grup. Simpul pertama grup menjadi simpul terakhir dan terhubung ke after, sehingga bagian list lainnya tetap tersambung.

Hitung k simpul sebelum membaliknya: jika kamu mencapai -1 lebih dulu, sisanya adalah grup pendek dan dibiarkan. Setelah dibalik, prev menjadi simpul pertama yang baru dalam grup. Hubungkan simpul terakhir dari grup sebelumnya ke simpul itu, atau jadikan simpul itu sebagai head untuk grup pertama. Simpul pertama grup yang lama kini menjadi simpul terakhir dari bagian yang sudah selesai.

Setiap simpul dikunjungi dua kali, sekali untuk menghitung dan sekali untuk membalik: waktu O(L) dan penggunaan memori beberapa bilangan bulat (O(L) di R, yang menyalin vektor tautan saat pertama kali diubah).

Algoritma

Mulai dengan head = 0, prevTail = -1, groupStart = 0.
Telusuri k langkah dari groupStart ke after; jika kamu mencapai -1 terlebih dahulu, lanjutkan ke langkah 5.
Dengan prev = after dan node = groupStart, ulangi sebanyak k kali: simpan next[node], atur next[node] = prev, lalu majukan keduanya.
Jika prevTail adalah -1, atur head = prev; jika tidak, atur next[prevTail] = prev. Atur prevTail = groupStart, groupStart = after; lanjutkan ke langkah 2.
Kumpulkan nilai dari 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

Jebakan dan kasus tepi

Membalik kelompok terakhir yang pendek. Hitung k node sebelum membaliknya; tautan yang sudah dibalik tidak dapat dikembalikan tanpa proses lain.
Memulai pembalikan dengan prev = -1, seperti pada pembalikan penuh. Bagian akhir yang pendek akan terlepas: contoh pertama menghasilkan 2, 1, 4, 3.
Tidak menghubungkan node terakhir dari kelompok sebelumnya ke node pertama yang baru. Node itu masih menunjuk ke node pertama yang lama, sehingga k-1 node menghilang.
Membaca jawaban dari node 0, atau membaca values dari kiri ke kanan. Setelah kelompok berisi k ≥ 2 dibalik, node 0 bukan lagi head, dan urutan array tidak pernah sama dengan urutan list.
Menggunakan indeks mulai dari 0 di Lua dan R, yang array-nya dimulai dari 1. Pertahankan indeks node berbasis 0 dan baca next[node + 1].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dan ruang untuk membalik node dalam kelompok berukuran k?

Proses ini berjalan dalam waktu O(L) untuk list yang terdiri dari L node: setiap node dihitung satu kali dan dibalik satu kali. Versi in-place menggunakan memori tambahan O(1); menyalin nilainya ke dalam array menggunakan O(L).

Apa yang terjadi pada grup terakhir jika jumlah node-nya kurang dari k?

Urutannya tetap seperti semula. Hitung node k sebelum membalik setiap kelompok. Jika kamu mencapai akhir list terlebih dahulu, biarkan sisanya seperti semula.

Mengapa solusi untuk masalah ini menggunakan node dummy?

Dengan object node, node dummy sebelum head memberi grup pertama sebuah node di depannya, sehingga satu baris menghubungkan setiap grup ke bagian yang sudah selesai. Dengan array tautan, prevTail yang tetap bernilai -1 sampai grup pertama selesai melakukan hal yang sama.

def reverseKGroup(next, values, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[2, 1, 4, 3, 5]