深入浅出经典面试题之——反转字符串

前言

如今无论大小公司，都喜欢出一些算法题来测试面试者的算法功底或者说是计算机功底。而如今Android和Java把很多方法都封装成API了，导致我们写代码往往只是调调API，没有深入了解过一些功能的底层算法实现。因此，研究算法一是能在面试中正确快速的解决算法题，而是能提高我们的编程功底，更好地编写出高效稳健的代码。

今天，我们研究的是——反转字符串。

//输入一个字符串，输出它的倒序字符串，注意不能使用系统提供的APIinput:  Hellooutput: olleH

几种解法

string:  Hello  length:  5            0 1 2 3 4 before: H e l l o after: o l l e H index sum 0: H--->o 0-->4 4 1: e--->l 1-->3 4 2: l--->l 2-->2 4 ... 分析字符串反转前后的规律可知: 两个反转字符串字符的下标之和为字符串长度-1.

1.使用数组

最常规的解法，也是我们在面试的时候最容易想到的一种方法。

具体思路是:

* 将字符串转换为char数组* 遍历循环给char数组赋值

编码实现：

public static String strReverseWithArray(String string){        if(string==null||string.length()==0)return string;        int length = string.length();        char [] array = string.toCharArray();        for(int i = 0;i

优化：

分析上一种解法，循环遍历时，我们不需要循环这么多次。每次循环的时候，我们应该直接给前、后位置都赋值。

编码实现:

public static String strReverseWithArray2(String string){        if(string==null||string.length()==0)return string;        int length = string.length();        char [] array = string.toCharArray();        for(int i = 0;i

2、逆序遍历

仔细观察会发现，反转字符串实际上是逆序输出字符串中的字符。

具体思路是:

• 逆序遍历字符串中的字符，并将它依次添加到StringBuilder中

编码实现：

public static String strReverseWithReverseLoop(String string){        if(string==null||string.length()==0)return string;        StringBuilder sb = new StringBuilder();        for(int i = string.length()-1;i>=0;i--){            sb.append(string.charAt(i));        }        return sb.toString();    }

3.使用递归

当我们反转字符串的时候，脑海里想的就是从首尾两端依次交换直到到达中间位置。当我们在反转某个字符时，剩下的字符串也是一个反转字符串的过程。这样，我们就能用递归的方法来实现反转字符串的目的。

具体思路是:

• 找出递归结束的临界条件
• 对针对于临界条件的不同的值做出不同的处理

编码实现：

public static String strReverseWithRecursive(String string){        if(string==null||string.length()==0)return string;        int length = string.length();        if(length==1){            return string;        }else{            return  strReverseWithRecursive(string.substring(1))+string.charAt(0);        }    }