【第三轮】6.16-6.22 CareerCup 1.4

【解题思路】
1. 首先遍历一遍字符串，数出空格的个数。如果字符串后面留的空间刚好就是转换后所需要的空间的话，这一步可以省略；
2. 如果第一步没有省略，则找到转换后的字符串最后一个字符所应该在的位置。方法也很简单，那就是原来只有一个字符的空格现在需要3个字符的空间，转换一下即可。如果第一步省略了，则字符转换后，最后一个字符的位置就是整个字符串（包括留白）的最后一个位置。
3. 从后向前遍历字符串，如果是非空格，直接就放在正确的位置；如果是空格，则转换成'%20'。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_4-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
None

小柯西 发表于 2014-6-17 02:30
为什么会想到用recursion来做这道题！

最近在看算法设计....

habina 发表于 2014-6-16 13:16
【解题思路】
  Split the whole string by space, save each word in an array.
  Concatenate and put  ...

I think your space complexity should be O(n)

ryancooper 发表于 2014-6-17 11:36
I think your space complexity should be O(n)

Thanks for pointing that out.
I think my code does not satisfy for performing operation in place.
I'll rewrite it.
Thanks again.

habina 发表于 2014-6-17 11:57
Thanks for pointing that out.
I think my code does not satisfy for performing operation in place. ...

That's fineActually, maybe you should use another language to write this if you want to do it in place since object string in python is immutable

ryancooper 发表于 2014-6-17 12:05
That's fineActually, maybe you should use another language to write this if you want to do ...

Yeah. I totally agree about that. I'll do it in c.

【解题思路】
先把index变成最后一个不是空格，然后就是替换。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qiangusc/def553c9b31b44560818

【解题思路】traverse字符串s，统计空格的数量c，new 一个s.length() + c<<1 大小的char[]，再次traverse，重组字符串
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/d111abfd1ff20e41cd01

【解题思路】
Original string must ends with '\0'. Count the number of spaces to get the length of the new string. Then start from the end of the new string and original string, if meets space in the original string, replace it with "%20", otherwise just move the character.
【时间复杂度】
O(N)
【空间复杂度】
O(1), in-place replace, no additional place
【gist link】
https://gist.github.com/iwilbert/d0efe909f1311c081bc2

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