السلسلة العكسية في Java: تعلم عكس السلاسل بطرق مختلفة

هل من الممكن أن تصبح مبرمجًا جيدًا دون معرفة الخوارزميات؟ مثير للجدل للغاية. نعم، يمكنك العثور على وظيفة في شركات الاستعانة بمصادر خارجية لدينا، لأنه خلال المقابلات يتم طرح أسئلة معظمها حول التكنولوجيا. ولكن هل ستكون متخصصًا جيدًا إذا كانت قراراتك مليئة بالعكازات؟ إذا كنت ترغب في الانتقال إلى شركة أجنبية أكثر جدية، فسوف تواجه مقابلات تركز بشكل أساسي على الخوارزميات. بطريقة أو بأخرى، من المفيد اعتماد الخوارزميات الأساسية، لأن الخوارزمية هي صديق المبرمج . سنتطرق اليوم إلى أحد هذه المواضيع ونناقش طرق عكس السلسلة. كل شيء بسيط هنا. عكس السلسلة هو إعادة السلسلة إلى الوراء. على سبيل المثال: JavaRush إلى الأبد ->reverof hsuRavaJ إذن، كيف يمكنك عكس سلسلة في Java؟

1.StringBuilder/StringBuffer

الطريقة الأكثر شيوعًا وبساطة هي استخدام StringBuilder/StringBuffer :

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

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

2. حل المصفوفة

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

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

3. الحل مع charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

في هذه الحالة، لا نحتاج حتى إلى تقسيم السلسلة إلى مصفوفة، لأننا نستخرج كل حرف باستخدام طريقة فئة السلسلة - charAt (حلقة for، مرة أخرى، تكون عكسية، مما يسمح لنا بأخذ الأحرف بشكل تسلسلي إلى الوراء).

4. الحل مع المكدس

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

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

هنا مرة أخرى نستخدم toCharArray لتقسيم السلسلة إلى مصفوفة ووضعها كلها في المكدس الخاص بنا باستخدام نوع عام Character . بعد ذلك، نبدأ في أخذ العناصر من أعلى المكدس. نظرًا لطبيعة المكدس كبنية LIFO - L ast I n F first O ut (أولًا يدخل وآخر يخرج)، سيتم أخذ العناصر إلى الوراء وسيتم تخزين النتيجة في الصف الناتج.

5. الحل عن طريق العودية

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

• الطريقة الأولى

  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
  
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
  
    return reverseString(rightStr) + reverseString(leftStr);
  }

  نستخدم متغيرات rightStr و leftStr لتقسيم السلسلة الواردة إلى جزأين متساويين. بعد ذلك، باستخدام هذا التقسيم، قمنا بتقسيم السلسلة إلى أصغر أجزاء قابلة للقسمة (حرف واحد). بعد ذلك، تبدأ عملية التكرار في الانهيار، مما يؤدي إلى إرجاع الأحرف بالترتيب المعاكس (تم وضع الأحرف التي كانت على اليمين على اليسار، وتلك التي كانت على اليسار تم وضعها على اليمين)

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

• الطريقة الثانية

  نحتاج هنا إلى وسيطة إضافية في الطريقة - Index.

  عند تشغيل هذه الطريقة، يتم إعطاء سلسلة بطول -1:

  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));

  والطريقة نفسها:

  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
  
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }

  يعمل فهرسنا كمؤشر لعنصر الصف الذي سنستخدمه الآن (وسوف نستخدم العناصر من النهاية).

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

نقوم بإضافة القيم التي تم الحصول عليها باستخدام فهرس الحروف مع نتيجة التنفيذ السابق للطريقة وإرجاع النتيجة.

• الطريقة الثالثة

  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }

  هذه الطريقة هي في الأساس أبسط الطرق العودية. وكما نتذكر، بسيط = الأفضل.

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

6. استخدام XOR

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

(A XOR B) XOR B = A
(A XOR B) XOR A = B

كيف ستبدو الطريقة:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

دعونا معرفة ما يحدث هنا. نقوم بإنشاء مصفوفة من السلسلة الواردة. نقوم بإنشاء متغيرين، low و high ، لتخزين الفهارس لاجتياز المصفوفة. وفقا لذلك، سوف ينتقل المرء من البداية إلى النهاية - قمنا بتعيين القيمة 0 لها، والثاني - من النهاية إلى البداية، قمنا بتعيينها arr.length - 1 . ندخل في حلقة يتم تشغيلها طالما أن ارتفاع المؤشر أكبر من انخفاضه . هذا هو المكان الذي تبدأ فيه الأشياء الممتعة - استخدام OR الحصري. دعونا ننظر إلى x و y كمثال . لنفترض أن arr[high] = 'x'; سيكون رمزه الثنائي 1 1 1 1 0 0 0 في هذا الوقت arr[high] = 'n'; الكود الثنائي - 1 1 0 1 1 1 0 ما سيكون لدينا في عمليات XOR في الحلقة:

1. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0

2. arr[high] = (char) (arr[low] ^ arr[high]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0

3. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0

ونتيجة لذلك، وبفضل هذه العمليات، قمنا بتبديل قيم خليتين مصفوفتين. arr[high] هو عدد العناصر من نهاية المصفوفة مثل arr[low] من البداية. لذلك، نقوم ببساطة بتبديل العناصر بهذه المؤشرات. على سبيل المثال، في التنفيذ الأول في جملة "JavaRush إلى الأبد"، سيتم تبديل J و r ، في التنفيذ الثاني - a و e ، وما إلى ذلك. إذا كان لدينا عدد فردي من الأحرف، فعندما نصل إلى العنصر الموجود في الأوسط، سيتم طردنا من الحلقة (أي ليست هناك حاجة لتغيير العنصر الأوسط). إذا كان الأمر متساويًا، فسيتم طردنا بعد معالجة جميع العناصر. حسنًا، بعد ذلك ندخل في حلقة عادية ونبني سلسلة من عناصر المصفوفة.