Spiral Matrix

Q: ما التعقيد الزمني وتعقيد المساحة لمصفوفة الحلزون؟

تقرأ كلتا الطريقتين كل قيمة مرة واحدة، لذا يكون الزمن O(m × n) ، ولا يمكن لأي حل أن يكون أفضل من ذلك لأن الإجابة تتضمن كل قيمة. يتطلب تقشير الطبقات باستخدام أربعة حدود ذاكرة إضافية O(1) ، بخلاف الذاكرة اللازمة للإجابة. أما السير مع الانعطاف عند وجود عائق، فيستخدم شبكة بحجم O(m × n) لتذكّر الخلايا التي قرأها.

متوسطرياضيات ومحاكاة المصفوفات والسلاسل النصية

+10

لديك مصفوفة من الأعداد الصحيحة تتكون من m صفوف وn أعمدة، معطاة على شكل قائمة من الصفوف. أعد جميع قيمها بترتيب حلزوني.

ابدأ من الزاوية العلوية اليسرى واتجه يمينًا على طول الصف العلوي، ثم إلى الأسفل على طول العمود الأيمن، ثم إلى اليسار على طول الصف السفلي، ثم إلى الأعلى على طول العمود الأيسر. واصل الدوران إلى الداخل باتجاه عقارب الساعة حتى تُقرأ كل قيمة مرة واحدة بالضبط.

الدالة

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: شبكة الأعداد الصحيحة، على هيئة قائمة من صفوف متساوية الطول
تُرجعinteger-array: كل قيمة في المصفوفة بترتيب حلزوني باتجاه عقارب الساعة، بدءًا من الزاوية العلوية اليسرى

القيود

1 ≤ m, n ≤ 80، حيث m = matrix.length وn = matrix[i].length
لكل صف الطول نفسه n.
-100 ≤ matrix[i][j] ≤ 100

أمثلة

المدخلات: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
المخرجات: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
الشرح: تزداد القيم على طول المسار الحلزوني. تُقرأ الحلقة الخارجية كالتالي: 1, 2, 3 على امتداد الجزء العلوي، و4, 5, 6 نزولًا على الجانب الأيمن، ثم 7, 8 عائدًا على امتداد الجزء السفلي، و9, 10 صعودًا على الجانب الأيسر. أما الطبقة الداخلية فهي عمود واحد، يُقرأ مرة واحدة من الأعلى إلى الأسفل: 11, 12.

المدخلات: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
المخرجات: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
الشرح: تعطي الحلقة الخارجية 7, 1, 5, 3، ثم 6, -1 نزولًا على الجانب الأيمن، و4, 0, 8 عودةً على طول الأسفل، و2 صعودًا على الجانب الأيسر. وما يتبقى هو الصف الوحيد 9, -4، يُقرأ مرة واحدة من اليسار إلى اليمين.

+15 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك إرجاع القيم بترتيب عكس اتجاه عقارب الساعة بدلًا من ذلك، بدءًا من الزاوية العلوية اليسرى والنزول أولًا عبر العمود الأيسر؟

تلميحات

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

فُتح 0 من 3

الحل

لا توجد هنا رياضيات ذكية؛ فالمشكلة تكمن في تتبّع العناصر، وهذا هو الموضع الذي تفشل فيه الحلول. يجب قراءة كل زاوية مرة واحدة، لا مرتين، وقد تكون الطبقة الأعمق صفًا واحدًا أو عمودًا واحدًا، حيث إن إكمال دورة كاملة سيعيد المرور على القيم نفسها. يمكنك التحرك كأنك روبوت يستدير يمينًا كلما واجه عائقًا، ويتذكر الخلايا التي قرأها. أو يمكنك تقشير المصفوفة حلقةً تلو الأخرى باستخدام أربعة حدود تتقلص، من دون الحاجة إلى ذاكرة إضافية.

تحرّك واستدر يمينًا عند وجود عائق

الفكرة

تخيّل متجوّلًا في الخلية العلوية اليسرى، متجهًا نحو اليمين. يقرأ الخلية التي يقف عليها، ثم يحاول التقدّم خطوة إلى الأمام. إذا كانت هذه الخطوة ستخرجه من المصفوفة أو ستوصله إلى خلية قرأها من قبل، يستدير إلى اليمين (يمينًا، ثم أسفل، ثم يسارًا، ثم أعلى، ثم يمينًا مجددًا) ويتقدّم في ذلك الاتجاه بدلًا من ذلك. ترسم هذه القاعدة الحلزون: إذ توقف حواف المصفوفة الدورة الأولى، وتعمل الخلايا التي قُرئت حتى الآن كجدران لكل دورة بعدها.

