Reverse string ใน Java: เรียนรู้ที่จะกลับสตริงในรูปแบบต่างๆ

เป็นไปได้ไหมที่จะกลายเป็นโปรแกรมเมอร์ที่ดีโดยไม่ต้องรู้อัลกอริธึม? ขัดแย้งกันมาก ใช่ คุณสามารถหางานในบริษัทเอาท์ซอร์สของเราได้ เพราะในระหว่างการสัมภาษณ์พวกเขาจะถามคำถามเกี่ยวกับเทคโนโลยีเป็นส่วนใหญ่ แต่คุณจะเป็นผู้เชี่ยวชาญที่ดีได้หรือไม่หากการตัดสินใจของคุณเต็มไปด้วยไม้ค้ำยัน? หากคุณต้องการย้ายไปยังบริษัทต่างชาติที่จริงจังมากขึ้น คุณจะได้พบกับบทสัมภาษณ์ที่เน้นไปที่อัลกอริธึมเป็นหลัก ไม่ทางใดก็ทางหนึ่ง มันก็คุ้มค่าที่จะใช้อัลกอริ ธึมพื้นฐานที่สุด เพราะอัลกอริธึมคือเพื่อนของโปรแกรมเมอร์ วันนี้เราจะพูดถึงหัวข้อใดหัวข้อหนึ่งเหล่านี้และหารือถึงวิธีการกลับรายการสตริง ทุกอย่างเรียบง่ายที่นี่ การย้อนกลับสตริงคือการทำให้สตริงถอยหลัง ตัวอย่างเช่น: JavaRush ตลอดไป ->reverof hsuRavaJ ดังนั้น คุณจะย้อนกลับสตริงใน Java ได้อย่างไร?

1. StringBuilder/StringBuffer

วิธีที่ธรรมดาและง่ายที่สุดคือการใช้StringBuilder/StringBuffer :

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

ทางออกที่ดีที่สุด = ง่ายที่สุด เมื่อถูกถามถึงวิธีย้อนกลับสตริงใน Java นี่เป็นสิ่งแรกที่ควรคำนึงถึง แต่เราคุยกันเรื่องอัลกอริธึมก่อนหน้านี้ใช่ไหม เรามาดูวิธีแก้ปัญหาที่ไม่แกะกล่องกันดีกว่า

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 loop ผ่านอาร์เรย์นี้จากจุดสิ้นสุด โดยเพิ่มอักขระลงในสตริงผลลัพธ์ไปพร้อมกัน

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;
}

ในกรณีนี้ เราไม่จำเป็นต้องแยกสตริงออกเป็นอาร์เรย์ เนื่องจากเราแยกอักขระแต่ละตัวโดยใช้เมธอด คลาส String - charAt (สำหรับการวนซ้ำอีกครั้งเป็นการย้อนกลับ ซึ่งช่วยให้เราสามารถนำอักขระไปข้างหลังตามลำดับ)

4. วิธีแก้ปัญหาด้วย Stack

คลาส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เพื่อแยกสตริงออกเป็นอาร์เรย์และใส่ทั้งหมดลงในStack ของ เรา ด้วยประเภททั่วไปCharacter ต่อไป เราเริ่มรับองค์ประกอบจากด้านบนของสแต็ก เนื่องจากธรรมชาติของสแต็กเป็น โครงสร้าง LIFO - L ast I n F irst 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เพื่อแยกสตริงขาเข้าออกเป็นสองส่วนเท่าๆ กัน ต่อไป เมื่อใช้การแยกนี้ เราจะแบ่งสตริงออกเป็นส่วนที่เล็กที่สุดที่หารได้ (1 อักขระ) หลังจากนั้นการเรียกซ้ำเริ่มพังทลายลงโดยคืนอักขระในลำดับตรงกันข้าม (ตัวที่อยู่ทางขวาจะวางอยู่ทางซ้าย ตัวที่อยู่ทางซ้ายจะวางอยู่ทางขวา)

  เราต้องไม่ลืมว่าการเรียกซ้ำแต่ละครั้งเป็นการเรียกเมธอดหลายครั้ง และเป็นผลให้ต้องใช้ทรัพยากรเป็นจำนวนมาก ถ้าเรากำลังพูดถึงการเรียกซ้ำโดยมีเงื่อนไขทางออกที่ไม่สามารถบรรลุได้ นี่คือเส้นทางสู่อนันต์และไปยัง StackOverflowError

• วิธีที่สอง

  ที่นี่เราต้องการอาร์กิวเมนต์เพิ่มเติมในวิธีการ - ดัชนี

  เมื่อเรียกใช้เมธอดนี้ จะได้รับความยาวสตริงเป็น -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เป็นการดำเนินการระดับบิตเชิงตรรกะ ในกรณีของตัวแปรสองตัว ผลลัพธ์ของการดำเนินการจะเป็นจริงก็ต่อเมื่ออาร์กิวเมนต์ตัวใดตัวหนึ่งเป็นจริงและอีกตัวเป็นเท็จ คุณสามารถอ่านเพิ่มเติมเกี่ยวกับการดำเนิน การระดับบิตได้ในบทความนี้ แนวทางแก้ไขถัดไปจะขึ้นอยู่กับข้อเท็จจริงที่ว่า:

(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;
}

เรามาดูกันว่าเกิดอะไรขึ้นที่นี่ เราสร้างอาร์เรย์จากสตริงที่เข้ามา เราสร้างตัวแปรสองตัวต่ำและสูงที่จะจัดเก็บดัชนีสำหรับการสำรวจอาร์เรย์ ดังนั้นเราจะย้ายจากต้นจนจบ - เราให้ค่าเป็น 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[ต่ำ] = (ถ่าน) (arr[ต่ำ] ^ arr[สูง]);

   
   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[สูง] = (ถ่าน) (arr[ต่ำ] ^ arr[สูง]);

   
   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[ต่ำ] = (ถ่าน) (arr[ต่ำ] ^ arr[สูง]);

   
   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เป็นต้น หากเรามีอักขระจำนวนคี่จากนั้นเมื่อเราไปถึงองค์ประกอบที่อยู่ใน ตรงกลาง เราจะหลุดออกจากวง (นั่นคือ ไม่จำเป็นต้องเปลี่ยนองค์ประกอบตรงกลาง) หากเป็นคู่ เราจะถูกโยนออกไปหลังจากประมวลผลองค์ประกอบทั้งหมดแล้ว หลังจากนั้นเราจะเข้าสู่วงปกติและสร้างสตริงจากองค์ประกอบอาร์เรย์