【第三轮】6.16-6.22 CareerCup 1.4

具体思路是　先计算出ｓｔｒｉｎｇ中的空格数，　然后从后往前找把空格替换
btw, 这里的　＂ｔｒｕｅ ＂ length 指的是　不包括ｃｈａｒ array 最后的＇\0＇吧？


时间：　Ｏ（ｎ）
空间：　Ｏ（１）
ｇｉｓｔ: https://gist.github.com/daisyang/523e69a4e599a7e96f02

【解题思路】Calculate the new length of the string, then starting from the original end of the array, push each char to the new end. if having space, push "%20" instead.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/e89e058b182a3fe24d88

Solution 1
【解题思路】scan the original string, find the number of space and calculate the new length of string, push new char to the end of the original string to avoid overriding the original string
【时间复杂度】O(n)
【空间复杂度】O(1)
Solution 2
【解题思路】do the same thing excepting allocating new memory for the new string.
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/pchong90/cd2840e67a2d7621171a

【解题思路】
Scan from the end of the string, and replace white space in place with the target chars '%20'

The reason that can't scan from the beginning is the replace chars have larger size then single white space character, the chars following white space will be overwritten by the replace chars.

【时间复杂度】
O(N) for string scanning

【空间复杂度】
O(1) in place replacement

【gist link】
https://gist.github.com/chrislukkk/c65c683e4a51c39f1618

【解题思路】Count the number of chars needed to add and get the new length. One pointer to the old end and one pointer to the new end go back at the same time. Keep moving the char from old string to new string and replacing space until it reaches the start point or there is no space to replace.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/7e89b34c8802f1b947fc

【解题思路】Count space, calculate new length, extend char array length, replace backward
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/xun-gong/999e81b5eb89db67c2e6

【解题思路】遍历数组求得替换后的长度，然后再遍历一次，逐字copy待替换的数组，如果遇到space就替换
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/5de88a5bda58681892c7

本来第一反应是用链表。。。。

【解题思路】
go through all characters in String, replace space with '%20'
【时间复杂度】
O(N)
【空间复杂度】
o(n)
【gist link】https://gist.github.com/tangxukai/34a0bc655a7c4b8ec3dc

【解题思路】
遍历该字符串，判断字符是否为空，若是则替换‘%20’;否则复制该字符
【时间复杂度】
O(N)
【空间复杂度】
o(n)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】
字符串->字符数组，统计空格次数，据此扩容一个新的字符数组，顺次遍历，没有空格，则正常给新数组赋值，一旦出现空格，依次给新数组赋值‘%’，‘2’，‘0’
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/498b511643a44ea36d55.git