Baliktarin ang string sa Java: pag-aaral na baligtarin ang mga string sa iba't ibang paraan

Posible bang maging isang mahusay na programmer nang hindi alam ang mga algorithm? Very, very controversial. Oo, makakahanap ka ng trabaho sa aming mga kumpanya ng outsourcing, dahil sa panahon ng mga panayam, kadalasan ay nagtatanong sila tungkol sa teknolohiya. Ngunit ikaw ba ay magiging isang mahusay na espesyalista kung ang iyong mga desisyon ay puno ng saklay? Kung gusto mong lumipat sa isang mas seryosong dayuhang kumpanya, makakatagpo ka ng mga panayam na pangunahing nakatuon sa mga algorithm. Sa isang paraan o iba pa, sulit na gamitin ang pinakapangunahing mga algorithm, dahil ang isang algorithm ay kaibigan ng isang programmer . Ngayon ay tatalakayin natin ang isa sa mga paksang ito at tatalakayin ang mga paraan upang baligtarin ang isang string. Simple lang ang lahat dito. Ang pag-reverse ng string ay pagpapaatras ng string. Halimbawa: JavaRush forever ->reverof hsuRavaJ Kaya, paano mo mababaligtad ang isang string sa Java?

1. StringBuilder/StringBuffer

Ang pinakakaraniwan at simpleng paraan ay ang paggamit ng StringBuilder/StringBuffer :

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

Pinakamahusay na solusyon = pinakasimple. Kapag tinanong kung paano i-reverse ang isang string sa Java, ito ang unang bagay na dapat maisip. Ngunit napag-usapan natin ang tungkol sa mga algorithm kanina, hindi ba? Tingnan natin ang mga solusyon na hindi sa labas ng kahon.

2. Array solution

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

Kino-convert namin ang aming string sa isang array gamit ang toCharArray method . Magpatakbo tayo ng for loop sa array na ito mula sa dulo nito, pagdaragdag ng mga character sa resultang string sa daan.

3. Solusyon sa charAt

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

Sa kasong ito, hindi na namin kailangan pang hatiin ang string sa isang array, dahil kinukuha namin ang bawat character gamit ang String class method - charAt (ang para sa loop, muli, ay reverse, na nagpapahintulot sa amin na kunin ang mga character nang sunud-sunod pabalik).

4. Solusyon sa Stack

Ang klase ng Stack ay hindi ginagamit sa loob ng mahabang panahon, at ito ay itinuturing na lipas na, ngunit gayunpaman, para sa sanggunian, magiging kapaki-pakinabang na tingnan ang isang solusyon gamit ito:

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

Dito muli namin ginagamit ang toCharArray upang hatiin ang string sa isang array at ilagay ang lahat ng ito sa aming Stack na may isang generic na uri ng Character . Susunod, nagsisimula kaming kumuha ng mga elemento mula sa tuktok ng stack. Dahil sa likas na katangian ng stack bilang istraktura ng LIFO - L as I n F irst O ut (first in, last out), ang mga elemento ay dadalhin pabalik at ang resulta ay maiimbak sa magreresultang row.

5. Solusyon sa pamamagitan ng recursion

Halos lahat ng problema sa algorithm ay maaaring malutas gamit ang recursion. At dito hindi rin natin magagawa kung wala siya. O kahit wala sila. Pagkatapos ng lahat, ngayon ay isasaalang-alang natin hindi lamang ang isang paraan ng paglutas ng recursion, ngunit marami.

• unang paraan

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

  Ginagamit namin ang rightStr at leftStr variable para hatiin ang papasok na string sa dalawang magkapantay na bahagi. Susunod, gamit ang split na ito, hinati namin ang string sa pinakamaliit na bahaging mahahati (1 character). Pagkatapos, ang recursion ay nagsisimulang bumagsak, ibinabalik ang mga character sa kabaligtaran na pagkakasunud-sunod (ang mga nasa kanan ay inilagay sa kaliwa; ang mga nasa kaliwa ay inilagay sa kanan)

  Hindi natin dapat kalimutan na ang bawat recursion ay isang maramihang tawag sa isang pamamaraan, at bilang resulta, isang malaking paggasta ng mga mapagkukunan. Well, kung pinag-uusapan natin ang tungkol sa recursion na may hindi matamo na kondisyon sa paglabas, ito ang landas sa infinity at sa StackOverflowError.

