رشته معکوس در جاوا: آموزش معکوس کردن رشته ها به روش های مختلف

آیا می توان بدون دانستن الگوریتم ها به یک برنامه نویس خوب تبدیل شد؟ خیلی خیلی بحث برانگیز بله، می‌توانید در شرکت‌های برون‌سپاری ما شغل پیدا کنید، زیرا در طول مصاحبه، بیشتر در مورد فناوری سؤال می‌پرسند. اما اگر تصمیمات شما پر از عصا باشد، آیا متخصص خوبی خواهید بود؟ اگر می‌خواهید به یک شرکت خارجی جدی‌تر بروید، با مصاحبه‌هایی مواجه می‌شوید که عمدتاً بر روی الگوریتم‌ها متمرکز هستند. به هر حال، ارزش دارد که از ابتدایی ترین الگوریتم ها استفاده کنید، زیرا یک الگوریتم دوست برنامه نویس است . امروز به یکی از این موضوعات می پردازیم و راه های معکوس کردن یک رشته را مورد بحث قرار می دهیم. اینجا همه چیز ساده است. معکوس کردن یک رشته به معنای عقب بردن رشته است. به عنوان مثال: JavaRush forever ->reverof hsuRavaJ بنابراین، چگونه می توانید یک رشته را در جاوا معکوس کنید؟

1. StringBuilder/StringBuffer

رایج ترین و ساده ترین راه استفاده از StringBuilder/StringBuffer است :

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

بهترین راه حل = ساده ترین. وقتی از شما پرسیده شد که چگونه یک رشته را در جاوا معکوس کنیم، این اولین چیزی است که باید به ذهن متبادر شود. اما ما قبلاً در مورد الگوریتم ها صحبت کردیم، اینطور نیست؟ بیایید نگاهی به راه حل هایی بیاندازیم که خارج از جعبه نیستند.

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 نوع عمومی در Stack خود قرار می دهیم . بعد، شروع به گرفتن عناصر از بالای پشته می کنیم. با توجه به ماهیت پشته به عنوان یک ساختار 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 برای تقسیم رشته ورودی به دو قسمت مساوی استفاده می کنیم. در مرحله بعد، با استفاده از این تقسیم، رشته را به کوچکترین قسمت های قابل تقسیم (1 کاراکتر) تقسیم می کنیم. پس از آن، بازگشت شروع به فروپاشی می کند و شخصیت ها را به ترتیب مخالف برمی گرداند (کسانی که در سمت راست بودند در سمت چپ قرار گرفتند؛ آن هایی که در سمت چپ بودند در سمت راست قرار گرفتند)

  ما نباید فراموش کنیم که هر بازگشتی یک فراخوانی چندگانه به یک متد است و در نتیجه هزینه قابل توجهی از منابع دارد. خوب، اگر ما در مورد بازگشت با شرایط خروج دست نیافتنی صحبت می کنیم، پس این مسیر به بی نهایت و به StackOverflowError است.

• روش دو

  در اینجا به یک آرگومان اضافی در متد - index نیاز داریم.

  هنگامی که این متد اجرا می شود، طول رشته ای 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[کم] ^ 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[high] = (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[low] = (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[high] به همان تعداد عنصر از انتهای آرایه است که arr[low] از ابتدا. بنابراین، ما به سادگی عناصر را با این شاخص ها تعویض می کنیم. به عنوان مثال، در اجرای اول در جمله "JavaRush forever" J و r با هم تعویض می شوند، در مورد دوم - a و e و غیره. اگر تعداد کاراکتر فرد داشته باشیم، وقتی به عنصری که در وسط، از حلقه به بیرون پرتاب خواهیم شد (یعنی نیازی به تغییر عنصر میانی نیست). اگر یکنواخت باشد، پس از پردازش همه عناصر، ما را بیرون می‌اندازند. خوب، پس از آن وارد یک حلقه معمولی می شویم و یک رشته از عناصر آرایه می سازیم.