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

释放双眼,带上耳机,听听看~!

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

前言

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

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

//输入一个字符串,输出它的倒序字符串
input:  Hello
output: 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==nullstring.length()==0)return string;
        int length = string.length();
        char [] array = string.toCharArray();
        for(int i = 0;i<length;i++){
            array[i] = string.charAt(length-1-i);
        }
        return new String(array);
    }

优化

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

编码实现:

 public static String strReverseWithArray2(String string){
        if(string==nullstring.length()==0)return string;
        int length = string.length();
        char [] array = string.toCharArray();
        for(int i = 0;i<length/2;i++){
            array[i] = string.charAt(length-1-i);
            array[length-1-i] = string.charAt(i);
        }
        return new String(array);
    }
2.使用栈

我们都知道,栈有”后进先出(LIFO)”的特点。这一特点刚好用于反转字符串。

具体思路是:

  • 将字符串转换为char数组
  • 将char数组中的字符依次压入栈中
  • 将栈中的字符依次弹出赋值给char数组

    编码实现

      public static String strReverseWithStack(String string){
        if(string==nullstring.length()==0)return string;
        Stack<Character> stringStack = new Stack<>();
        char [] array = string.toCharArray();
        for(Character c:array){
            stringStack.push(c);
        }
        int length = string.length();
        for(int i= 0;i<length;i++){
            array[i] = stringStack.pop();
        }
        return new String(array);
    }
3.逆序遍历

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

具体思路是:

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

编码实现

public static String strReverseWithReverseLoop(String string){
        if(string==nullstring.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();
    }
4.使用位运算

计算机的数据流本质上都是0,1二进制数据。字符串也是一样。而二进制数据的处理往往是通过位运算来实现的。位操作有:与,或,非,异或

对位运算有过了解的应该知道,使用异或操作能实现交换两个变量的值而不引入第三个变量。

实现原理:

  • 首先介绍异或操作

    异或操作: 当两两数值相同为否,而数值不同为真。写作A^B
    
    A  B  A^B
    0  0   0
    0  1   1
    1  0   1
    0  1   0
    • 使用异或操作交换数值
    两个数异或的结果再与其中一个数异或的结果是另外一个数
    
    这涉及到了离散数学中的异或的性质:
    1.交换律:A^B=B^A
    2.结合律: A^(B^C)=(A^B)^C
    3.恒等律:X^0=0
    4.归零律:X^X=0
    5.自反:A^B^B = A^0=A
    
    根据以上性质:
    
    A=A^B
    B=A^B
    A=A^B
    
    通过以上三步,能实现在程序中交换两个变量的数值的目标。
    • 使用异或操作交换字符值
    before:"Hello"
    after: "olleH"
    
    index: 0   1   2   3   4
    char : H   e   l   l   o
    ASCII: 72  101 108 108 111
    
    以第0个字符和第4个字符交换为例:
    
    交换前:
    array[0]=1001000
    array[4]=1101111
    
    交换:
    array[0]=array[0]^array[4]=0100111
    array[4]=array[4]^array[0]=1001000
    array[0]=array[0]^array[4]=1101111
    
    交换后:
    array[0]=1101111--->111-->o
    array[4]=1001000--->72--->H
    

    编码实现

    public static String strReverseWithXor(String string){
        if(string==nullstring.length()==0)return string;
        char [] array =string.toCharArray();
        int length = string.length()-1;
        for(int i =0;i<length;i++,length--){
            array[i]^=array[length];
            array[length]^=array[i];
            array[i]^=array[length];
        }
        return new String(array);
    }
5.使用递归

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

具体思路是:

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

编码实现

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

【转自慕课】https://www.imooc.com

JAVA

答答租车系统改进版本

2022-3-3 17:15:49

JAVA

正则表达式对象和RegExp对象

2022-3-3 17:16:03

搜索