置換文字列のスペース(C++/Java実装)
1746 ワード
問題の説明:1つの関数を実装して文字列の各スペースを「20%」に置き換えます.例:
入力:「we are happy」
出力:「we%20 are%20 happy」
問題解決の考え方:(C++実現方法)前から後ろに遍歴し、スペースに遭遇して文字を後ろに移動すると、O(n)個のスペースがある時間効率がO(n^2)であると仮定します.したがって、最適化された解法は、一度に所定の位置に移動し、まず文字列を巡回することで、文字列の長さと文字列内のスペースの数を同時に得ることができ、その後、1つのスペースに対して「%20」という3つの文字で置き換えられるので、最終文字列にあるべき長さ、2つのポインタ、1つは最終文字列の末尾、1つは元の文字列の末尾を指すことができます.順番にコピーすると、スペースが置換され、2つのポインタが重なる(つまり同じ位置を指す)と、スペースの置換が完了します.このように時間効率はO(n)である.
(Java実装方法)
入力:「we are happy」
出力:「we%20 are%20 happy」
問題解決の考え方:(C++実現方法)前から後ろに遍歴し、スペースに遭遇して文字を後ろに移動すると、O(n)個のスペースがある時間効率がO(n^2)であると仮定します.したがって、最適化された解法は、一度に所定の位置に移動し、まず文字列を巡回することで、文字列の長さと文字列内のスペースの数を同時に得ることができ、その後、1つのスペースに対して「%20」という3つの文字で置き換えられるので、最終文字列にあるべき長さ、2つのポインタ、1つは最終文字列の末尾、1つは元の文字列の末尾を指すことができます.順番にコピーすると、スペースが置換され、2つのポインタが重なる(つまり同じ位置を指す)と、スペースの置換が完了します.このように時間効率はO(n)である.
void replaceBlank(char string[], int length) {//length
if (string == NULL || length <= 0)
return;
int originalLength = 0;//
int numberOfBlank = 0; //
int i = 0;
while (string[i] != '\0') {
originalLength++;
if (string[i] == ' ')
numberOfBlank++;
i++;
}
int newLength = originalLength + numberOfBlank * 2;//
if (newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while (indexOfOriginal >= 0 && indexOfNew >= indexOfOriginal) {
if (string[indexOfOriginal] == ' ') {
string[indexOfNew--] = '0';
string[indexOfNew--] = '2';
string[indexOfNew--] = '%';
}
else {
string[indexOfNew--] = string[indexOfOriginal];
}
indexOfOriginal--;
}
}
(Java実装方法)
// : Java API replaceAll
public static String replaceSpace(String str) {
String regex = " ";
return str.replaceAll(regex, "%20");
}
// : ,
public static String replaceSpace1(String str){
StringBuilder sb = new StringBuilder(str);
for(int i=0; i<sb.length(); i++){
if(sb.charAt(i) == ' ')
sb.replace(i, i+1, "%20");
}
return sb.toString();
}