كيفية حل التحدي رمز مؤشر Palindrome

كيفية حل تحدي رمز مؤشر Palindrome الخاص بـ HackerRank باستخدام JavaScript

كيفية حل تحدي رمز مؤشر Palindrome الخاص بـ HackerRank باستخدام JavaScript

مشكلة

دعنا نقسم التحدي إلى متطلبات:

  • رابط للتحدي: تحدي رمز Palindrome Index الخاص بـ HackerRank
  • سوف تتلقى سلسلة واحدة ، ق
  • s بين 1 و 100005 ضمناً
  • يسمح لك بإزالة خطاب
  • إذا قمت بإزالة خطاب ، فيجب عليك إرجاع الفهرس الخاص به
  • السلسلة بعد إزالة الحرف سوف تساوي نفسها للخلف (مثل: palindrome)
  • إذا لم تتم إزالة أي سلسلة ، أو كان يجب إزالة أكثر من حرف واحد ، فارجع -1
// مثال
"ababab"
// نتيجة
5
// السبب ، عند إزالة الفهرس 5
"ababa" = "ababa" العكس

هدف

اكتب دالة أو وظائف تُرجع فهرس الحرف الذي تمت إزالته من السلسلة (السلسلة) لجعله متآلفًا و -1 غير ممكن أو لا تتم إزالة سلسلة

تغطي قواعدنا

التأكد من أننا نفي بالمتطلبات:

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     if (slen> = 1 && slen <= 100005) {
           // تابع الكود
     }
      
     نتيجة العودة
}

نحتاج أيضًا إلى دراسة ما إذا كانت السلسلة بمفردها لا تحتاج إلى إزالة أي أحرف لجعلها متآكلة.

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           // تابع الكود
     }
      
     نتيجة العودة
}

فهم المشكلة

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

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

عبور الشخصيات

نحن بالتأكيد بحاجة إلى استخدام حلقة لتصفح الحروف:

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          لـ (دعني = 0 ؛ أنا <سلط ؛ i ++) {
               // تابع الكود
          }
     }
      
     نتيجة العودة
}

خلق سلاسل جديدة

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

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          لـ (دعني = 0 ؛ أنا <سلط ؛ i ++) {
               
               / / إنشاء سلسلة جديدة
               دع newS = s.substring (0، i) + s.substring ((i + 1))؛
 
               / / قم بإنشاء عكس هذه السلسلة
               دع revNewS = newS.split (''). revers (). join ('')؛
               
               // قارن
               if (newS === revNewS) {
                    النتيجة = أنا ؛
                    استراحة؛
               }
          }
     }
      
     نتيجة العودة
}

مشاكل مع الحل الأول لدينا

عندما أجريت الاختبارات ، عادت معظم القيم الأصغر الأولي بالنتائج الصحيحة. كانت المشكلة عندما كان طول s 73785 أو أكثر. جاءت النتائج مع:

تم الإنهاء بسبب المهلة

فهم المشكلة مرة أخرى

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

متطلبات Palindrome

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

// مثال - "acbba"
↓ ↓
a c b b a = amesame
  ↓ ↓
أ ب ب أ = ليست هي نفسها

مقارنة الحروف

إعادة تشكيل حلنا الأصلي من حلقة for سيبدو كما يلي:

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          من أجل (دعني = 0 ؛ أنا 

تحديد أي رسالة لإزالة

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

// مثال مع الحلقة - "acbba"
...
أنا = 1
  ↓ ↓
أ ب ب أ = ليست هي نفسها
// يجب أن تكون الإجابة المتوقعة هي (1)
// مثال مع حلقة - "abbca"
...
أنا = 1
  ↓ ↓
أ ب ب ج أ = ليست هي نفسها
يجب أن تكون الإجابة المتوقعة 3 أو (الطول - 1 - ط)

نحتاج بعد ذلك إلى تقييم كلا السيناريوهين للعثور على إجاباتنا.

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          لـ (دعني = 0 ؛ أنا <سلط ؛ i ++) {
               
               // مقارنة الحرف الأول بالآخر ، إلخ
               إذا (s.charAt (i)! = s.charAt (slen - 1 - i)) {
 
                    // حساب للرسالة في التسول.
                    let s1 = s.substring (0، i) + s.substring ((i + 1))؛
                    // المحاسبة عن الرسالة في النهاية
                    اسمحوا s2 = s.substring (0 ، (slen - 1 - i)) + s.sststring ((len - 1 - i) + 1) ؛
               }
          }
     }
      
     نتيجة العودة
}

