מחרוזת הפוכה ב-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 class - charAt (לולאת for, שוב, הפוכה, מה שמאפשר לנו לקחת תווים ברצף לאחור).

4. פתרון עם Stack

אף אחד לא משתמש במחלקה 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 כדי לפצל את המחרוזת למערך ולשים את הכל ב- Stack שלנו עם Character מסוג גנרי . לאחר מכן, אנו מתחילים לקחת אלמנטים מהחלק העליון של הערימה. בשל אופי המחסנית כמבנה LIFO - L ast I n F irst 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 כדי לפצל את המחרוזת הנכנסת לשני חלקים שווים. לאחר מכן, באמצעות הפיצול הזה, אנו מפצלים את המחרוזת לחלקים הקטנים ביותר המתחלקים (תו אחד). לאחר מכן, הרקורסיה מתחילה להתמוטט, ומחזירה את התווים בסדר הפוך (אלה שהיו מימין הוצבו משמאל; אלו שהיו משמאל הונחו מימין)

  אסור לשכוח שכל רקורסיה היא קריאה מרובה לשיטה, וכתוצאה מכך הוצאה לא מבוטלת של משאבים. ובכן, אם אנחנו מדברים על רקורסיה עם תנאי יציאה בלתי ניתנים להשגה, אז זה הנתיב אל האינסוף ואל 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 . אנחנו נכנסים ללולאה שתתנגן כל עוד המדד הגבוה גדול מנמוך . כאן מתחילים לקרות הדברים המהנים - השימוש ב-OR בלעדי. בואו נסתכל על x ו- y כדוגמה . נניח arr[high] = 'x'; הקוד הבינארי שלו יהיה 1 1 1 1 0 0 0 בשלב זה arr[high] = 'n'; קוד בינארי - 1 1 0 1 1 1 0 מה יהיה לנו בפעולות XOR בלולאה:

1. arr[low] = (char) (arr[low] ^ arr[high]);

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

   
   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[high] הוא כמה אלמנטים מסוף המערך כמו arr[low] הוא מההתחלה. לכן, אנחנו פשוט מחליפים את האלמנטים עם המדדים האלה. לדוגמה, בביצוע הראשון במשפט "JavaRush forever" יוחלפו J ו- r , בשני - a ו- e וכו'. אם יש לנו מספר אי זוגי של תווים, אז כשנגיע לאלמנט שנמצא ב- באמצע, נזרק מהלולאה (כלומר אין צורך לשנות את האלמנט האמצעי). אם זה יהיה שווה, נזרק לאחר עיבוד כל האלמנטים. ובכן, אחרי זה אנחנו נכנסים ללולאה רגילה ובונים מחרוזת ממרכיבי המערך.