剣指offer面接問題5:スペースの置き換え(Java実装)

1644 ワード

タイトル:文字列のスペースを「%20」に置き換える関数を実装してください.例えば、文字列がWe Are Happyである.置換後の文字列は、We%20 Are%20 Happyである.
試験例:1.機能テスト:入力文字列には、スペース(一番前、真ん中、一番後ろ、連続複数のスペース)2が含まれます.境界テスト:入力した文字列にスペースがありません.3.負のテスト:空のポインタ(空の文字列、1つのスペース文字のみ、複数のスペース文字)を入力します.
方法一:時間複雑度O(n²)
文字列を最初から最後までスキャンし、スペースに遭遇したときに置き換えます.1文字を2文字に置き換えるため、毎回後ろのすべての文字を2文字後ろに移動する必要があります.文字列の長さがnであると仮定すると、各スペースに対して後のO(n)文字を移動する必要があるので、O(n)個のスペースにとって時間の複雑さはO(n)である²)
方法2:時間複雑度O(n)
末尾から文字列をコピーすると、各文字が1回移動するだけなので、時間の複雑さは(n)です.文字列を最初から最後までスキャンし、スペース数を計算し、置換後の文字列の長さをスペース数で計算します.2つのポインタがそれぞれ新旧文字列の末尾を指し、古い文字列の長さを置換後の新しい文字列の長さに拡大し、下付き文字列の境界を越えないように定義します.その後oldindexは前に移動し、後ろから文字列をコピーし、スペースに遭遇すると対応する文字に直接置き換えます.
public class test_five {
		public String replaceSpace(StringBuffer str){
			if(str == null)return null;
			
			int length = str.length();
			
			// , 
			int spacenumber = 0;
			for(int i=0;i=0 && oldindex

方法3:文字列コンストラクタを使用して別のコンテナにコピーする追加のスペースが必要です
public String replaceSpace(StringBuffer str) {
        if (str == null)
            return null;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            if (String.valueOf(str.charAt(i)).equals(" ")) {
                sb.append("%20");
            }else {
                sb.append(str.charAt(i));
            }
        }
        return String.valueOf(sb);
    }