Go语言视频零基础入门到精通

javalearner

java的各种变量中，开发用的最多的是字符串，字符串的相关操作比较重要。有关字符串的算法题也较多，IT笔试面试中对字符串是肯定会有所考察的。
下面来说一下前段时间看到的字符串反转操作相关算法题，题中有些问题值得深思，对此给出了自己的看法.

1. 1. StringBulider 实现
   
2. public String reverse(String str) {
   
3.   if((null== str) || (str.length()  <=1)) {
   
4.       return str;
   
5.   }
   
6.   StringBuilder result =new StringBuilder(str);
   
7.    for(int i =0; i < (str.length() /2); i++) {
   
8.       int swapIndex = str.length() -1- i;
   
9.       char swap = result.charAt(swapIndex);
   
10.       result.setCharAt(swapIndex, result.charAt(i));
    
11.       result.setCharAt(i, swap);
    
12.    }
    
13.     return result.toString();
    
14. }

复制代码

  
   
   

     
   

     
   
  
2. char数组实现

1. public String reverse(String str) {
   
2.   if((null== str) || (str.length() <=1)) {
   
3.      return str;
   
4.    }
   
5.     char[] chars = str.toCharArray();
   
6.     int right = chars.length -1;
   
7.     for(int left =0; left < right; left++) {
   
8.        Char swap = chars[left];
   
9.        chars[left] = chars[right];
   
10.        chars[right--] = swap;
    
11.     }
    
12.       return new String(chars);
    
13.   }

复制代码

3. SringBuffer方法
  public String reverse(String str) {
   if((null== str) || (str.length() <=1)) {
    return str;
   }
   StringBuffer reverse =new StringBuffer(str.length());
    for(int i = str.length() -1; i >=0; i--) {
     reverse.append(str.charAt(i));
   }
   return reverse.toString();
}

4.用相关接口来实现
//<StringBuffer 实现了此接口>
public interface Reverser {
        public String reverse(String str);
    }   /*
   Java中，最好的实现就是用JDK中StringBuffer的反转方法，它不仅速度快， 效率高，而且还知道如何处理unicode代理对 (surrogate pairs)。 其实现方法实际上是实现了Reverse接口的。
  */
  public class JdkReverser implements Reverser {
   public String reverse(String str) {
     if((null== str) || (str.length() <=1)) {
      Return str;
    }
     return new StringBuffer(str).reverse().toString();
    }
   }  5.递归（Recursion) 实现
  public String reverse(String str) {
    if((null== str) || (str.length() <=1)) {
     return str;
   }
    return reverse(str.substring(1)) + str.charAt(0);
  } 实际上见得最多的应该就是3，4，5了。毕竟这三个可以从效率，以及概念等方面去考察，也能反映出一个人的基础是否扎实。

6.在此提出几个关于递归的问题。
① 递归方案的效率？
② 什么叫尾(Tail)递归？


简单分析：
①. 递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。相比于递归来说，迭代只需要进行n次迭代，递归的效率是比较低的。需要注意的是迭代并不适合所有的场合。

②. 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。
     当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。
尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

     尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。
尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题――因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。
传统递归越深，距离目标越近；尾递归越深，距离起点越远。

下面给出尾递归的一种实现:
   public class TestTailReverse {
     public static void main(String[] args) {
      String string = "Stephan";
      int len = string.length();
     System.out.println(reverse(string, "",len));
    }
    public static String reverse(String str, String des,int len) {
    des = des + str.charAt(str.length() - 1);
    return len == 1 ? des : reverse(str.substring(0, len - 1), des,--len);
  }
}
   
  

  
  
   
   

     
   

     
   
  

复制代码