『剣指offer』Java学習録:文字列(面接問題4:スペースを置換)

23743 ワード
面接試験
文書ディレクトリ
  • 文字列
  • Stringの重要特性
  • StringBuilderの重要特性
  • StringBufferとStringBuilderの違い
  • StringBuilder&StringBufferの拡張ロジック
  • String、StringBuilder、StringBufferの違い
  • 試験問題4:スペース置換
  • タイトル
  • 分析
  • 解:java
    • 文字列
    文字列は、使用頻度が高いため、各言語で特殊な処理が行われているため、いくつかの文字からなるシーケンスです.
    CC++の文字列は、'0'文字で終わる配列です.Javaの文字列は、文字配列を含むクラスを指す.String.
    Javaでは、Stringの他に文字列に関するクラスがStringBufferおよびStringBuilderあります.String・StringBufferとStringBuilderの応用と区別を明らかにすることは、Javaベースの習得にとって非常に重要であり、面接でも問題が発生することが多い.
    Stringの重要な特性
  • Stringオブジェクトの主な役割は文字列の作成、検索、比較などの基礎操作である.
  • Stringの下位データ構造は固定長の文字配列(char [])このクラスの基本操作は、配列の下付きindex関連する検索操作、例えばindexOf系列関数である.このクラスの特徴は、可変ではなく、任意の継ぎ目、切り取り、追加、置換などの修正操作によって、新しいStringオブジェクトが誕生し、頻繁にオブジェクトが作成され、効率が低下することである.
  • コードでは、"hello"の文字列に類似しており、いずれもStringオブジェクトを表しており、通常は字面量としても扱われている.new String()スタックメモリに保存されており、仮想マシンの定数プールに保存されている.変数:String str = "hello";を明示すると、プログラムはまず定数プールに存在するかどうかを確認します"hello"オブジェクトがある場合は、そのオブジェクトの参照を直接str変数に割り当てます.この場合、オブジェクトは作成されません.定数プールに"hello"オブジェクトが見つからない場合、"hello"オブジェクトが作成され、定数プールに保存され、参照がstr変数に割り当てられます.この点が重要で、以前は面接でよく考察されていました.

    • StringBuilderの重要な機能
  • ・String対象注目文字列の基礎操作が異なるStringBuffer・StringBuilderと同様に、主に注目文字列がつなぎ合わせられている.なぜStringはすでに接合操作を実現しているのか、専門的に設計StringBuilder接合の仕事をしているのか.Stringオブジェクトの修正操作は、新しいオブジェクトの作成につながることを覚えています.プログラムでは、文字列の結合作業をループで実行することがよくあります.これはシステムリソースに大きな負担をもたらします.StringBuilderはこの問題を解決します.
  • StringBuilder継承したAbstractStringBuilder、AbstractStringBuilderの下位データ構造も配列であり、一定の拡張機構により配列容量を変更する(新たにより大きな配列を作成する).
    • StringBufferとStringBuilderの違い
    単独で説明しなかったのはStringBufferあまりにも似ているため、APIが類似しているだけでなく(機能が類似していることを意味する)、同じく継承しているAbstractStringBuilderこのクラスは主要な機能を実現し、同様に動的配列を維持している.
    違いは次のとおりです.
  • StringBufferスレッドが安全で効率が低い
  • StringBuilderスレッドが安全ではなく、効率が高い
    • スレッドが安全かどうかは、すべて1つsynchronizedキーワードの使用にあります.StringBufferの関数申明には、いずれもsynchronizedキーワードがありますがStringBuilderはありません.コードの違いを見てみましょう.StringBufferのappend関数:
    @Override
public synchronized StringBuffer append(Object obj) {
    toStringCache = null;
    super.append(String.valueOf(obj));
    return this;
}
    StringBuilderのappend関数:
    @Override
