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 F irst Out (биринчи кирген, акыркы чыккан), элементтер артка кабыл алынат жана натыйжа пайда болгон катарда сакталат.

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' дейли ; Анын экorк codeу 1 1 1 1 0 0 0 болот Бул учурда arr[жогорку] = 'n'; Бинардык code - 1 1 0 1 1 1 0 Циклдеги XOR операцияларында бизде эмне болот:

1. arr[төмөн] = (чар) (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[жогорку] = (чар) (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[төмөн] = (чар) (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[low] башынан эле ошончолук. Ошондуктан, биз жөн гана элементтерди бул индекстер менен алмаштырабыз. Мисалы, "JavaRush түбөлүккө" сүйлөмүндөгү биринчи аткарууда J жана r алмаштырылат, экинчисинде - a жана e , ж.б. орто, биз циклден ыргытылат (б.а. орто элементти өзгөртүүнүн кереги жок). Эгерде ал тең болсо, биз бардык элементтерди иштеткенден кийин ыргытабыз. Андан кийин биз кадимки циклге кирип, массивдин элементтеринен сап курабыз.