Java тіліндегі кері жол: жолдарды әртүрлі тәсілдермен кері қайтаруды үйрену

Алгоритмдерді білмей-ақ жақсы бағдарламашы болу мүмкін бе? Өте, өте даулы. Иә, сіз біздің аутсорсингтік компанияларда жұмыс таба аласыз, өйткені сұхбат кезінде олар көбінесе технологияға қатысты сұрақтар қояды. Бірақ сіздің шешімдеріңіз балдақпен толтырылса, сіз жақсы маман бола аласыз ба? Егер сіз неғұрлым маңызды шетелдік компанияға ауысқыңыз келсе, сіз ең алдымен алгоритмдерге бағытталған сұхбаттарды кездестіресіз. Қалай болғанда да, ең қарапайым алгоритмдерді қабылдаған жөн, өйткені алгоритм бағдарламашының досы . Бүгін біз осы тақырыптардың біріне тоқталып, жолды кері қайтару жолдарын талқылаймыз. Мұнда бәрі қарапайым. Жолды кері қайтару жолды кері алу болып табылады. Мысалы: JavaRush forever ->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 циклін орындап , нәтиже жолына таңбаларды қосамыз.

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 арқылы шығарамыз (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 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 айнымалыларын қолданамыз. Әрі қарай, осы бөлу арқылы жолды ең кіші бөлінетін бөліктерге (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 пайдалану

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 орнатамыз . Біз жоғары индекс төменнен үлкен болғанша ойнайтын циклды енгіземіз . Дәл осы жерде қызықты нәрселер басталады - эксклюзивті НЕМЕСЕ пайдалану. Мысал ретінде x және y мәндерін қарастырайық . arr[жоғары] = 'x' делік ; Оның екілік codeы 1 1 1 1 0 0 0 болады Бұл уақытта arr[жоғары] = 'n'; Екілік code - 1 1 0 1 1 1 0 Циклдегі XOR операцияларында бізде не болады:

1. arr[төмен] = (char) (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[жоғары] = (char) (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[төмен] = (char) (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[жоғары] массивтің соңынан бастап қанша элементтер болса, arr[төмен] басынан сонша болады. Сондықтан біз жай ғана осы индекстермен элементтерді ауыстырамыз. Мысалы, бірінші орындалуда «JavaRush мәңгі» сөйлеміндегі J мен r ауыстырылады, екіншісінде - a және e , т.б. Егер бізде таңбалар саны тақ болса, онда біз таңбадағы элементке жеткенде ортасында, біз циклден лақтырылатын боламыз (яғни, ортаңғы элементті өзгертудің қажеті жоқ). Егер ол біркелкі болса, біз барлық элементтерді өңдегеннен кейін лақтырамыз. Осыдан кейін біз кәдімгі циклге өтіп, массив элементтерінен жол саламыз.