public StringBuilder append(Object obj) {
    return append(String.valueOf(obj));
}

    StringBuilder&StringBufferの拡張ロジックStringBuilderおよびStringBufferともに継承AbstractStringBuilder、拡張ロジックも同様AbstractStringBuilderクラスで定義される.
    まず、拡張コードを見てください.
    char[] value; //        。
int count; //        ，        。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public AbstractStringBuilder append(String str) {
    if (str == null)
    return appendNull();
    int len = str.length();
    ensureCapacityInternal(count + len); //   value      ，      。
    str.getChars(0, len, value, count);
    count += len;
    return this;
}
private void ensureCapacityInternal(int minimumCapacity) {
    //   minimumCapacity                        。
    // overflow-conscious code
    if (minimumCapacity - value.length > 0) { //               ，  if   
        value = Arrays.copyOf(value, newCapacity(minimumCapacity)); //      ，
    }
}
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int newCapacity = (value.length << 1) + 2; //       ，       2 +2。
    if (newCapacity - minCapacity < 0) { //              ，            
        newCapacity = minCapacity;
    }
    return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0)
        ? hugeCapacity(minCapacity)
        : newCapacity;
}
private int hugeCapacity(int minCapacity) {
    if (Integer.MAX_VALUE - minCapacity < 0) { // overflow
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE) ? minCapacity : MAX_ARRAY_SIZE;
}

    全体の論理はまだ簡単です.整理すると次のようになります.
  • AbstractStringBuilder毎回append文字列の場合に呼び出されるensureCapacityInternal新旧文字列を格納するのに十分な容量を確保する.
  • 古い文字列の長さと新しい文字列の長さの和は最小容量とみなされ、最小容量が現在の配列数より大きい場合は拡張が必要となる.
  • 拡張された新しい配列の容量は元の配列の容量の2倍+2(新容量)であり、新容量が最小容量より小さい場合は、新容量の値を最小容量に置き換える.通常これが新配列の容量である.
  • 例外として、新容量が整数の最大値よりも大きいと、メモリオーバーフロー異常が放出されます.MAX_ARRAY_SIZEとInteger.MAX_VALUEの間であれば、新容量の値は最小容量となる.

    • String、StringBuilder、StringBufferの違い
  • データ構造上、Stringは配列を使用し、StringBuilderとStringBufferは動的配列を使用する.
  • 使用上:Stringは主に文字列のクエリー操作に用いられ、StringBuilderとStringBufferは文字列の追加、削除、変更に用いられる.
  • 効率上:Stringの増加、削除、変更操作によりオブジェクトが作成され、StringBuilderとStringBufferは必ずしも作成されないため、前者は後者より低い.またStringBuilderはStringBufferに比べて同期を使用しており、StringBuilderよりも効率が低い.

    • 違いの主な原因は前にはっきり言ったが,ここでは繰り返さない.Stringに関する面接問題を見てみましょう.
    面接問題4:スペースの置換
    タイトル
    文字列の各スペースを「%20」に置き換える関数を実装してください.例えば「We are happy.」と入力し、「We%20 are%20 happy.」と出力します.
    背景:ネットワークプログラミングで、URLパラメータにスペース、#などの特殊文字が含まれている場合、サーバが正しくないか、正しいパラメータがない可能性があります.これらの特殊な文字をサーバが認識できる文字に変換する必要があります.変換ルールは、"%"の後にASCIIコードに続く2桁の16進数表現である.例えば、スペースのASCIIコードは32、すなわち16進数の0 x 20である.したがって、スペースは%20に置き換える必要があります.
    ぶんせき
    Javaを使って言語を開発するパートナーは、この問題がこんなに簡単だと思っているに違いない.Stringクラスのreplace関数を呼び出せば実現できる.はい、そう言えば間違いありません.しかし、実はこの問題はC/C++言語設計の面接問題です.Javaの場合、この問題の文字列は文字配列に変更する必要があります.
    1つのスペースを%20に置き換える必要があるので、1回のスペースを置き換えると2が増えます.必要に応じて、元の文字配列空間が十分かどうかを考慮する必要があります.スペースが足りない場合は、文字配列を再作成し、元の配列の文字を一度コピーする必要があります.最適化されたスペースはありません.ここでは文字配列を再作成する場合は考慮しません.
    元の配列空間が十分であると仮定すると、2つの実装方法があります.
  • 前から後へ配列を遍歴し、スペースに遭遇すると格納する%20後のすべての関数を2に後退させる.文字列長がnであると仮定すると、各スペース文字について、後のO n O_を移動する必要がある{n}On文字なので、O n O_を含む{n}On個のスペース文字列の合計時間効率はO n 2 O_である{n^2} On2​.これはOfferを手に入れることができるものではありません.
  • 時間的複雑度がO n O_{n}Onの解法は,1つのスペースを置換するごとに実長が2つ増えるため,最終配列の実長は実長=原配列実長+スペース数∗2実長=原配列実長+スペース数*2実長=原配列実長+スペース数∗2であるため,まず配列を遍歴する必要がある.元の配列の実際の長さ元の配列の実際の長さ元の配列の実際の長さ値と、配列内のスペース数のスペース数を求めて、置換後の実際の長さを計算します.そして後から配列を巡り、2つのポインタを提供し、p1・p2p1元の文字列の末尾を指し、p2置換後の文字列の末尾を指す.次に前へ移動するp1ポインタは、その指す文字をp2指す位置に割り当て、同時にp2前へ1マス移動する.スペースを当てた後、p11マス前に移動し、p2前に文字列%20%203マス前に移動します.最終p1とp2は同じ位置を指し、置き換えが完了します.解析的には,移動を必要とするすべての文字が1回しか移動しないため,このアルゴリズムの時間的複雑さはO n O_である.前より速いです.後でこの考え方でアルゴリズムを実現する.

    • 解:java
    public class Main {
    public static void main(String args[]) {
        //  0  ，         。
        char[] str = {'w', 'e', ' ', 'a', 'r', 'e', ' ', 'h', 'a', 'p', 'p', 'y',
            0, 0, 0, 0};
        int rawLength = 0; //       
        int emptyBlanks = 0; //     
        for (char cha : str) { //   ，                  
            if (cha == 0) {
                break;
            }
            rawLength++;
            if (cha == ' ') {
                emptyBlanks++;
            }
        }
        System.out.println(new String(str));
        int p1 = rawLength - 1; //  1       0    
        //                         ， 1       0    
        int p2 = rawLength + 2 * emptyBlanks - 1;
        while (p1 != p2 && p1 >= 0 && p2 >= 0) {
            if (str[p1] != ' ') {
                str[p2] = str[p1];
                p1--;
                p2--;
            } else {
                p1--;
                str[p2--] = '0';
                str[p2--] = '2';
                str[p2--] = '%';
            }
        }
        System.out.println(new String(str));
    }
}

    実行結果:
    we are happy
we%20are%20happy

    解:C++
    C++のコードはJavaコードとほぼ一致しています.
    int main() {
    char str[16] = {'w', 'e', ' ', 'a', 'r', 'e', ' ', 'h', 'a', 'p', 'p', 'y'};
    int rawLength = 0; //       
    int emptyBlanks = 0; //     
    for (char cha : str) { //   ，                  
        if (cha == 0) {
            break;
        }
        rawLength++;
        if (cha == ' ') {
            emptyBlanks++;
        }
    }
    cout << str << endl;
    int p1 = rawLength - 1; //  1       0    
    //                         ， 1       0    
    int p2 = rawLength + 2 * emptyBlanks - 1;
    while (p1 != p2 && p1 >= 0 && p2 >= 0) {
        if (str[p1] != ' ') {
            str[p2] = str[p1];
            p1--;
            p2--;
        } else {
            p1--;
            str[p2--] = '0';
            str[p2--] = '2';
            str[p2--] = '%';
        }
    }
    cout << str << endl;
    return 0;
}

    実行結果:
    we are happy
we%20are%20happy
    Linux環境でSSH制限
    Spring 3操作clob問題