Java-da sətri tərsinə çevirmək: sətirləri müxtəlif yollarla tərsinə çevirməyi öyrənmək

Alqoritmləri bilmədən yaxşı proqramçı olmaq mümkündürmü? Çox, çox mübahisəli. Bəli, siz autsorsing şirkətlərimizdə iş tapa bilərsiniz, çünki müsahibə zamanı onlar daha çox texnologiya ilə bağlı suallar verirlər. Bəs qərarlarınız qoltuqaltılarla dolu olsa, yaxşı mütəxəssis olacaqsınız? Daha ciddi bir xarici şirkətə keçmək istəyirsinizsə, ilk növbədə alqoritmlərə yönəlmiş müsahibələrlə qarşılaşacaqsınız. Bu və ya digər şəkildə ən əsas alqoritmləri qəbul etməyə dəyər, çünki alqoritm proqramçının dostudur . Bu gün biz bu mövzulardan birinə toxunacağıq və sətri tərsinə çevirməyin yollarını müzakirə edəcəyik. Burada hər şey sadədir. Sətri tərsinə çevirmək simi geriyə çəkməkdir. Məsələn: JavaRush forever ->reverof hsuRavaJ Beləliklə, Java-da sətri necə geri qaytarmaq olar?

1. StringBuilder/StringBuffer

Ən ümumi və sadə yol StringBuilder/StringBuffer istifadə etməkdir :

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

Ən yaxşı həll = ən sadə. Java-da bir sətri necə tərsinə çevirmək barədə soruşduqda, ağlına gələn ilk şey budur. Amma biz əvvəllər alqoritmlərdən danışdıq, elə deyilmi? Qutudan kənar olmayan həlləri nəzərdən keçirək.

2. Massiv həlli

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

Biz toCharArray metodundan istifadə edərək sətrimizi massivə çeviririk . Gəlin , bu massivin sonundan başlayaraq for döngüsünü keçirək və nəticədə yaranan sətirə simvollar əlavə edək.

3. charAt ilə həll

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

Bu halda, sətri sıraya bölmək lazım deyil, çünki biz hər simvolu String sinfi metodundan istifadə edərək çıxarırıq - charAt (for döngəsi yenidən tərsdir, bu da bizə simvolları ardıcıl olaraq geri götürməyə imkan verir).

4. Stack ilə həll

Uzun müddətdir heç kim Stack sinfindən istifadə etmir və o, köhnəlmiş hesab olunur, lakin buna baxmayaraq, istinad üçün ondan istifadə edərək həll yoluna baxmaq faydalı olacaq:

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

Burada biz yenə də toCharArray-dan istifadə edərək sətri massivə bölürük və hamısını ümumi xarakter tipli Stack - ə yerləşdiririk . Sonra, yığının yuxarı hissəsindən elementləri götürməyə başlayırıq. Yığın LIFO strukturu kimi xarakterinə görə - L ast I n irst O ut (ilk girən, sonuncu çıxan) elementlər geriyə doğru götürüləcək və nəticə yaranan cərgədə saxlanacaq.

5. Rekursiya ilə həll

Demək olar ki, hər bir alqoritm problemi rekursiyadan istifadə etməklə həll edilə bilər. Və burada da onsuz edə bilmərik. Və ya onlar olmadan. Axı, bu gün biz rekursiyanın həllinin yalnız bir üsulunu deyil, bir neçəsini nəzərdən keçirəcəyik.

• üsul bir

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

  Daxil olan sətri iki bərabər hissəyə bölmək üçün biz rightStr və leftStr dəyişənlərindən istifadə edirik. Sonra, bu bölünmədən istifadə edərək, simi ən kiçik bölünən hissələrə (1 simvol) ayırırıq. Bundan sonra, rekursiya simvolları əks ardıcıllıqla qaytararaq dağılmağa başlayır (sağda olanlar sola, solda olanlar sağa yerləşdirildi)

  Unutmamalıyıq ki, hər bir rekursiya bir metoda çoxlu çağırışdır və nəticədə kifayət qədər resursların xərclənməsidir. Yaxşı, əgər əlçatmaz çıxış şərti ilə rekursiyadan danışırıqsa, bu, sonsuzluğa və StackOverflowError-a gedən yoldur.

