This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Write a function that reverses the input string. The input string is given in the form of the character array char[].

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

You can assume that all the characters in the array are printable characters in the ASCII code table.

Example 1: input: [" h ", "e", "l", "l", "o"] output: [" o ", "l", "l", "e", "h"] example 2: input: [" h ", "a", "n", "n", "a", "h"] output: [" H"," A "," N "," N "," A ","H"] Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • The most common questions in the string survey are: If they don’t ask us anything else, we can just create an array and iterate backwards.

  • In this case, you can use the two-pointer solution without using extra space.

AC code

public class ReverseString { public static void main(String[] args) { char[] s = new char[]{'h','e','l','l','o'}; new ReverseString().reverseString(s); } public void reverseString(char[] s) { for (int i = 0, j = s.length - 1; i < j; i++, j--) { char temp = s[i]; s[i] = s[j]; s[j] = temp; }}}Copy the code

Submit tests:

AC smoothly!

conclusion

  • The code above uses the beginning and end pointer traversal, and then swaps characters. No extra space is used and the time is O(n/2). More efficient!
  • The head-and-tail double-pointer traversal technique is also often used in sorting arrays. In addition to the head and tail double Pointers, there are fast and slow double Pointers, is also very common skills.
  • This topic is relatively simple, the code is simple, we should memorize, practice more, form muscle memory. Do difficult, complex topics for the future solid foundation.
  • Stick to the daily question, come on!