الدوال والمصفوفات والنصوص

تدريب عملي: خوارزميات المصفوفات والنصوص

15 دقيقة الدرس 10 من 14

تدريب عملي: خوارزميات المصفوفات والنصوص

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

سنحلّ أربع مسائل كلاسيكية تظهر باستمرار في المقابلات الوظيفية، وتحدّيات البرمجة، والبرامج الفعلية:

عكس مصفوفة في موضعها
إيجاد القيمة الكبرى في مصفوفة
حساب تكرارات حرف في نص
التحقّق من أن نصًّا مقلوب (palindrome)

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

1. عكس مصفوفة في موضعها

العكس في الموضع يعني أنّنا لا ننشئ مصفوفة ثانية؛ بل نبادل العناصر داخل المصفوفة الأصلية. الأسلوب يُسمّى المؤشّران المتقابلان (Two-Pointer): مؤشّر يبدأ من الفهرس 0 وآخر من آخر فهرس، يتّجهان نحو بعضهما ويتبادلان العناصر حتى يلتقيا.

public static void reverseArray(int[] arr) {
    int left = 0;
    int right = arr.length - 1;

    while (left < right) {
        // مبادلة arr[left] و arr[right]
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        left++;
        right--;
    }
}

// الاستخدام
int[] numbers = {1, 2, 3, 4, 5};
reverseArray(numbers);
System.out.println(Arrays.toString(numbers)); // [5, 4, 3, 2, 1]

لماذا لا ننشئ مصفوفة جديدة؟ إنشاء مصفوفة ثانية يستهلك ذاكرة إضافية بما يتناسب مع حجم المدخل (يُسمّى O(n) space). أسلوب المؤشّرَين لا يحتاج سوى متغيّر واحد إضافي (temp) وهو ثابت — O(1) space — ما يُفيد مع المصفوفات الكبيرة.

2. إيجاد القيمة الكبرى

النمط المعتاد: افترض أن العنصر الأوّل هو الحدّ الأقصى، ثم تجوّل بقيّة المصفوفة وحدّث افتراضك كلّما وجدت قيمة أكبر.

public static int findMax(int[] arr) {
    if (arr.length == 0) {
        throw new IllegalArgumentException("يجب ألا تكون المصفوفة فارغة");
    }

    int max = arr[0]; // ابدأ بالعنصر الأوّل

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    return max;
}

// الاستخدام
int[] scores = {42, 17, 99, 56, 8};
System.out.println("Max: " + findMax(scores)); // Max: 99

احرص دائمًا على التحقّق من المصفوفة الفارغة. استدعاء arr[0] على مصفوفة فارغة يرمي Java استثناءً من نوع ArrayIndexOutOfBoundsException في وقت التشغيل. فحص الطول مع رسالة خطأ واضحة يجعل التنقيح أسهل بكثير.

3. حساب تكرارات حرف

تخزّن كلاس String الأحرف مرتّبة. لحساب كم مرّة يظهر حرف معيّن، نمرّ على كل موضع باستخدام charAt(i) ونزيد عدّادًا عند التطابق.

public static int countOccurrences(String text, char target) {
    int count = 0;

    for (int i = 0; i < text.length(); i++) {
        if (text.charAt(i) == target) {
            count++;
        }
    }

    return count;
}

// الاستخدام
String sentence = "banana";
System.out.println(countOccurrences(sentence, 'a')); // 3
System.out.println(countOccurrences(sentence, 'n')); // 2

حساسية حالة الأحرف مهمّة. الحرف 'A' والحرف 'a' مختلفان في Java. إن أردت إحصاءً بغضّ النظر عن الحالة، حوّل النص والحرف المستهدف معًا إلى حالة واحدة أولًا: text.toLowerCase().charAt(i) وCharacter.toLowerCase(target).

4. التحقّق من كون النص مقلوبًا (Palindrome)

النص المقلوب يُقرأ بالاتّجاهَين بالطريقة ذاتها — مثل "racecar" و"level" و"madam". الأسلوب الأوضح يعكس تقنية عكس المصفوفة: قارن الحرف عند موضع left بالحرف عند موضع right. إذا تطابقت كل الأزواج حتى يلتقي المؤشّران، فالنص مقلوب.

public static boolean isPalindrome(String text) {
    // أزل الأحرف غير الأبجدية الرقمية وحوّل إلى أحرف صغيرة
    String cleaned = text.toLowerCase().replaceAll("[^a-z0-9]", "");

    int left = 0;
    int right = cleaned.length() - 1;

    while (left < right) {
        if (cleaned.charAt(left) != cleaned.charAt(right)) {
            return false; // عدم تطابق — ليس مقلوبًا
        }
        left++;
        right--;
    }

    return true; // كل الأزواج تطابقت
}

// الاستخدام
System.out.println(isPalindrome("racecar"));        // true
System.out.println(isPalindrome("A man a plan a canal Panama")); // true
System.out.println(isPalindrome("hello"));           // false

تنظيف المدخل أولًا قرار تصميمي متعمّد. مسائل النص المقلوب في العالم الواقعي (ومعظم أسئلة المقابلات) لا تعتدّ بالمسافات وعلامات الترقيم. باستدعاء replaceAll مع تعبير نمطي في البداية مرّة واحدة، تظل حلقة المقارنة بسيطة وتركّز على المهمّة الأساسية.

الأنماط المشتركة

لاحظ الأنماط المتكرّرة في الخوارزميات الأربع:

المؤشّران المتقابلان — استُخدم في مسألتَي العكس والنص المقلوب. كلّما أردت مقارنة أو مبادلة من طرفَي تسلسل، تذكّر هذا النمط.
النتيجة الجارية — استُخدم في مسألتَي الحدّ الأقصى والتعداد. هيّئ متغيّرًا قبل الحلقة، حدّثه داخلها، وأعده بعدها.
الحراسة المبكّرة — تحقّق من الحالات الحدّية (مدخل فارغ، قيمة null) في أعلى التابع مباشرةً، ودع المسار الطبيعي يسير دون تشتّت دفاعي.
الأسماء الوصفية للتوابع — isPalindrome وfindMax تخبر القارئ بما يفعله التابع قبل أن يقرأ سطرًا واحدًا من جسمه.

عادة تدريبية: بعد كتابة أيّ خوارزمية، اختبرها بثلاثة مدخلات على الأقل — حالة طبيعية، حالة حدّية (نص فارغ، عنصر واحد، طول زوجي مقابل فردي)، وحالة تكون فيها الإجابة false أو صفرًا. هذه الاختبارات الثلاثة تكتشف الغالبية العظمى من أخطاء off-by-one.

الخلاصة

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