《剑指offer》Java版代码全集：https://github.com/wuping5719/Algorithm/tree/master/1-Sword-Offer
本题来自《剑指offer 名企面试官精讲典型编程题》面试题4。
题目4：请实现一个函数，把字符串中的每个空格替换成"%20"。例如：输入"hello world."，则输出"hello%20world."。
在网络编程中，如果URL参数中含有特殊字符，如空格，'#'等，可能导致服务端无法获得正确的参数值。我们需要将特殊符号转换为服务器可以识别的字符。转换规则为在'%'后面跟上ASCII码的两位十六进制。空格可以被替换为"%20"，'#'可以被替换为"%23"。
时间复杂度为O(n)的解法：
可以先遍历一次字符串，统计出字符串中的空格总数，并由此计算出替换之后的字符串总长度。每替换一个空格，长度增加2。替换后的字符串长度等于原来的长度加上空格数乘以2。
准备两个指针P1，P2从后往前开始复制替换。P1指向原字符串末尾，P2指向替换之后的字符串末尾。接下来我们向前移动指针P1，逐步将它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格后，P1向前移动一格，P2之前插入"%20"，同时把P2向前移动3格。当P1和P2指向同一个位置，表明所有空格替换完毕。
以下为操作示意图：
注：图中阴影区域表示被移动的字符。
我以Java为编程语言实现上述思想：
1 package array; 2 3 /** 4 * @author WuPing 5 * @version 2016年4月8日 上午11:05:59 6 */ 7 8 public class ReplaceBlank { 9 10 public static void replaceBlank(char strings[], int length) { 11 // length为字符数组string的总容量 12 if (strings != null && length > 0) { 13 int originalLength = 0; // 字符数组实际长度 14 int numberOfBlank = 0; // 字符数组中的空格数 15 int i = 0; 16 while (strings[i] != ' ') { 17 ++originalLength; 18 19 if (strings[i] == ' ') 20 ++numberOfBlank; 21 22 ++i; 23 } 24 25 // newLength为把空格替换成'%20'之后的长度 26 int newLength = originalLength + numberOfBlank * 2; 27 if (newLength > length) 28 return; 29 30 int indexOfOriginal = originalLength; // 字符数组起始扫描索引 31 int indexOfNew = newLength; // 替换空格后的字符数组起始扫描索引 32 while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) { 33 // 从后向前扫描，遇到空格则替换成'%20'，否则直接复制字符 34 if (strings[indexOfOriginal] == ' ') { 35 strings[indexOfNew--] = '0'; 36 strings[indexOfNew--] = '2'; 37 strings[indexOfNew--] = '%'; 38 } else { 39 strings[indexOfNew--] = strings[indexOfOriginal]; 40 } 41 42 --indexOfOriginal; 43 } 44 } 45 } 46 47 //空格在字符串中间 48 public static void Test1(int length) { 49 char[] test1Strings = new char[length]; 50 test1Strings[0] = 'h'; 51 test1Strings[1] = 'e'; 52 test1Strings[2] = 'l'; 53 test1Strings[3] = 'l'; 54 test1Strings[4] = 'o'; 55 test1Strings[5] = ' '; 56 test1Strings[6] = 'w'; 57 test1Strings[7] = 'o'; 58 test1Strings[8] = 'r'; 59 test1Strings[9] = 'l'; 60 test1Strings[10] = 'd'; 61 test1Strings[11] = ' '; // 模拟字符串结束符 62 63 System.out.println("Test1 begin: "); 64 System.out.print("替换空格前的字符数组："); 65 for (int i = 0; i < test1Strings.length; i++) { 66 if (test1Strings[i] == ' ') { 67 break; 68 } 69 System.out.print(test1Strings[i]); 70 } 71 System.out.println(); 72 73 replaceBlank(test1Strings, length); 74 75 System.out.print("替换空格后的字符数组："); 76 for (int i = 0; i < test1Strings.length; i++) { 77 if (test1Strings[i] == ' ') { 78 break; 79 } 80 System.out.print(test1Strings[i]); 81 } 82 System.out.println(); 83 } 84 85 //空格在字符串开头 86 public static void Test2(int length) { 87 char[] test2Strings = new char[length]; 88 test2Strings[0] = ' '; 89 test2Strings[1] = 'h'; 90 test2Strings[2] = 'e'; 91 test2Strings[3] = 'l'; 92 test2Strings[4] = 'l'; 93 test2Strings[5] = 'o'; 94 test2Strings[6] = 'w'; 95 test2Strings[7] = 'o'; 96 test2Strings[8] = 'r'; 97 test2Strings[9] = 'l'; 98 test2Strings[10] = 'd'; 99 test2Strings[11] = ' '; // 模拟字符串结束符 100 101 System.out.println("Test2 begin: "); 102 System.out.print("替换空格前的字符数组："); 103 for (int i = 0; i < test2Strings.length; i++) { 104 if (test2Strings[i] == ' ') { 105 break; 106 } 107 System.out.print(test2Strings[i]); 108 } 109 System.out.println(); 110 111 replaceBlank(test2Strings, length); 112 113 System.out.print("替换空格后的字符数组："); 114 for (int i = 0; i < test2Strings.length; i++) { 115 if (test2Strings[i] == ' ') { 116 break; 117 } 118 System.out.print(test2Strings[i]); 119 } 120 System.out.println(); 121 } 122 123 //空格在字符串末尾 124 public static void Test3(int length) { 125 char[] test3Strings = new char[length]; 126 test3Strings[0] = 'h'; 127 test3Strings[1] = 'e'; 128 test3Strings[2] = 'l'; 129 test3Strings[3] = 'l'; 130 test3Strings[4] = 'o'; 131 test3Strings[5] = 'w'; 132 test3Strings[6] = 'o'; 133 test3Strings[7] = 'r'; 134 test3Strings[8] = 'l'; 135 test3Strings[9] = 'd'; 136 test3Strings[10] = ' '; 137 test3Strings[11] = ' '; // 模拟字符串结束符 138 139 System.out.println("Test3 begin: "); 140 System.out.print("替换空格前的字符数组："); 141 for (int i = 0; i < test3Strings.length; i++) { 142 if (test3Strings[i] == ' ') { 143 break; 144 } 145 System.out.print(test3Strings[i]); 146 } 147 System.out.println(); 148 149 replaceBlank(test3Strings, length); 150 151 System.out.print("替换空格后的字符数组："); 152 for (int i = 0; i < test3Strings.length; i++) { 153 if (test3Strings[i] == ' ') { 154 break; 155 } 156 System.out.print(test3Strings[i]); 157 } 158 System.out.println(); 159 } 160 161 //字符串中有连续两个空格 162 public static void Test4(int length) { 163 char[] test4Strings = new char[length]; 164 test4Strings[0] = 'h'; 165 test4Strings[1] = 'e'; 166 test4Strings[2] = 'l'; 167 test4Strings[3] = 'l'; 168 test4Strings[4] = 'o'; 169 test4Strings[5] = ' '; 170 test4Strings[6] = ' '; 171 test4Strings[7] = 'w'; 172 test4Strings[8] = 'o'; 173 test4Strings[9] = 'r'; 174 test4Strings[10] = 'l'; 175 test4Strings[11] = 'd'; 176 test4Strings[12] = ' '; // 模拟字符串结束符 177 178 System.out.println("Test4 begin: "); 179 System.out.print("替换空格前的字符数组："); 180 for (int i = 0; i < test4Strings.length; i++) { 181 if (test4Strings[i] == ' ') { 182 break; 183 } 184 System.out.print(test4Strings[i]); 185 } 186 System.out.println(); 187 188 replaceBlank(test4Strings, length); 189 190 System.out.print("替换空格后的字符数组："); 191 for (int i = 0; i < test4Strings.length; i++) { 192 if (test4Strings[i] == ' ') { 193 break; 194 } 195 System.out.print(test4Strings[i]); 196 } 197 System.out.println(); 198 } 199 200 //字符数组为null 201 public static void Test5() { 202 System.out.print("Test5 begin: "); 203 replaceBlank(null, 0); 204 System.out.println("passed!"); 205 } 206 207 //字符串为空串 208 public static void Test6(int length) { 209 char[] test6Strings = new char[length]; 210 test6Strings[0] = ' '; // 模拟字符串结束符 211 212 System.out.println("Test6 begin: "); 213 System.out.print("替换空格前的字符数组："); 214 for (int i = 0; i < test6Strings.length; i++) { 215 if (test6Strings[i] == ' ') { 216 break; 217 } 218 System.out.print(test6Strings[i]); 219 } 220 System.out.println(); 221 222 replaceBlank(test6Strings, length); 223 224 System.out.print("替换空格后的字符数组："); 225 for (int i = 0; i < test6Strings.length; i++) { 226 if (test6Strings[i] == ' ') { 227 break; 228 } 229 System.out.print(test6Strings[i]); 230 } 231 System.out.println(); 232 } 233 234 //字符串为一个空格 235 public static void Test7(int length) { 236 char[] test7Strings = new char[length]; 237 test7Strings[0] = ' '; 238 test7Strings[1] = ' '; // 模拟字符串结束符 239 240 System.out.println("Test7 begin: "); 241 System.out.print("替换空格前的字符数组："); 242 for (int i = 0; i < test7Strings.length; i++) { 243 if (test7Strings[i] == ' ') { 244 break; 245 } 246 System.out.print(test7Strings[i]); 247 } 248 System.out.println(); 249 250 replaceBlank(test7Strings, length); 251 252 System.out.print("替换空格后的字符数组："); 253 for (int i = 0; i < test7Strings.length; i++) { 254 if (test7Strings[i] == ' ') { 255 break; 256 } 257 System.out.print(test7Strings[i]); 258 } 259 System.out.println(); 260 } 261 262 //字符串中没有空格 263 public static void Test8(int length) { 264 char[] test8Strings = new char[length]; 265 test8Strings[0] = 'h'; 266 test8Strings[1] = 'e'; 267 test8Strings[2] = 'l'; 268 test8Strings[3] = 'l'; 269 test8Strings[4] = 'o'; 270 test8Strings[5] = 'w'; 271 test8Strings[6] = 'o'; 272 test8Strings[7] = 'r'; 273 test8Strings[8] = 'l'; 274 test8Strings[9] = 'd'; 275 test8Strings[10] = ' '; // 模拟字符串结束符 276 277 System.out.println("Test8 begin: "); 278 System.out.print("替换空格前的字符数组："); 279 for (int i = 0; i < test8Strings.length; i++) { 280 if (test8Strings[i] == ' ') { 281 break; 282 } 283 System.out.print(test8Strings[i]); 284 } 285 System.out.println(); 286 287 replaceBlank(test8Strings, length); 288 289 System.out.print("替换空格后的字符数组："); 290 for (int i = 0; i < test8Strings.length; i++) { 291 if (test8Strings[i] == ' ') { 292 break; 293 } 294 System.out.print(test8Strings[i]); 295 } 296 System.out.println(); 297 } 298 299 //字符串中全是空格 300 public static void Test9(int length) { 301 char[] test9Strings = new char[length]; 302 test9Strings[0] = ' '; 303 test9Strings[1] = ' '; 304 test9Strings[2] = ' '; 305 test9Strings[3] = ' '; 306 test9Strings[4] = ' '; // 模拟字符串结束符 307 308 System.out.println("Test9 begin: "); 309 System.out.print("替换空格前的字符数组："); 310 for (int i = 0; i < test9Strings.length; i++) { 311 if (test9Strings[i] == ' ') { 312 break; 313 } 314 System.out.print(test9Strings[i]); 315 } 316 System.out.println(); 317 318 replaceBlank(test9Strings, length); 319 320 System.out.print("替换空格后的字符数组："); 321 for (int i = 0; i < test9Strings.length; i++) { 322 if (test9Strings[i] == ' ') { 323 break; 324 } 325 System.out.print(test9Strings[i]); 326 } 327 System.out.println(); 328 } 329 330 public static void main(String[] args) { 331 int length = 100; 332 Test1(length); 333 Test2(length); 334 Test3(length); 335 Test4(length); 336 Test5(); 337 Test6(length); 338 Test7(length); 339 Test8(length); 340 Test9(length); 341 } 342 343 }
程序运行结果如下图：
