Reverse Nodes in k-Group

Q: ما التعقيد الزمني وتعقيد المساحة لعكس العقد في مجموعات حجمها k؟

يعمل في زمن O(L) لقائمة تتكون من L عقد: تُحصى كل عقدة مرة واحدة وتُعكس مرة واحدة. يستخدم الإصدار الذي يعمل في المكان ذاكرة إضافية مقدارها O(1)؛ أما نسخ القيم إلى مصفوفة فيستخدم O(L).

Q: ماذا يحدث للمجموعة الأخيرة إذا كان عدد العُقَد فيها أقل من k؟

يحتفظ بترتيبه الأصلي. عُدّ العقد k قبل عكس كل مجموعة؛ وإذا وصلت إلى نهاية القائمة أولًا، فاترك الباقي كما هو.

صعبالقائمة المترابطة

+10

تُخزَّن قائمة مترابطة أحادية في مصفوفتين بالطول نفسه. تحتوي العقدة i على values[i] وترتبط بالعقدة next[i]؛ وتشير -1 إلى نهاية القائمة، والعقدة 0 هي الرأس. قد تُخزَّن العقد بأي ترتيب، لذا اتبع الروابط، لا ترتيب المصفوفة.

اعكس القائمة ضمن مجموعات من k عقد: تُعكس أول k عقد، ثم تُعكس المجموعة التالية المكوّنة من k عقد، وهكذا. تحتفظ المجموعة الأخيرة التي تضم أقل من k عقد بترتيبها. أعد القيم بترتيب القائمة الجديد.

الدالة

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

nextinteger-array: فهرس العقدة التي ترتبط بها كل عقدة، أو ‎-1‎ للعقدة الأخيرة
valuesinteger-array: القيمة التي تحتفظ بها كل عقدة
kinteger: عدد العُقد في كل مجموعة لعكسها
تُرجعinteger-array: القيم بترتيب القائمة الجديدة

القيود

1 ≤ L ≤ 5000، حيث L هو طول next وvalues.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
كل قيمة next[i] هي -1 أو فهرس عقدة من 0 إلى L-1.
بدءًا من العقدة 0، تزور القائمة كل عقدة مرة واحدة بالضبط، ثم تصل إلى -1. لا توجد دورة.

أمثلة

المدخلات: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
المخرجات: [2, 1, 4, 3, 5]
الشرح: تُقرأ القائمة كالتالي: 1, 2, 3, 4, 5 (العُقد 0, 2, 4, 1, 3). الزوجان 1, 2 و3, 4 معكوسان، أما 5 وحده فأقصر من k = 2، لذا يبقى في النهاية.

المدخلات: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
المخرجات: [30, 20, 10, 60, 50, 40, 70, 80]
الشرح: تُقرأ القائمة 10, 20, ..., 80. تم عكس ترتيب المجموعتين 10, 20, 30 و40, 50, 60. المجموعة 70, 80 أقصر من k = 3، لذا تحتفظ بترتيبها.

المدخلات: next = [2, -1, 1]values = [7, 9, 3]k = 3
المخرجات: [9, 3, 7]
الشرح: تُقرأ المصفوفة 7, 9, 3، لكن القائمة تُقرأ 7, 3, 9. عندما تكون k مساوية للطول، تكون القائمة كلها مجموعة واحدة وتخرج معكوسة: 9, 3, 7.

سؤال إضافي

هل يمكنك كتابتها بصورة递递ية، بعكس مجموعة واحدة والاستدعاء递递ي على بقية القائمة؟ ما مقدار الذاكرة الإضافية التي تستخدمها؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

عكس قائمة كاملة هو تمريرة واحدة لقلب الروابط. هنا، تتوقف عمليات القلب كل k عقدة، ويجب وصل كل مجموعة معكوسة بالجزء الذي يسبقها والعقد التي تليها. يمكنك نسخ القيم إلى مصفوفة وعكس الكتل، أو إعادة ربط كل مجموعة في مكانها باستخدام ذاكرة إضافية بحجم O(1).

انسخ القيم واعكس ترتيب كل كتلة

الفكرة

ابدأ من العقدة 0 باستخدام node = next[node] وانسخ القيم إلى مصفوفة بترتيب القائمة. أصبحت المجموعات الآن كتلًا من الفهارس: 0 إلى k-1، وk إلى 2k-1، وهكذا: اعكس كل كتلة كاملة، واترك الكتلة الأخيرة الأقصر كما هي. يستغرق هذا وقتًا قدره O(L) وذاكرة إضافية قدرها O(L)، ولا يلمس أي رابط.

الخوارزمية

