:-: 6.3 反转字符串 ***** **题干：** 编写一个函数，其作用是将输入的字符串反转过来。 示例 1: ``` 输入: "hello" 输出: "olleh" ``` 示例 2: ``` 输入: "A man, a plan, a canal: Panama" 输出: "amanaP :lanac a ,nalp a ,nam A" ``` **题目分析：** 我们需要反转这个数组大体有五种思路：一是字符串转换为字符数组，倒序后拼接成字符串；二是字符串转换为字符数组，字符数组折半首尾交换字符值，然后直接再转换为字符串；三是使用StringBuilder，StringBuffer的reverse()方法。四是利用栈的后进先出特性，使得字符串反转。五是递归，分而治之。 **新手有可能遇到的解题思路陷阱：** 无 **解题思路分析以及代码实现：** 第一种思路：字符串转字符，倒序拼接。 第一种思路代码： ``` public String reverseString(String s) { char[] reverseString = s.toCharArray(); StringBuilder sb = new StringBuilder(); for (int i = reverseString.length - 1; i >= 0; i--) { sb.append(reverseString[i]); } return sb.toString(); } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：字符串转字符，折半交换。 第二种思路代码： ``` public String reverseString(String s) { int i = 0, j = s.length() - 1; char[] reverseString = s.toCharArray(); while (i < j) { if (reverseString[i] != reverseString[j]) { char temp = reverseString[i]; reverseString[i] = reverseString[j]; reverseString[j] = temp; } i++; j--; } return new String(reverseString); } ``` 第二种思路变种：交换用位操作符 ^=。 第二种思路变种代码： ``` public static String reverseString(String s) { int i = 0, j = s.length() - 1; char[] reverseString = s.toCharArray(); while (i < j) { if (reverseString[i] != reverseString[j]) { reverseString[i] ^= reverseString[j]; reverseString[j] ^= reverseString[i]; reverseString[i] ^= reverseString[j]; } i++; j--; } return new String(reverseString); } ``` **复杂度分析** 时间复杂度：O(logn)。 空间复杂度：O(n)。 第三种思路：换类型，调用原生方法。从源码分析来看，也可以算作是折半来交换，再转换为字符串。 第三种思路代码： ``` public String reverseString(String s) { //return new StringBuffer(s).reverse().toString(); return new StringBuilder(s).reverse().toString(); } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第四种思路：栈的特性，后进先出。 第四种思路代码： ``` public String reverseString(String s) { if (s == null && s.length() == 0) { return s; } Stack<Character> strStack = new Stack<Character>(); char[] reverseString = s.toCharArray(); for (Character ch : reverseString) { strStack.push(ch); } int len = s.length(); for (int i = 0; i < len; i++) { reverseString[i] = strStack.pop(); } return new String(reverseString); } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第五种思路：递归，分而治之。 第五种思路代码： ``` public String reverseString(String s) { int length = s.length(); if (length <= 1) return s; String left = s.substring(0, length / 2); String right = s.substring(length / 2, length); return reverseString(right) + reverseString(left); } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**