Rentetan terbalik dalam Java: belajar membalikkan rentetan dengan cara yang berbeza

Adakah mungkin untuk menjadi pengaturcara yang baik tanpa mengetahui algoritma? Sangat, sangat kontroversi. Ya, anda boleh mendapatkan pekerjaan di syarikat penyumberan luar kami, kerana semasa temuduga mereka kebanyakannya bertanya soalan tentang teknologi. Tetapi adakah anda akan menjadi pakar yang baik jika keputusan anda dipenuhi dengan tongkat? Jika anda ingin berpindah ke syarikat asing yang lebih serius, anda akan menghadapi temu duga yang tertumpu terutamanya pada algoritma. Satu cara atau yang lain, adalah berbaloi untuk menggunakan algoritma yang paling asas, kerana algoritma adalah rakan pengaturcara . Hari ini kita akan menyentuh salah satu topik ini dan membincangkan cara untuk membalikkan rentetan. Semuanya mudah di sini. Membalikkan rentetan membawa rentetan ke belakang. Contohnya: JavaRush forever ->reverof hsuRavaJ Jadi, bagaimanakah anda boleh membalikkan rentetan dalam Java?

1. StringBuilder/StringBuffer

Cara yang paling biasa dan mudah ialah menggunakan StringBuilder/StringBuffer :

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

Penyelesaian terbaik = paling mudah. Apabila ditanya bagaimana untuk membalikkan rentetan dalam Java, ini adalah perkara pertama yang perlu diingati. Tetapi kita bercakap tentang algoritma sebelum ini, bukan? Mari kita lihat penyelesaian yang bukan di luar kotak.

2. Penyelesaian tatasusunan

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

Kami menukar rentetan kami kepada tatasusunan menggunakan kaedah toCharArray . Mari kita jalankan gelung for melalui tatasusunan ini dari hujungnya, menambah aksara pada rentetan yang terhasil di sepanjang jalan.

3. Penyelesaian dengan charAt

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

Dalam kes ini, kita tidak perlu membahagikan rentetan kepada tatasusunan, kerana kita mengekstrak setiap aksara menggunakan kaedah kelas String - charAt (gelung for, sekali lagi, adalah terbalik, yang membolehkan kita mengambil aksara secara berurutan ke belakang).

4. Penyelesaian dengan Tindanan

Kelas Stack tidak digunakan untuk masa yang lama, dan ia dianggap usang, tetapi bagaimanapun, sebagai rujukan, adalah berguna untuk melihat penyelesaian menggunakannya:

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

Di sini sekali lagi kami menggunakan toCharArray untuk memisahkan rentetan kepada tatasusunan dan meletakkan semuanya dalam Tindanan kami dengan Character jenis generik . Seterusnya, kami mula mengambil elemen dari bahagian atas timbunan. Disebabkan sifat tindanan sebagai struktur LIFO - L as I n F irst O ut (masuk dahulu, keluar terakhir), elemen akan dibawa ke belakang dan hasilnya akan disimpan dalam baris yang terhasil.

5. Penyelesaian secara rekursi

Hampir setiap masalah algoritma boleh diselesaikan menggunakan rekursi. Dan di sini kita juga tidak boleh melakukannya tanpa dia. Atau bahkan tanpa mereka. Lagipun, hari ini kita akan mempertimbangkan bukan hanya satu kaedah untuk menyelesaikan rekursi, tetapi beberapa.

• kaedah satu

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

  Kami menggunakan pembolehubah rightStr dan leftStr untuk memisahkan rentetan masuk kepada dua bahagian yang sama. Seterusnya, menggunakan perpecahan ini, kami membahagikan rentetan kepada bahagian terkecil yang boleh dibahagikan (1 aksara). Selepas itu, rekursi mula runtuh, mengembalikan aksara dalam susunan yang bertentangan (yang di sebelah kanan diletakkan di sebelah kiri; yang di sebelah kiri diletakkan di sebelah kanan)

  Kita tidak boleh lupa bahawa setiap rekursi adalah panggilan berganda kepada kaedah, dan akibatnya, perbelanjaan sumber yang besar. Nah, jika kita bercakap tentang rekursi dengan keadaan keluar yang tidak boleh dicapai, maka ini ialah laluan ke infiniti dan ke StackOverflowError.

