【第三轮】6.16-6.22 CareerCup 1.4

【解题思路】
原地改char数组，根据原来字符串的长度和空格的个数。
【时间复杂度】
O(N)
【空间复杂度】
o(1)
【gist link】https://gist.github.com/asdw3276/bcac142e15ec2b9193e1

【解题思路】
I use a two scan approach. In the first scan, I count the number of spaces in the string, with which we can calculate the real length of the string we want. In the second scan, we replace white space with "%20". We need to  start from the end and work backward to avoid overwriting and losing information.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/jyhjuzi/dc69612f9ef6be06b224

【解题思路】
用char[]数组 array，从后往前遍历，遇到第一个不是空格的字符的位置，标记为真实长度（实际上是真实长度-1）。
然后从前往后遍历，每遇到空格，整体向后移动两位，空格替换为"%20"，长度+2；
最后从array中截取真实长度值（此时要加回1）。
【时间复杂度】
O(N)，，，妈蛋不会算。应该是错的，求解答
【空间复杂度】
O(1)
代码地址
https://gist.github.com/guchang/fd3870b62cac0d7d1db4

求解，题目的意思不太明确。
You may assume that the string has sufficient space at the end of the string to hold the additional characters, 这句话 ，还有给的例子：
Input: "Mr John Smith       "
Output: "Mr%20Dohn%20Smith"  
Smith 后面结尾的空格不用转换为％20 了嘛？ 题目中 U may assume那句话什么意思？ 看大家写的 基本都是Smith后面的空格也要转换的吧？

【解题思路】
*Scan first to get the number of spaces. Then iterate from the back to front in the true string, place the characters at the right place
         * O(n) time, O(1) space
         */
【时间复杂度】
O(N)
【空间复杂度】
o(1)
【gist link】https://gist.github.com/XiaoxiaoLi/12fda96630d3ba820042

heycinderella 发表于 2014-6-20 01:24
【解题思路】
Iterate the chars from back to front, move each non-space char to the
         * back, tu ...

求问，为什么测试数据里面最后都加了 \0 ?

zZ-IT 发表于 2014-6-20 01:31
求问，为什么测试数据里面最后都加了 \0 ?

sorry我题意理解错了，不应该有那个。修改后的在这https://gist.github.com/XiaoxiaoLi/12fda96630d3ba820042

【解题思路】convert string to list, go through every character, replace space with'20%'
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/yokiy/01c7f6d7eaa3c855652a

【解题思路】Traverse the string, get the number of space. generate a new char array whose length is the origin length + 2*the number of space, then copy the origin string to the new char array and replace space with "%20".
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/bitcpf/95300d061a63c5e32f86