انتقِل من العقدة 0 حتى -1 وأضِف values[node] إلى مصفوفة.
لكل start = 0, k, 2k, ... طالما أن start + k ≤ L: اعكس الكتلة من الفهرس start إلى start+k-1.
اترك الكتلة الأقصر في النهاية كما هي.
أعِد المصفوفة.

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

اعكس كل مجموعة في موضعها بإعادة ربط العقد

الفكرة

لعكس قائمة كاملة، مرّر عليها باستخدام prev وnode وعيّن next[node] = prev. المجموعة هي الحلقة نفسها عند تشغيلها k مرات، مع بدء prev من after، وهي العقدة التي تأتي مباشرة بعد المجموعة. تصبح العقدة الأولى في المجموعة هي الأخيرة، وترتبط بـafter، وبذلك يبقى باقي القائمة متصلًا.

عُدّ k عقد قبل قلبها: إذا وصلت إلى -1 أولًا، فالمتبقي مجموعة قصيرة وتظل كما هي. بعد القلب، يصبح prev العقدة الأولى الجديدة للمجموعة. اربط آخر عقدة في المجموعة السابقة بها، أو اجعلها الرأس إذا كانت هذه أول مجموعة. تصبح العقدة الأولى القديمة للمجموعة الآن آخر عقدة في الجزء الذي اكتمل.

تُزار كل عقدة مرتين، مرة للعد ومرة للقلب: زمن O(L) وبضعة أعداد صحيحة من الذاكرة (O(L) في R، إذ ينسخ متجه الروابط عند أول تغيير فيه).

الخوارزمية

ابدأ بـ head = 0، وprevTail = -1، وgroupStart = 0.
انتقل k خطوات من groupStart إلى after؛ إذا وصلت إلى -1 أولًا، فانتقل إلى الخطوة 5.
مع prev = after وnode = groupStart، كرر k مرات: احفظ next[node]، واضبط next[node] = prev، ثم حرّك كليهما إلى الأمام.
إذا كانت قيمة prevTail هي -1، فاضبط head = prev؛ وإلا فاضبط next[prevTail] = prev. اضبط prevTail = groupStart وgroupStart = after؛ ثم انتقل إلى الخطوة 2.
اجمع القيم بدءًا من 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

أخطاء شائعة وحالات حدّية

عكس المجموعة الأخيرة القصيرة. عُدّ العقد k قبل العكس؛ فلا يمكن التراجع عن وصلة معكوسة دون تمريرة أخرى.
بدء العكس بـ prev = -1، كما في العكس الكامل. عندها ينفصل الذيل القصير: يعيد المثال الأول 2, 1, 4, 3.
عدم وصل العقدة الأخيرة من المجموعة السابقة بالعقدة الأولى الجديدة. فهي ما زالت تشير إلى العقدة الأولى القديمة، لذا تختفي k-1 عقد.
قراءة الإجابة من العقدة 0، أو قراءة values من اليسار إلى اليمين. بعد عكس مجموعة من k ≥ 2 عقد، لا تعود العقدة 0 هي الرأس، كما أن ترتيب المصفوفة لم يكن ترتيب القائمة قط.
استخدام الفهرسة بدءًا من 0 في Lua وR، إذ تبدأ مصفوفاتهما من 1. أبقِ فهارس العقد بدءًا من 0، واقرأ next[node + 1].

أسئلة شائعة3

ما التعقيد الزمني وتعقيد المساحة لعكس العقد في مجموعات حجمها k؟

يعمل في زمن O(L) لقائمة تتكون من L عقد: تُحصى كل عقدة مرة واحدة وتُعكس مرة واحدة. يستخدم الإصدار الذي يعمل في المكان ذاكرة إضافية مقدارها O(1)؛ أما نسخ القيم إلى مصفوفة فيستخدم O(L).

ماذا يحدث للمجموعة الأخيرة إذا كان عدد العُقَد فيها أقل من k؟

يحتفظ بترتيبه الأصلي. عُدّ العقد k قبل عكس كل مجموعة؛ وإذا وصلت إلى نهاية القائمة أولًا، فاترك الباقي كما هو.

لماذا تستخدم حلول هذه المسألة عقدةً وهمية؟

مع كائنات العقد، تمنح العقدة الوهمية قبل الرأس المجموعة الأولى عقدةً أمامها، بحيث يربط سطر واحد كل مجموعة بالجزء المكتمل. ومع مصفوفة من الروابط، يؤدي prevTail الذي يظل -1 حتى اكتمال المجموعة الأولى المهمة نفسها.

def reverseKGroup(next, values, k):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

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

الإخراج المتوقع

[2, 1, 4, 3, 5]