Jump Game
أنت تقف عند الفهرس 0 في المصفوفة nums. من الفهرس i يمكنك القفز إلى الأمام بأي عدد من الخطوات من 1 إلى nums[i]، لذا فإن nums[i] هو أطول قفزة يمكنك القيام بها من هناك، وتعني القيمة 0 أنك لا تستطيع التحرك. أعد true إذا أوصلتك سلسلة من القفزات إلى الفهرس الأخير، وfalse خلاف ذلك.
الدالة
- numsinteger-array
- أطول قفزة يمكنك القيام بها من كل فهرس
- تُرجعboolean
- true إذا كان بإمكانك الوصول إلى الفهرس الأخير بدءًا من الفهرس 0، وإلا false
القيود
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 105- قد تكون القفزة أقصر من
nums[i]، لذا فإن القفزة الطويلة لا تجبرك أبدًا على تجاوز الفهرس الأخير.
أمثلة
- المدخلات
- nums = [2, 0, 3, 1, 0, 2]
- المخرجات
- true
- الشرح
- من الفهرس 0 يمكنك الوصول إلى الفهرس 1 أو 2. يحتوي الفهرس 1 على 0 وهو طريق مسدود، لكن الفهرس 2 يحتوي على 3 ويصل إلى الفهرس 5، وهو الفهرس الأخير.
- المدخلات
- nums = [1, 3, 0, 0, 0, 2]
- المخرجات
- false
- الشرح
- يمكن للمؤشر 0 الانتقال إلى المؤشر 1 فقط، ويصل المؤشر 1 إلى المؤشر 4 كحد أقصى. تحتوي المؤشرات 2 و3 و4 جميعها على 0، لذا لا يتجاوز أي شيء المؤشر 4 ليصل إلى المؤشر 5.
- المدخلات
- nums = [0]
- المخرجات
- true
- الشرح
- تحتوي المصفوفة على عنصر واحد، لذا تبدأ عند الفهرس الأخير ولا تحتاج إلى أي قفزة.
+18 اختبارات مخفية عند الإرسال
سؤال إضافي
احسب عدد تسلسلات القفز المختلفة التي تصل إلى الفهرس الأخير، بترديد 10^9+7، مع الحفاظ على زمن تنفيذ O(n).
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لا يحاصرك
0إلا عندما لا يستطيع أي شيء قبله القفز فوقه. ما الذي تحتاج إلى معرفته عن الفهارس التي تسبقه لتتمكن من تحديد ذلك؟إذا كان بإمكانك الوصول إلى الفهرس
i، فيمكنك الوصول إلى كل فهرس منiحتىi+nums[i]، لأن القفزات الأقصر مسموح بها. لذا تشكّل الفهارس التي يمكن الوصول إليها دائمًا كتلة متصلة تبدأ عند الفهرس 0.تحرّك من اليسار إلى اليمين، واحتفظ بـ
farthest، وهو الطرف الأيمن من ذلك المدى. إذا كان الفهرس الحالي يتجاوزfarthest، فلا يمكن الوصول إليه مطلقًا. وإلا، فوسّعfarthestإلىi+nums[i]إذا كانت هذه القيمة أكبر. إذا اجتزت المصفوفة بأكملها، فيمكن الوصول إلى الفهرس الأخير.
الحل
يزداد عدد المسارات الممكنة أُسّيًا، لذا لا يمكن لفحص المسارات واحدًا تلو الآخر أن ينجح مع المصفوفات الطويلة. والحقيقة الأساسية هي أن الفهارس التي يمكنك الوصول إليها تشكّل دائمًا كتلة متصلة تبدأ عند الفهرس 0. رقم واحد، وهو الطرف الأيمن لتلك الكتلة، يتضمن كل ما تحتاج إليه، وتحدّد جولة واحدة الإجابة.
جرّب كل قفزة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
أبسط فكرة هي أن تنفّذ ذلك بنفسك. قف عند الفهرس 0 وجرّب، واحدًا تلو الآخر، كل موضع هبوط تسمح به قفزتك. ومن كل موضع هبوط، كرّر الأمر نفسه. إذا وصل أي مسار إلى الفهرس الأخير، فالإجابة هي true. وإذا انتهى كل مسار إلى طريق مسدود، فالإجابة هي false.
في المثال الأول، يحتوي الفهرس 0 على 2، لذا تجرّب الفهرس 1 والفهرس 2. يحتوي الفهرس 1 على 0، وهو طريق مسدود، لذا تعود وتحاول الفهرس 2. يحتوي الفهرس 2 على 3، ويصل إلى الفهرس 5، وهو الفهرس الأخير، فيتوقف البحث وتكون النتيجة true.
البحث صحيح لأنه يفحص كل مسار. وهذه أيضًا مشكلته: فهو لا يتذكر أبدًا الفهرس الذي سبق أن استكشفه، لذلك يعيد استكشاف الفهرس نفسه لكل مسار يصل إليه. عندما تكون الإجابة false، عليه استبعاد كل المسارات. في [4, 3, 2, 1, 0, 5]، يمكن لكل فهرس يسبق 0 الوصول إلى 0، ما ينتج عنه 8 مسارات مختلفة إليه. ومع وجود 30 فهرسًا من هذا النوع، يتجاوز عدد المسارات 500 مليون، بينما تحتوي أكبر حالات الاختبار على 10,000 عنصر. كما أن مسارًا بهذا الطول يتجاوز سعة مكدس الاستدعاءات في بعض اللغات: إذ تتوقف Python افتراضيًا عند 1,000 استدعاء متداخل.
الخوارزمية
- اكتب دالة مساعدة
reach(i)تجيب عن السؤال: هل يمكنك الوصول من الفهرسiإلى الفهرس الأخير؟ - إذا كان
iهو الفهرس الأخير، فأعِدtrue. - وإلا، فجرّب كل موضع هبوط
nextمنi+1إلىmin(i+nums[i], n-1)، وأعِدtrueبمجرد أن تُعيدreach(next)ذلك. - إذا لم ينجح أي موضع هبوط، فأعِد
false. - الإجابة هي
reach(0).
def canJump(nums):
last = len(nums) - 1
def reach(i):
# Can you get from index i to the last index?
if i == last:
return True
for nxt in range(i + 1, min(i + nums[i], last) + 1):
if reach(nxt):
return True
return False
return reach(0)تذكّر الفهارس التي يمكن أن تنهي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يطرح البحث أعلاه السؤال نفسه، «هل يمكن أن ينتهي الفهرس j؟»، مرارًا وتكرارًا. لا تتغير الإجابة بالنسبة إلى j، لذا احسبها مرة واحدة وخزّنها. اعتبر الفهرس جيدًا إذا أمكن الوصول منه إلى الفهرس الأخير. الفهرس الأخير جيد. ويكون أي فهرس آخر i جيدًا عندما يكون أحد الفهارس التي يمكنه الوصول إليها، من i+1 إلى i+nums[i]، جيدًا.
يعتمد كل فهرس فقط على الفهارس التي تقع إلى يمينه، لذا املأ جدولًا good من اليمين إلى اليسار. في المثال الأول، الفهرس 5 جيد. يحمل الفهرس 4 القيمة 0، لذا فهو ليس جيدًا. لا يصل الفهرس 3 إلا إلى الفهرس 4، وهو ليس جيدًا. يصل الفهرس 2 إلى الفهارس 3 و4 و5، وبما أن 5 جيد، فإن 2 جيد. يحمل الفهرس 1 القيمة 0، لذا فهو ليس جيدًا. يصل الفهرس 0 إلى الفهرسين 1 و2، وبما أن 2 جيد، فالإجابة هي true.
يُحسم أمر كل فهرس مرة واحدة الآن، لكن حسمه قد يتطلب فحص ما يصل إلى n خلايا. في [9998, 9997, …, 1, 0, 7]، يمكن لكل فهرس الوصول إلى 0 ولا شيء بعده، لذا يفحص كل فهرس نطاقه بالكامل ولا يجد أي فهرس جيد. وهذا يعادل نحو 5 × 10^7 عملية فحص لـ 10,000 عنصر، وقد بُنيت أكبر الاختبارات على هذا النحو. يزداد العمل مع مربع طول القائمة، لذا تنفد المهلة عند تشغيلها.
الخوارزمية
- أنشئ مصفوفة من القيم المنطقية
goodبطولn، واجعل قيمةgood[n-1]تساوي true. - مرّ على
iبدءًا منn-2نزولًا إلى 0. - افحص
jبدءًا منi+1وصولًا إلىmin(i+nums[i], n-1). إذا كانت قيمة أيٍّ منgood[j]تساوي true، فاجعل قيمةgood[i]تساوي true وأوقف الفحص. - أعِد
good[0].
def canJump(nums):
n = len(nums)
good = [False] * n # good[i]: from i you can reach the last index
good[n - 1] = True
for i in range(n - 2, -1, -1):
for j in range(i + 1, min(i + nums[i], n - 1) + 1):
if good[j]:
good[i] = True
break
return good[0]تتبّع أبعد فهرس يمكن الوصول إليه
الفكرة
انظر إلى الفهارس التي يمكنك الوصول إليها، لا إلى المسارات. من الفهرس i يمكنك الوصول إلى أي فهرس من i+1 إلى i+nums[i]، بلا فجوات. لذلك، ما إن يصبح الفهرس i قابلًا للوصول، يصبح كل فهرس حتى i+nums[i] قابلًا للوصول أيضًا. ابدأ بالفهرس 0 وحده، واستمر في إضافة هذه الامتدادات. يبدأ كل امتداد جديد داخل الكتلة التي لديك بالفعل، لذا تشكّل الفهارس القابلة للوصول دائمًا كتلة واحدة متصلة، [0, farthest].
لهذا يكفي رقم واحد. مرّ على i من اليسار إلى اليمين. ما دام i ≤ farthest، يكون الفهرس i قابلًا للوصول، لذا وسّع farthest إلى max(farthest, i+nums[i]). إذا تجاوز i قيمة farthest في أي وقت، فلن تقفز أي فهرسة قابلة للوصول إلى i. لا يمكن للكتلة أن تمتد عبر تلك الفجوة، لذا لا يمكن الوصول إلى أي شيء على يمينها، بما في ذلك الفهرس الأخير. إذا وصلت أثناء المرور إلى النهاية من دون فجوة، فسيكون الفهرس الأخير قابلًا للوصول.
في المثال الثاني، تكون قيمة farthest هي 0، ثم تصبح 1 بعد الفهرس 0، ثم 4 بعد الفهرس 1. قيم الفهارس 2 و3 و4 هي 0، وتُبقيها عند 4. يقع الفهرس 5 بعد 4، لذا تكون الإجابة false. في المثال الأول، يرفع الفهرس 2 قيمة farthest إلى 5، ولا يتجاوزها أي فهرس أبدًا، لذا تكون الإجابة true.
لماذا يكون الاكتفاء بأبعد مدى آمنًا؟ أنت لا تلتزم بأي قفزة. تضم الكتلة كل فهرس يمكن الوصول إليه عبر أي مسار، وتقع كل نقطة هبوط أقرب داخلها. إن الاحتفاظ بالطرف الأيمن وحده لا يفقد أي معلومات.
الخوارزمية
- عيّن
farthest = 0. - لكل فهرس
iمن اليسار إلى اليمين: إذا كانi > farthest، فأعِدfalse. - وإلا، عيّن
farthest = max(farthest, i+nums[i]). - إذا انتهت الحلقة، فهذا يعني أن الوصول إلى كل فهرس كان ممكنًا، لذا أَعِد
true.
def canJump(nums):
farthest = 0 # every index up to farthest can be reached
for i, jump in enumerate(nums):
if i > farthest:
return False # nothing reachable jumps to i
farthest = max(farthest, i + jump)
return True
أخطاء شائعة وحالات حدّية
تنشأ معظم الإجابات الخاطئة من قراءة nums[i] على أنه القفزة الوحيدة، أو من ترتيب الشرطين داخل الحلقة.
- القفز دائمًا بمقدار
nums[i]خطوة بالضبط، أو اختيار أطول قفزة دائمًا. مع[2, 5, 0, 0]، تهبط القفزة الكاملة من الفهرس 0 على 0، بينما تصل القفزة بمقدار خطوة واحدة إلى الفهرس 1 ثم إلى النهاية. - إرجاع
falseفور رؤية 0. لا يكون للصفر تأثير إلا إذا لم تقفز أي خطوة قبله إلى ما بعده: تتجاوز[2, 0, 1]الصفر، وتكون الإجابةtrue. - تحديث
farthestقبل التحقق منi > farthest. يجب ألا يؤدي فهرس لا يمكنك الوصول إليه إلى توسيع النطاق، لذا تحقّق أولًا ثم حدّث. - اعتبار المصفوفة ذات العنصر الواحد حالة فشل. فأنت تقف بالفعل عند الفهرس الأخير، لذا تكون الإجابة
true، حتى عندما يكون هذا العنصر 0. - استخدام الاستدعاء الذاتي مع المصفوفات الطويلة. قد يتطلب المسار 10,000 قفزة، ما يؤدي إلى تجاوز سعة مكدس الاستدعاءات في عدة لغات. لا يتطلب المرور الواحد أي استدعاء ذاتي.
أسئلة شائعة4
ما هو التعقيد الزمني للعبة القفز؟
تمرّ زيارة الوصول الأبعد على كل فهرس مرة واحدة، لذا يكون زمن تنفيذها O(n) وتستخدم مساحة إضافية O(1). أمّا أسلوب الجدول فتعقيده O(n²) في أسوأ الحالات، وتجربة كل مسار تستغرق زمنًا أُسّيًا.
لماذا تنجح الطريقة الجشعة في لعبة القفز؟
نظرًا إلى السماح بالقفزات الأقصر، فإن الوصول إلى الفهرس i يعني أنك تستطيع الوصول إلى كل فهرس حتى i+nums[i]. تتداخل هذه الامتدادات دائمًا مع الجزء الذي تم الوصول إليه بالفعل، لذا تشكّل الفهارس التي يمكن الوصول إليها كتلة واحدة تبدأ عند 0. لا تتتبّع العملية الجشعة سوى الطرف الأيمن لتلك الكتلة، وهو ما يصف الكتلة بأكملها، لذا فهي لا تستبعد أبدًا مسارًا كان من الممكن أن ينجح.
هل تُعدّ لعبة القفز مسألة برمجة ديناميكية؟
يمكن حلّها باستخدام البرمجة الديناميكية: علِّم كل فهرس بأنه جيد إذا كانت إحدى نقاط الهبوط الخاصة به جيدة، مع ملء الجدول من اليمين إلى اليسار. يستغرق ذلك O(n²). لاحظ أن الفهرس الجيد الأيسر هو الوحيد المهم، إذ إن أي فهرس يصل إلى فهرس جيد يصل أيضًا إلى الأيسر منه. احتفظ بهذا الفهرس فقط، goal، وانقله إلى i كلما تحقق i+nums[i] ≥ goal. تكون الإجابة هي ما إذا كان goal ينتهي عند 0؛ وهذه عملية مرور بتعقيد O(n) تحاكي الطريقة الجشعة.
كيف تجد الحد الأدنى لعدد القفزات؟
استخدم الفكرة نفسها الخاصة بأبعد مدى على طبقات. احتفظ بنهاية الكتلة التي يمكنك الوصول إليها بعدد القفزات الحالي، وبأبعد فهرس يمكن أن تصل إليه القفزة التالية. عندما يتجاوز i نهاية الكتلة الحالية، تحتاج إلى قفزة إضافية، وتنتهي الكتلة التالية عند ذلك الفهرس الأبعد. ما زال هذا يقتصر على مرور واحد بتعقيد O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def canJump(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [2, 0, 3, 1, 0, 2]
المتوقع
true