Leetcodeブラシノート-『剣指Offer』面接問題05-スペースの置き換え

スペースの置換
文字列sの各スペースを「%20」に置き換える関数を実装してください.
 
例1:
入力:s="We are happy."出力:「We%20 are%20 happy.」 
制限:
0<=sの長さ<=10000
 
私の考え:
find関数を使用して文字列内のスペースの位置を見つけ、replace関数を使用してスペースを「20%」に置き換えます.
C++コードは以下の通りです.

class Solution {
public:
    string replaceSpace(string s) {
        while(s.find(" ")<s.size()){
            s.replace(s.find(" "),1,"%20");
        }
        return s;
    }
};

 
その他の参考資料:
文字配列は,1文字から3文字に置換するたびに,文字配列を用いて容易に置換できる.文字配列の長さsの長さの3倍を確立し、これにより、文字配列が置換されたすべての文字を収容できることを保証することができる.
sを取得する長さlengthは、length*3初期化sizeが0である文字配列arrayを作成し、sizeは置換後の文字列の長さが左から右に文字列sを遍歴してsを取得する現在の文字cが文字cがスペースである場合、array[size]='%',array[size+1]='2',array[size+2]='0',sizeの値を3文字cがスペースでない場合、array[size]=cとし、sizeの値を1遍歴した後、sizeの値は置換後の文字列の長さに等しく、arrayの前のsize文字から新しい文字列を作成し、新しい文字列を返します.
複雑性解析

時間複雑度:O(n).文字列sを繰り返します.

空間複雑度:O(n).sの長さの3倍の文字配列を追加します.

 
解題構想2:PythonやJavaなどの言語では、文字列は可変のタイプに設計されています.つまり、文字列のある文字を直接修正することはできません.新しい文字列実装が必要です.
Python解法の流れ:
listを初期化しresと記す.リストsの各文字cを巡回する:cがスペースの場合:resの後に文字列「%20」を追加する;cがスペースでない場合:resの後に文字cを追加します.リストresを文字列に変換して返します.
Java解法プロセス:
StringBuilderをresとして初期化します.文字列sの各文字cを巡回する:cがスペースの場合:resの後に文字列「%20」を追加する;cがスペースでない場合:resの後に文字cを追加します.resをStringタイプに変換して返します.複雑度分析:時間複雑度O(N):O(N)を遍歴し、各ラウンドに文字操作を追加(修正)してO(1)を使用する.空間複雑度O(N):Pythonが新しく作成したlistとJavaが新しく作成したStringBuilderは、線形サイズの余分な空間を使用しています.