مرحبًا بكم مرة أخرى في سلسلة المدونات الخاصة بنا حول حل المشكلات في هندسة البرمجيات الحديثة!

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

في هذا الجزء، سوف نتعمق في نمط أساسي آخر: نمط المؤشرات المتعددة. يعد هذا النمط لا يقدر بثمن عند التعامل مع السيناريوهات التي تتطلب مقارنة عناصر متعددة أو البحث عنها أو اجتيازها في وقت واحد. دعنا نستكشف كيفية عمله وأين يمكنك تطبيقه لتحسين كفاءة التعليمات البرمجية الخاصة بك.

02. نمط متعدد المؤشرات

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

مثال للمشكلة

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

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

الحل الأساسي

function sumZero(arr){
    for (let i = 0; i 



تعقيد الوقت - O(N^2)

الحل باستخدام نمط المؤشرات المتعددة

الخطوة 1: فهم المشكلة

نحن بحاجة إلى العثور على رقمين في مصفوفة **sorted التي مجموعها يساوي الصفر. وبما أن المصفوفة مرتبة، فيمكننا الاستفادة من هذا الترتيب للعثور على الحل بشكل أكثر كفاءة.

  الخطوة 2: تهيئة مؤشرين  

قم بإعداد مؤشرين: أحدهما (يسار) يبدأ من بداية المصفوفة، والآخر (يمين) يبدأ من النهاية.

مثال:


Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




الخطوة 3: حساب مجموع القيم عند المؤشرات

أضف القيم عند المؤشرات اليسرى واليمنى للحصول على المجموع


Sum = -4   5 = 1




الخطوة 4: قارن المجموع بالصفر

• إذا كان المجموع أكبر من الصفر: حرك المؤشر الأيمن خطوة واحدة إلى اليسار لتقليل المجموع.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• إذا كان المجموع أقل من الصفر: حرك المؤشر الأيسر خطوة واحدة إلى اليمين لزيادة المجموع.

New Sum = -4   2 = -2
Sum is -2 



الخطوة 5: كرر العملية

استمر في تحريك المؤشرات وحساب المجموع حتى تلتقي أو يتم العثور على زوج.


New Sum = -3   2 = -1
Sum is -1 



المجموع هو صفر، لذا ترجع الدالة [-2, 2].

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

الرمز النهائي


function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




ملحوظة:
تعقيد الوقت: O(n) - الوظيفة فعالة وتتدرج خطيًا مع حجم المصفوفة.
تعقيد المساحة: O(1) - تستخدم الوظيفة الحد الأدنى من الذاكرة الإضافية.

خاتمة

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

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