احتفظ بالاتجاه على هيئة فهرس d ضمن مصفوفتين صغيرتين، dr = [0, 1, 0, -1] وdc = [1, 0, -1, 0]، بحيث يكون الاستدارة يمينًا هي d = (d+1) % 4. واحتفظ بشبكة منطقية seen بحجم المصفوفة. في المثال الأول، يقرأ المتجوّل 1, 2, 3، ثم يواجه الحافة اليمنى فيستدير إلى الأسفل ليقرأ 4, 5, 6، ثم يستدير إلى اليسار ليقرأ 7, 8، وإلى الأعلى ليقرأ 9, 10. تقع 1 فوق 10، وقد قُرئت من قبل، لذا يستدير يمينًا نحو 11. وتقع 4 إلى يمين 11، وقد قُرئت، لذا يستدير إلى الأسفل نحو 12.

نفّذ الحلقة m × n مرة بالضبط، مرة واحدة لكل خلية، ولن تحتاج أبدًا إلى اكتشاف النهاية. بعد القراءة الأخيرة، قد يواجه المتجوّل جدارًا، لكنه لن يخطو مجددًا. تُقرأ كل خلية مرة واحدة، لذا يكون الزمن O(m × n). تتطلب شبكة seen ذاكرة إضافية بمقدار O(m × n)، وهي ما يزيله النهج التالي.

الخوارزمية

ابدأ عند الصف 0، والعمود 0، متجهًا إلى اليمين، مع شبكة seen تكون جميع قيمها false.
كرّر m × n مرة: أضف القيمة الحالية وعلّم خليتها بأنها تمت زيارتها.
احسب الخلية التالية في الاتجاه الحالي. إذا كانت خارج المصفوفة أو تمت زيارتها بالفعل، فاستدر يمينًا واحسبها مرة أخرى.
انتقل إلى تلك الخلية.
أعِد القيم بالترتيب الذي أضفتها به.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

قشّر الطبقات باستخدام أربعة حدود

الفكرة

الدوامة مجموعة من الحلقات المتداخلة. صِف الحلقة الحالية بأربعة حدود: الصفوف من top إلى bottom، والأعمدة من left إلى right. تقرأ دورة واحدة الصف العلوي من left إلى right، والعمود الأيمن من top+1 نزولًا إلى bottom، والصف السفلي من right-1 عودةً إلى left، والعمود الأيسر من bottom-1 صعودًا إلى top+1. يبدأ كل جانب بعد خلية واحدة من نهاية الجانب الذي يسبقه، لذا تُقرأ كل زاوية مرة واحدة بالضبط. بعد ذلك، حرّك الحدود الأربعة خطوة واحدة إلى الداخل وكرّر ما دام top ≤ bottom وleft ≤ right.

المأزق هو وجود حلقة لا يزيد سمكها على صف واحد أو عمود واحد، حيث يمر مسار العودة فوق خلايا سبق قراءتها. في المثال الثاني، بعد الحلقة الخارجية تصبح الحدود top = bottom = 1، وleft = 1 وright = 2: الصف الوحيد 9, -4. يقرأ الصف العلوي القيمتين، ولا يحتوي العمود الأيمن على شيء أسفل top. لكن الصف السفلي هو الصف نفسه، والمرور عليه عودةً سيضيف 9 مرة ثانية. لذا لا تمرّ على الصف السفلي والعمود الأيسر إلا عندما يكون top < bottom وleft < right. المثال الثالث هو الحالة المعكوسة: في العمود الوحيد 4, 1, 7، ستؤدي العودة صعودًا عبر العمود الأيسر إلى قراءة 1 مرة أخرى.

تُقرأ كل قيمة مرة واحدة، لذا يكون الزمن O(m × n)، وهو أقل زمن ممكن لأن الإجابة تحتوي على كل قيمة. وباستثناء مساحة الإجابة، تقتصر الذاكرة على أربعة أعداد صحيحة.

الخوارزمية

