剣指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は前に移動し、後ろから文字列をコピーし、スペースに遭遇すると対応する文字に直接置き換えます.
方法3:文字列コンストラクタを使用して別のコンテナにコピーする追加のスペースが必要です
試験例: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);
}