Java-da ters setir: setirleri dürli usullar bilen tersleşdirmegi öwrenmek

Algoritmleri bilmän gowy programmist bolmak mümkinmi? Örän jedelli. Hawa, autsorsing kompaniýalarymyzda iş tapyp bilersiňiz, sebäbi söhbetdeşlik wagtynda esasan tehnologiýa hakda sorag berýärler. Decisionsöne kararlaryňyz taýak bilen doldurylsa gowy hünärmen bolarsyňyzmy? Has çynlakaý daşary ýurt kompaniýasyna geçmek isleseňiz, esasan algoritmlere gönükdirilen söhbetdeşliklere duşarsyňyz. Bu ýa-da beýleki usullar, iň esasy algoritmleri kabul etmeli, sebäbi algoritm programmistiň dostudyr . Bu gün bu mowzuklaryň birine degip geçeris we setiri tersleşdirmegiň ýollaryny ara alyp maslahatlaşarys. Bu ýerde hemme zat ýönekeý. Setiri yzyna öwürmek setiri yza çekýär. Mysal üçin: JavaRush baky -> reverof hsuRavaJ Şeýlelik bilen, Java-da bir setiri nädip tersine öwrüp bilersiňiz?

1. StringBuilder / StringBuffer

Iň ýaýran we ýönekeý usul StringBuilder / StringBuffer ulanmak :

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

Iň oňat çözgüt = iň ýönekeý. Java-da bir setiri nädip tersine öwürmelidigi soralanda, ilki bilen kellä gelmeli zat. Algoritmler hakda öňem gürleşipdik, şeýlemi? Geliň, gutulardan çykmaýan çözgütlere göz aýlalyň.

2. Array çözgüdi

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 usuly bilen setirimizi massiwde öwürýäris . Geliň, bu massiwiň soňundan aýlawy işledeliň, ýolda emele gelen setire simwol goşalyň .

3. CharAt bilen çözgüt

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

Bu ýagdaýda, hatda setiri massiwlere bölmek hökman däl, sebäbi her bir simwoly String synp usuly - charAt (sim üçin yzygiderli yza çekmäge mümkinçilik berýän tersine) tersi bolýar.

4. Stack bilen çözgüt

“Stack” synpy köp wagt bäri ulanylmaýar we könelişen hasaplanýar, ýöne muňa garamazdan, salgylanma üçin ulanyp, çözgüdi gözlemek peýdaly bolar:

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

Bu ýerde ýene-de seti massiwlere bölmek we hemmesini umumy görnüşli nyşan bilen Stack- a goýmak üçinCharArray- dan peýdalanýarys . Soň bolsa, stakanyň ýokarsyndan elementleri alyp başlaýarys. LIFO gurluşy hökmünde stakanyň tebigaty sebäpli - L ast I n F irst O ut (ilki bilen, iň soňunda) elementler yza çekiler we netijäniň netijesi hatarda saklanar.

5. Gaýtalama arkaly çözgüt

Algoritm meselesiniň hemmesini diýen ýaly gaýtalamak arkaly çözüp bolýar. Bu ýerde-de biz onsuz edip bilmeris. Evena-da olar bolmasa-da. Galyberse-de, bu gün diňe gaýtalanmagy çözmegiň diňe bir usulyny däl, eýsem birnäçe usulyny hem gözden geçireris.

• usul

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

  Gelýän setiri iki deň bölege bölmek üçin sagStr we leftStr üýtgeýjilerini ulanýarys. Soň bolsa, bu bölünişi ulanyp, setiri iň kiçi bölünýän böleklere böldük (1 nyşan). Ondan soň, gaýtalanýan nyşanlary ters tertipde yzyna gaýtaryp başlaýar (sag tarapdakylar çep tarapda, çep tarapdakylar sagda ýerleşdirildi);

  Her gezek gaýtalanmagyň bir usula köp çagyryşdygyny we netijede serişdeleriň ep-esli harçlanýandygyny ýatdan çykarmaly däldiris. Dogrusy, ýetip bolmajak çykyş ýagdaýy bilen gaýtalanma hakda aýdýan bolsak, bu çäksizlige we StackOverflowError-a barýan ýol.