• kaedah dua

  Di sini kita memerlukan hujah tambahan dalam kaedah - indeks.

  Apabila kaedah ini dijalankan, ia diberi panjang rentetan -1:

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

  Dan kaedah itu sendiri:

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

  Indeks kami berfungsi sebagai penunjuk elemen baris mana yang akan kami gunakan sekarang (dan kami akan menggunakan elemen dari akhir).

  Oleh itu, kami menetapkan syarat keluar apabila indeks mencapai elemen pertama.

Kami menambah nilai yang diperoleh menggunakan indeks huruf dengan hasil pelaksanaan kaedah sebelumnya dan mengembalikan hasilnya.

• kaedah tiga

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

  Kaedah ini pada asasnya adalah yang paling mudah daripada kaedah rekursif. Dan seperti yang kita ingat, mudah = terbaik.

  Semasa setiap larian, kami menentukan rentetan yang sama, tetapi tanpa elemen pertama. Apabila keadaan keluar dicapai (apabila kita mempunyai satu aksara yang tinggal), rekursi mula runtuh, dan aksara yang tidak digunakan sebelumnya akan ditambahkan pada setiap hasil berikutnya.

6. Menggunakan XOR

XOR ialah operasi bitwise logik. Dalam kes dua pembolehubah, hasil operasi adalah benar jika dan hanya jika salah satu hujah adalah benar dan satu lagi palsu. Anda boleh membaca lebih lanjut mengenai operasi bitwise dalam artikel ini . Penyelesaian seterusnya akan bergantung pada fakta bahawa:

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

Apakah kaedah yang akan kelihatan seperti:

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

Mari kita fikirkan apa yang berlaku di sini. Kami mencipta tatasusunan daripada rentetan masuk. Kami mencipta dua pembolehubah, rendah dan tinggi , yang menyimpan indeks untuk merentasi tatasusunan. Oleh itu, seseorang akan bergerak dari awal ke akhir - kami memberikannya nilai 0, yang kedua - dari akhir ke awal, kami menetapkannya arr.length - 1 . Kami memasukkan gelung yang akan dimainkan selagi indeks tinggi lebih besar daripada rendah . Di sinilah perkara yang menyeronokkan mula berlaku - penggunaan OR eksklusif. Mari kita lihat x dan y sebagai contoh . Katakan arr[tinggi] = 'x'; Kod binarinya ialah 1 1 1 1 0 0 0 Pada masa ini arr[high] = 'n'; Kod binari - 1 1 0 1 1 1 0 Apa yang kita akan ada dalam operasi XOR dalam gelung:

1. arr[rendah] = (char) (arr[rendah] ^ arr[tinggi]);

   
   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[tinggi] = (char) (arr[rendah] ^ arr[tinggi]);

   
   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[rendah] = (char) (arr[rendah] ^ arr[tinggi]);

   
   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

Akibatnya, terima kasih kepada operasi ini, kami menukar nilai dua sel tatasusunan. arr[tinggi] ialah seberapa banyak elemen dari hujung tatasusunan seperti arr[rendah] dari awal. Oleh itu, kita hanya menukar elemen dengan indeks ini. Sebagai contoh, pada pelaksanaan pertama dalam ayat "JavaRush selamanya" J dan r akan ditukar, pada yang kedua - a dan e , dsb. Jika kita mempunyai bilangan aksara ganjil, maka apabila kita mencapai elemen yang ada dalam tengah, kita akan tercampak keluar dari gelung (iaitu Tidak perlu menukar elemen tengah). Jika genap, kami akan dibuang selepas memproses semua elemen. Nah, selepas itu kita pergi ke gelung biasa dan membina rentetan daripada elemen tatasusunan.