古典的な面接問題を深く説明する——反転文字列

古典的な面接問題を深く説明する——反転文字列
前言
今では、大小の会社にかかわらず、面接者のアルゴリズムの基礎、あるいはコンピュータの基礎をテストするアルゴリズムの問題が好きです.現在、AndroidとJavaは多くの方法をAPIにカプセル化しており、コードを書くのはAPIを調整するだけで、いくつかの機能の下位アルゴリズムの実現を深く理解していないことが多い.そのため、アルゴリズムを研究する1つは、面接でアルゴリズムの問題を正確かつ迅速に解決することができるのではなく、私たちのプログラミングの基礎を高め、効率的で安定したコードをよりよく書くことができます.
今日、私たちが研究しているのは、文字列を反転することです.

//       ，         ，           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==null||string.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==null||string.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==null||string.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==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();
    }

4.ビット演算の使用
コンピュータのデータストリームは本質的に0,1バイナリデータである.文字列も同じです.バイナリデータの処理は往々にしてビット演算によって実現される.ビット操作には、、、または、非、異またはがあります.
ビット演算についてよく知られていることは、第3の変数を導入することなく、異種または操作を使用して2つの変数を交換する値を実現できることである.
実現原理:

まず、異種または動作

について説明する.

     :          ，       。  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==null||string.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==null||string.length()==0)return string;
        int length = string.length();
        if(length==1){
            return string;
        }else{
            return  strReverseWithRecursive(string.substring(1))+string.charAt(0);
        }
    }