• ikinji usul

  Bu ýerde bize usul - indeksde goşmaça argument gerek.

  Bu usul işledilende, oňa -1 uzynlyk berilýär:

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

  Usulyň özi:

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

  Indeksimiz haýsy hatar elementini häzir ulanjakdygymyzyň görkezijisi bolup hyzmat edýär (we elementleri soňundan ulanarys).

  Şonuň üçin indeks birinji elemente ýetende çykyş şertlerini kesgitleýäris.

Usulyň öňki ýerine ýetirilişiniň netijesi bilen harp indeksini ulanyp alnan bahalary goşýarys we netijäni gaýtaryp berýäris.

• Üçünji usul

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

  Bu usul, esasan, gaýtalanýan usullaryň iň ýönekeýidir. We ýadymyzda bolsa, ýönekeý = iň gowusy.

  Her ylgawyň dowamynda şol bir setiri kesgitleýäris, ýöne birinji elementsiz. Çykyş ýagdaýy ýetilende (bir nyşan galan wagty), gaýtalanma çöküp başlaýar we indiki netijelere öňki ulanylmadyk nyşan goşular.

6. XOR ulanmak

XOR logiki bitwise amal. Iki üýtgeýji bolan ýagdaýynda, argumentleriň biri dogry, beýlekisi ýalan bolsa, amalyň netijesi dogry. Bitwise amallary barada has giňişleýin maglumaty şu makalada okap bilersiňiz . Indiki çözgüt şu hakykata bagly bolar:

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

Usulyň nähili boljakdygy:

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

Geliň, bu ýerde nämeleriň bolup geçýändigini anyklalyň. Gelýän setirden bir massiw döredýäris. Toplumdan geçmek üçin indeksleri saklaýan pes we ýokary iki üýtgeýji döredýäris . Şoňa laýyklykda biri başyndan ahyryna geçer - 0 bahasyny, ikinjisi - başyndan başyna belläris, arr.length - 1 belläris . Indeksiň ýokary pesliginden uly bolsa, oýnajak aýlawy girizýäris . Ine, gyzykly zatlar bolup başlaýar - eksklýuziw OR-ny ulanmak. Mysal hökmünde x we ​​y seredeliň . Arr [ýokary] = 'x' diýeliň ; Ikilik kody 1 1 1 1 0 0 0 Bu wagt arr [high] = 'n'; Ikilik kody - 1 1 0 1 1 1 0 XOR amallarynda aýlawda nämeler bolar:

1. arr [pes] = (char) (arr [pes] ^ arr [ýokary]);

   
   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 [ýokary] = (char) (arr [pes] ^ arr [ýokary]);

   
   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 [pes] = (char) (arr [pes] ^ arr [ýokary]);

   
   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

Netijede, bu amallaryň netijesinde iki sany massiw öýjüginiň bahalaryny çalyşdyk. arr [ýokary] massiwiň ujundan başlap, [pes] başyndan köp elementdir. Şonuň üçin elementleri diňe şu görkezijiler bilen çalyşýarys. Mysal üçin, “JavaRush hemişelik” sözleminiň birinji ýerine ýetirilişinde J we r çalşylýar, ikinjisinde - a we e we ş.m. Eger-de bizde sanlaryň sany köp bolsa, onda elementdäki elemente ýetenimizde ortasy, aýlawdan çykarys (ýagny orta elementi üýtgetmegiň zerurlygy ýok). Şeýle bolsa, ähli elementleri gaýtadan işlänimizden soň kowarys. Şondan soň, yzygiderli halka girýäris we massiw elementlerinden bir setir gurýarys.