عيّن top = 0 وbottom = m-1 وleft = 0 وright = n-1.
ما دام top ≤ bottom وleft ≤ right، اقرأ الصف العلوي من left إلى right والعمود الأيمن من top+1 إلى bottom.
إذا كان top < bottom وleft < right، اقرأ الصف السفلي من right-1 إلى left والعمود الأيسر من bottom-1 إلى top+1.
أضف واحدًا إلى top وleft، واطرح واحدًا من bottom وright.
أعِد القيم بالترتيب الذي قرأتها به.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

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

الحلقات قصيرة، لذا تكمن الأخطاء عند الزوايا وفي الطبقة الأخيرة.

قراءة الطبقة الأخيرة مرتين عندما تكون صفًا واحدًا أو عمودًا واحدًا. من دون التحقق من top < bottom وleft < right، ينتهي المثال الثاني بـ 9, -4, 9 ويقرأ المثال الثالث 4, 1, 7, 1.
قراءة الزاوية مرتين. إذا امتد كل جانب من خليته الأولى الخاصة به إلى خليته الأخيرة الخاصة به، فستُقرأ كل زاوية بواسطة جانبين. ابدأ كل جانب من خلية واحدة بعد نهاية الجانب السابق.
التكرار ما دام top < bottom بدلًا من top ≤ bottom. يتوقف ذلك قبل الوصول إلى وسط المربع ذي الأبعاد الفردية: في مصفوفة 3 × 3 لا تُقرأ قيمة المركز أبدًا.
الخلط بين الصفوف والأعمدة في مصفوفة ليست مربعة. استخدام matrix.length لكلا الحدّين ينجح مع كل اختبار لمصفوفة مربعة ويفشل مع مصفوفة 3 × 4.
نسيان المدخلات الرفيعة: صف واحد، عمود واحد، خلية واحدة. كل منها طبقة واحدة لا تصل أبدًا إلى الصف السفلي أو العمود الأيسر.
في R، يعدّ a:b تنازليًا عندما يكون a > b، لذا فإن نطاقًا فارغًا مثل 3:2 يعطي 3, 2 بدلًا من لا شيء؛ تحقّق من ذلك أو استخدم seq_len. في Lua وR، يبدأ ترقيم الصفوف والأعمدة من 1.

أسئلة شائعة4

ما التعقيد الزمني وتعقيد المساحة لمصفوفة الحلزون؟

تقرأ كلتا الطريقتين كل قيمة مرة واحدة، لذا يكون الزمن O(m × n)، ولا يمكن لأي حل أن يكون أفضل من ذلك لأن الإجابة تتضمن كل قيمة. يتطلب تقشير الطبقات باستخدام أربعة حدود ذاكرة إضافية O(1)، بخلاف الذاكرة اللازمة للإجابة. أما السير مع الانعطاف عند وجود عائق، فيستخدم شبكة بحجم O(m × n) لتذكّر الخلايا التي قرأها.

كيف تتجنب قراءة قيمة مرتين أثناء اجتياز حلزوني؟

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

كيف تملأ مصفوفة بترتيب حلزوني بدلًا من قراءتها؟

استخدم الحدود الأربعة نفسها والجوانب الأربعة نفسها، لكن اكتب بدلًا من القراءة. احتفظ بعدّاد يبدأ عند 1 وخزّنه في كل خلية أثناء المرور عليها، مع إضافة واحد في كل مرة. بالنسبة إلى مصفوفة n × n، ينتهي العدّاد عند n²، والمثال الأول أعلاه هو الناتج لشبكة 4 × 3.

لماذا يؤدي الانعطاف إلى اليمين عند وجود عائق إلى تكوين حلزوني؟

في الدورة الأولى، ينعطف المتجوّل عند الحواف الأربع للمصفوفة. وفي كل دورة لاحقة، تصبح الخلايا التي قُرئت من قبل بمثابة الجدران، لذا تنعطف كل دورة قبل الحلقة التي سار فيها في المرة السابقة بخلية واحدة. وهذا يُبقي كل دورة داخل الدورة السابقة، فتتشكل الحركة الحلزونية. لا يحتاج المتجوّل أبدًا إلى معرفة الطبقة التي يوجد فيها، بل يكفيه معرفة ما إذا كانت الخلية التالية خالية.

Python

def spiralOrder(matrix):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

المتوقع

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]