• dalawang paraan

  Dito kailangan namin ng karagdagang argumento sa pamamaraan - index.

  Kapag ang pamamaraang ito ay pinapatakbo, binibigyan ito ng haba ng string na -1:

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

  At ang pamamaraan mismo:

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

  Ang aming index ay nagsisilbing tagapagpahiwatig kung aling elemento ng row ang gagamitin namin ngayon (at gagamitin namin ang mga elemento mula sa dulo).

  Samakatuwid, nagtakda kami ng mga kundisyon sa paglabas kapag naabot ng index ang unang elemento.

Idinagdag namin ang mga halaga na nakuha gamit ang index ng titik na may resulta ng nakaraang pagpapatupad ng pamamaraan at ibinalik ang resulta.

• ikatlong paraan

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

  Ang pamamaraang ito ay mahalagang pinakasimple sa mga recursive. At tulad ng naaalala natin, simple = pinakamahusay.

  Sa bawat pagtakbo, tinutukoy namin ang parehong string, ngunit wala ang unang elemento. Kapag naabot na ang kundisyon ng paglabas (kapag mayroon kaming isang character na natitira), ang recursion ay magsisimulang bumagsak, at ang dating hindi nagamit na character ay idaragdag sa bawat kasunod na resulta.

6. Gamit ang XOR

Ang XOR ay isang lohikal na bitwise na operasyon. Sa kaso ng dalawang variable, ang resulta ng isang operasyon ay totoo kung at kung ang isa sa mga argumento ay totoo at ang isa ay mali. Maaari kang magbasa nang higit pa tungkol sa mga pagpapatakbo ng bitwise sa artikulong ito . Ang susunod na solusyon ay umaasa sa katotohanan na:

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

Ano ang magiging hitsura ng pamamaraan:

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

Alamin natin kung ano ang nangyayari dito. Lumilikha kami ng array mula sa papasok na string. Lumilikha kami ng dalawang variable, mababa at mataas , na nag-iimbak ng mga index para sa pagtawid sa array. Alinsunod dito, ang isa ay lilipat mula simula hanggang wakas - binibigyan namin ito ng halaga 0, ang pangalawa - mula sa dulo hanggang simula, itinakda namin ito arr.length - 1 . Naglalagay kami ng loop na maglalaro hangga't ang index high ay mas malaki kaysa mababa . Dito magsisimulang mangyari ang mga nakakatuwang bagay - ang paggamit ng eksklusibong OR. Tingnan natin ang x at y bilang isang halimbawa . Ipagpalagay na arr[high] = 'x'; Ang binary code nito ay magiging 1 1 1 1 0 0 0 Sa oras na ito arr[high] = 'n'; Binary code - 1 1 0 1 1 1 0 Ano ang mayroon tayo sa mga operasyon ng XOR sa isang loop:

1. arr[mababa] = (char) (arr[mababa] ^ arr[mataas]);

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

   
   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

Bilang resulta, salamat sa mga operasyong ito, pinalitan namin ang mga halaga ng dalawang array cell. Ang arr[high] ay kasing dami ng elemento mula sa dulo ng array gaya ng arr[low] mula sa simula. Samakatuwid, pinapalitan lang namin ang mga elemento gamit ang mga indeks na ito. Halimbawa, sa unang execution sa pangungusap na "JavaRush forever" ang J at r ay mapapalitan, sa pangalawa - a at e , atbp. Kung mayroon tayong kakaibang bilang ng mga character, pagkatapos ay kapag naabot natin ang elemento na nasa gitna, kami ay itatapon sa labas ng loop (i.e. Hindi na kailangang baguhin ang gitnang elemento). Kung ito ay pantay, itatapon kami pagkatapos iproseso ang lahat ng mga elemento. Well, pagkatapos nito pumunta kami sa isang regular na loop at bumuo ng isang string mula sa mga elemento ng array.