• ikinci üsul

  Burada metodda əlavə bir arqumentə ehtiyacımız var - indeks.

  Bu üsul işə salındıqda ona -1 sətir uzunluğu verilir:

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

  Və metodun özü:

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

  İndeksimiz indi hansı sətir elementindən istifadə edəcəyimizin göstəricisi kimi xidmət edir (və biz elementləri sondan istifadə edəcəyik).

  Buna görə də, indeks birinci elementə çatdıqda çıxış şərtlərini təyin edirik.

Metodun əvvəlki icrasının nəticəsi ilə məktub indeksindən istifadə edərək əldə edilmiş dəyərləri əlavə edirik və nəticəni qaytarırıq.

• üçüncü üsul

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

  Bu üsul mahiyyətcə rekursiv olanların ən sadəsidir. Və xatırladığımız kimi, sadə = ən yaxşı.

  Hər qaçış zamanı biz eyni sətri təyin edirik, lakin birinci element olmadan. Çıxış şərtinə çatdıqda (bir simvol qaldıqda) rekursiya dağılmağa başlayır və hər bir sonrakı nəticəyə əvvəlki istifadə olunmamış simvol əlavə olunacaq.

6. XOR-dan istifadə

XOR məntiqi bit əməliyyatıdır. İki dəyişən vəziyyətində, əməliyyatın nəticəsi yalnız və yalnız arqumentlərdən biri doğru, digəri isə yanlış olduqda doğrudur. Bu məqalədə bit əməliyyatları haqqında ətraflı oxuya bilərsiniz . Növbəti həll aşağıdakı faktlara əsaslanacaq:

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

Metod necə görünəcək:

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

Gəlin burada nə baş verdiyini anlayaq. Gələn sətirdən massiv yaradırıq. Massivdən keçmək üçün indeksləri saxlayan iki aşağı və yüksək dəyişən yaradırıq . Müvafiq olaraq, biri başdan sona hərəkət edəcək - biz ona 0 dəyəri qoyuruq, ikincisi - sonundan əvvələ, onu təyin edirik arr.length - 1 . Yüksək indeks aşağıdan böyük olduğu müddətdə oynayacaq bir döngəyə daxil oluruq . Əyləncəli şeylərin baş verdiyi yer budur - eksklüziv OR-dan istifadə. Nümunə olaraq x və y -ə baxaq . Tutaq ki, arr[yüksək] = 'x'; Onun ikili kodu 1 1 1 1 0 0 0 olacaq Bu zaman arr[yüksək] = 'n'; İkili kod - 1 1 0 1 1 1 0 Döngüdə XOR əməliyyatlarında nələrə sahib olacağıq:

1. arr[aşağı] = (char) (arr[aşağı] ^ arr[yüksək]);

   
   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[yüksək] = (char) (arr[aşağı] ^ arr[yüksək]);

   
   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[aşağı] = (char) (arr[aşağı] ^ arr[yüksək]);

   
   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

Nəticədə, bu əməliyyatlar sayəsində iki massiv hüceyrəsinin dəyərlərini dəyişdirdik. arr[yüksək] arr[aşağı] əvvəldən olduğu kimi massivin sonundan çox elementdir . Ona görə də biz sadəcə olaraq bu indekslərlə elementləri dəyişdiririk. Məsələn, “JavaRush forever” cümləsindəki birinci icrada J və r , ikincisində - a və e , və s. dəyişdiriləcək. Əgər bizdə tək sayda simvol olarsa, onda biz elementə çatdıqda, mətndə olan elementə çatırıq. orta, biz döngədən atılacağıq (yəni orta elementi dəyişdirməyə ehtiyac yoxdur). Düzdürsə, bütün elementləri emal etdikdən sonra atılacağıq. Yaxşı, bundan sonra biz adi bir döngəyə daxil oluruq və massiv elementlərindən bir sətir qururuq.