مقارنة الاوتار

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

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          لـ (دعني = 0 ؛ أنا <سلط ؛ i ++) {
               
               // مقارنة الحرف الأول بالآخر ، إلخ
               إذا (s.charAt (i)! = s.charAt (slen - 1 - i)) {
 
                    // حساب للرسالة في التسول.
                    let s1 = s.substring (0، i) + s.substring ((i + 1))؛
                    // المحاسبة عن الرسالة في النهاية
                    اسمحوا s2 = s.substring (0 ، (slen - 1 - i)) + s.sststring ((len - 1 - i) + 1) ؛
                    
                    إذا (s1 === s1.split (''). revers (). join ('')) {
                         النتيجة = أنا ؛
                         استراحة؛
                    } آخر إذا (s2 === s2.split (''). revers (). join ('')) {
                         النتيجة = القتلى - 1 - i ؛
                         استراحة؛
                    }
               }
          }
     }
      
     نتيجة العودة
}

بدأ هذا بالفعل في الظهور بشكل جيد ، لكننا بحاجة إلى دراسة حالة استخدام أخرى.

ماذا عن أكثر من رسالة واحدة

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

// مثال سيناريو - "acbdbba"
...
أنا = 1
  ↓ ↓
أ ج ب د ب ب أ = ليست هي نفسها
/ / إذا أزلنا ج
"abdbba"! = "abbdba"
/ / إذا أزلنا ب
"acbdba"! = "abdbca"
/ / ليكون ليكون palindrome نحتاج لإزالة حرف آخر
// الذي هو خارج متطلباتنا ، وبالتالي النتيجة = -1

عندئذٍ ، سيتضمن الكود الخاص بنا آخر ما يلي:

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          من أجل (دعني = 0 ؛ أنا 

تحسين الكود حتى أكثر

هناك نوعان من التحسينات الأخيرة التي يمكن أن نجعلها.

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

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          من أجل (دعني = 0 ؛ أنا 

الأمثل للحصول على حلقة

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

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
           
          من أجل (دعني = 0 ؛ أنا 

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

المحلول

الحل الكامل دون تعليقات:

وظيفة palindromeIndex (ق) {
     دع النتيجة = -1 ؛
     const slen = s.length؛
     
     إذا (slen> = 1 && slen <= 100005 & s! == s.split (''). revers (). join ('')) {
          من أجل (دعني = 0 ؛ أنا 

حالات تجريبية

الآن دعنا نتحقق من صحة الكود:

// "a" ، متوقع -1
// "" ، متوقع -1
// "acbdbba" ، متوقع -1
// "aaab" ، المتوقع 3
// "acbba" ، المتوقع 1
palindromeIndex ( "أ")؛ // -1 
palindromeIndex ( "")؛ // -1 
palindromeIndex ( "acbdbba")؛ // -1 
palindromeIndex ( "AAAB")؛ // 3 
palindromeIndex ( "acbba")؛ // 1 

ردود الفعل

إذا كان لديك أي نصائح حول كيفية تحسين هذا أو مناقشة الترميز / خوارزميات ، أحب التحدث.

إذا حصلت على قيمة من ذلك ، فيرجى مشاركتها على twitter أو غيرها من منصات التواصل الاجتماعي. شكرا مرة أخرى على القراءة.

من فضلك اتبعني أيضًا على twitter: @ mannycoding و instagram at mannycodes.