Reverse Nodes in k-Group
Danh sách liên kết đơn (singly linked list) được lưu trong hai mảng có cùng độ dài. Nút i chứa values[i] và liên kết đến nút next[i]; -1 đánh dấu điểm kết thúc danh sách, còn nút đầu là nút 0. Các nút có thể được lưu theo bất kỳ thứ tự nào, vì vậy hãy lần theo các liên kết, không phải thứ tự trong mảng.
Đảo ngược danh sách theo từng nhóm gồm k nút: k nút đầu tiên sẽ được đảo ngược, tiếp theo là nhóm k nút kế tiếp, cứ thế tiếp tục. Nhóm cuối cùng có ít hơn k nút sẽ giữ nguyên thứ tự. Trả về các giá trị theo thứ tự mới của danh sách.
Hàm
- nextinteger-array
- chỉ số của nút mà mỗi nút liên kết đến, hoặc -1 nếu là nút cuối cùng
- valuesinteger-array
- giá trị mà mỗi nút lưu giữ
- kinteger
- số nút trong mỗi nhóm cần đảo ngược
- Trả vềinteger-array
- các giá trị theo thứ tự trong danh sách mới
Ràng buộc
1 ≤ L ≤ 5000, trong đóLlà độ dài củanextvàvalues.-1000 ≤ values[i] ≤ 10001 ≤ k ≤ L- Mỗi
next[i]là-1hoặc chỉ số nút từ0đếnL-1. - Bắt đầu từ nút
0, danh sách đi qua mỗi nút đúng một lần rồi đến-1. Không có chu trình.
Ví dụ
- Đầu vào
- next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
- Đầu ra
- [2, 1, 4, 3, 5]
- Giải thích
- Danh sách có các giá trị
1, 2, 3, 4, 5(các nút0, 2, 4, 1, 3). Các cặp1, 2và3, 4bị đảo ngược, còn5đứng riêng lẻ, ngắn hơnk = 2, nên vẫn ở cuối.
- Đầu vào
- next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
- Đầu ra
- [30, 20, 10, 60, 50, 40, 70, 80]
- Giải thích
- Danh sách có các giá trị
10, 20, ..., 80. Các nhóm10, 20, 30và40, 50, 60được đảo ngược.70, 80ngắn hơnk = 3, nên vẫn giữ nguyên thứ tự.
- Đầu vào
- next = [2, -1, 1]values = [7, 9, 3]k = 3
- Đầu ra
- [9, 3, 7]
- Giải thích
- Mảng đọc là
7, 9, 3, nhưng danh sách đọc là7, 3, 9. Khikbằng độ dài, toàn bộ danh sách là một nhóm và được đảo ngược:9, 3, 7.
Câu hỏi mở rộng
Bạn có thể viết hàm này bằng đệ quy, đảo ngược một nhóm rồi gọi đệ quy với phần còn lại của danh sách không? Cách này dùng thêm bao nhiêu bộ nhớ?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Đảo ngược cả danh sách cần duyệt qua bằng hai con trỏ, nút trước đó và nút hiện tại, rồi đảo từng liên kết khi bạn đi qua. Điều gì sẽ thay đổi nếu phải dừng sau
knút và phần còn lại của danh sách vẫn phải được nối liền?Trước khi đảo ngược một nhóm, hãy đi trước
kbước để kiểm tra xem có đủknút hay không; nếu không, hãy giữ nguyên phần còn lại. Nút bạn đến nằm ngay sau nhóm, và nút đầu tiên của nhóm phải liên kết đến nút đó.Giữ lại nút cuối cùng của phần đã hoàn thành. Sau khi đảo ngược một nhóm, trỏ nút đó đến nút đầu tiên mới của nhóm. Với nhóm đầu tiên, nút đó chính là nút đầu mới. Nút đầu tiên cũ của nhóm giờ là nút cuối của phần đã hoàn thành.
Lời giải
Đảo ngược toàn bộ danh sách là một lượt lật các liên kết. Ở đây, cứ mỗi k nút thì dừng lật, rồi nối từng nhóm đã đảo ngược với phần phía trước và các nút phía sau. Bạn có thể sao chép các giá trị vào một mảng rồi đảo ngược từng khối, hoặc nối lại các nhóm ngay tại chỗ bằng bộ nhớ phụ O(1).
Sao chép các giá trị và đảo ngược từng khối
Ý tưởng
Bắt đầu đi từ nút 0 với node = next[node] và sao chép các giá trị vào một mảng theo thứ tự trong danh sách. Lúc này, các nhóm là những khối chỉ số 0 đến k-1, k đến 2k-1 và cứ thế tiếp tục: đảo ngược từng khối đầy đủ, để nguyên khối cuối ngắn hơn. Việc này mất O(L) thời gian và O(L) bộ nhớ bổ sung, đồng thời không hề thay đổi liên kết nào.
Thuật toán
- Đi từ nút
0đến-1và thêmvalues[node]vào một mảng. - Với
start = 0, k, 2k, ...khistart + k ≤ L: đảo ngược khối từ chỉ sốstartđếnstart+k-1. - Giữ nguyên khối ngắn hơn ở cuối.
- Trả về mảng.
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Đảo ngược từng nhóm ngay tại chỗ bằng cách liên kết lại
Ý tưởng
Để đảo ngược toàn bộ danh sách, bạn duyệt qua danh sách bằng prev và node, rồi gán next[node] = prev. Một nhóm cũng dùng vòng lặp đó, chạy k lần, với prev bắt đầu từ after, nút ngay sau nhóm. Nút đầu tiên của nhóm trở thành nút cuối cùng và liên kết với after, nhờ đó phần còn lại của danh sách vẫn được nối liền.
Đếm k nút trước khi đảo: nếu bạn gặp -1 trước, phần còn lại là một nhóm ngắn và được giữ nguyên. Sau khi đảo, prev là nút đầu tiên mới của nhóm. Nối nút cuối cùng của nhóm trước đó với nút này, hoặc đặt nút này làm nút đầu nếu đây là nhóm đầu tiên. Nút đầu tiên cũ của nhóm giờ là nút cuối cùng của phần đã hoàn tất.
Mỗi nút được duyệt hai lần, một lần để đếm và một lần để đảo: thời gian O(L) và cần một ít bộ nhớ cho số nguyên (O(L) trong R, vì R sao chép vector liên kết khi có thay đổi đầu tiên).
Thuật toán
- Bắt đầu với
head = 0,prevTail = -1,groupStart = 0. - Đi
kbước từgroupStartđếnafter; nếu gặp-1trước, chuyển đến bước 5. - Với
prev = aftervànode = groupStart, lặp lạiklần: lưunext[node], đặtnext[node] = prev, rồi tiến cả hai. - Nếu
prevTaillà-1, đặthead = prev; nếu không, đặtnext[prevTail] = prev. ĐặtprevTail = groupStart,groupStart = after; chuyển đến bước 2. - Thu thập các giá trị bắt đầu từ
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
Lỗi thường gặp và trường hợp biên
- Đảo ngược nhóm cuối cùng ngắn hơn. Đếm
knút trước khi đảo, vì không thể khôi phục liên kết đã đảo nếu không duyệt lại. - Bắt đầu đảo với
prev = -1, như khi đảo ngược toàn bộ. Phần đuôi ngắn sẽ bị mất: ví dụ đầu tiên trả về2, 1, 4, 3. - Không nối nút cuối của nhóm trước với nút đầu mới. Nút đó vẫn trỏ đến nút đầu cũ, nên
k-1nút biến mất. - Đọc kết quả từ nút
0, hoặc đọcvaluestừ trái sang phải. Khi một nhóm cók ≥ 2nút bị đảo, nút0không còn là nút đầu, và thứ tự mảng vốn không phải là thứ tự danh sách. - Dùng chỉ số bắt đầu từ 0 trong Lua và R, vì mảng của chúng bắt đầu từ 1. Giữ chỉ số nút theo hệ 0 và đọc
next[node + 1].
Câu hỏi thường gặp3
Độ phức tạp về thời gian và không gian của việc đảo ngược các nút theo nhóm k là gì?
Thuật toán chạy trong thời gian O(L) với danh sách gồm L nút: mỗi nút được đếm một lần và đảo ngược một lần. Phiên bản tại chỗ dùng O(1) bộ nhớ bổ sung; sao chép các giá trị vào một mảng sẽ dùng O(L).
Điều gì xảy ra với nhóm cuối cùng nếu nhóm đó có ít hơn k nút?
Nó giữ nguyên thứ tự ban đầu. Hãy đếm k nút trước khi đảo ngược từng nhóm; nếu bạn đến cuối danh sách trước, hãy giữ nguyên phần còn lại.
Tại sao lời giải cho bài toán này lại dùng một nút giả?
Với các đối tượng nút, một nút giả đứng trước nút đầu tạo ra một nút phía trước nhóm đầu tiên, nhờ đó một dòng liên kết mọi nhóm với phần đã hoàn thành. Với một mảng các liên kết, prevTail giữ nguyên giá trị -1 cho đến khi nhóm đầu tiên hoàn tất và cũng thực hiện chức năng tương tự.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def reverseKGroup(next, values, k):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
next = [2, 3, 4, -1, 1] values = [1, 4, 2, 5, 3] k = 2
Đầu ra mong đợi
[2, 1, 4, 3, 5]