【第三轮】6.16-6.22 CareerCup 1.4

【解题思路】
直接用StringBuilder可以解。 或者就是CC书里面的方法，从尾端添加，根据string 长度和space的个数，新的长度为length + space *2.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】https://gist.github.com/UncleGarden/f2bca2305e003bd11944

【解题思路】
给的例子有点奇怪。问题在于：是把每个空格都换成指定字符串？还是在一起的空格换一个？原串尾巴的空格要不要管？
我的程序默认替换每个空格，包括头和尾的空格。
方法：计算替换后所需的字符串长度len，将原来的String convert to char[len];替换每个空格；再将char[]转回String
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】
https://gist.github.com/jaly50/e02d9695ad2316675755
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
The input string is:Come and count how many space I have.  
After replace space with %20, the string is:Come%20and%20count%20how%20many%20space%20I%20have.%20%20

【解题思路】
count spaces; calculate new string length, add null terminator, traverse backwards and replace spaces (in space).
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/b0e0b2525e5e84bd347a.git
【test case】
leading space
tailing space
all spaces
empty string

Output:
Hello World!

%20Hello%20World!%20
%20%20%20



补充内容 (2014-6-29 19:00):
gist link忘记去掉.git了=。= 请手动……

用Java语言实现的基本上90%的人误解了这个题……

1. 题目要求是in place，如果console输入的是String类型，必然不可能in place, 所以函数参数肯定是char[]类型，而不是String
          我们要求的是实现函数，所以可以输入的是string,然后main函数里面使用ReplaceSpace2(inputStr.toCharArray())保证是char[]类型
2. 同样，in place的要求，在函数内，是不可以新建char[]的，必须在原有的char[]上进行更改

guchang 发表于 2014-6-19 12:24
【解题思路】
用char[]数组 array，从后往前遍历，遇到第一个不是空格的字符的位置，标记为真实长度（实际 ...

1. two for loops in your code, which means the Time Complexity maybe O(n^2), actually you can begin for the tail of the char[], which will avoid rewriting.
2. you cannot use another char[] because the Question required in place.

guchang 发表于 2014-6-19 12:24
【解题思路】
用char[]数组 array，从后往前遍历，遇到第一个不是空格的字符的位置，标记为真实长度（实际 ...

Also, it's a huge bug in your code!

the char[] cannot change the length after initial, but in your code, you just use  array[j+2]=array[j];
it will cause ArrayIndexOutOfBoundsException actually.

For example: the input "Mr John Smith" will not pass.

heycinderella 发表于 2014-6-20 01:24
【解题思路】
*Scan first to get the number of spaces. Then iterate from the back to front in the t ...

a bug in your code!

the char[] cannot change the length after initial, but in your code, you just use  array[j+2]=array[j];
it will cause ArrayIndexOutOfBoundsException actually.

For example: the input "Mr John Smith" will not pass.

solution 1
ignore the sentence: please use a character array so that you can perform this operation in place and use string as the input
1. count the number of spaces in the input string except the space at the end of string
2. Create a new char[], calculate the length of the new char[]
3. in the for-loop, replace the spaces into ‘%20′
Time Complexity: O(n)
Space Complexity: O(n)

solution 2
according to the required: use a character array so that you can perform this operation in place, which means the parameter of the method should be char[] rather than String, and cannot use another char[] inside the method. But because the length of the char[] is fixed when initial char[]. So we initial the char[] have enough space to store char. [do it in the void main() method]
1. count the number of spaces in the input string except the space at the end of char[]
2. calculate the new length needed after replace the space with ‘%20′
3. Traverse the char[] from the tail(the new length location rather than the whole char[]) to the front to avoid rewrite
Time Complexity: O(n)
Space Complexity: O(1)


Link is here: http://www.jyuan92.com/post-310

兰橘清檬 发表于 2014-6-17 02:33
【解题思路】
遍历 char 数组计算新数组的长度；
从后往前copy，并将空格改为 %20

请问下，用函数用了void， main如何输出呢？

虽然public void replaceSpace(char[] str, int length) 中的char[]改变了，但是length并不会改变，这样的话在void main函数中输出的话，你怎么知道输出到哪一位？

java是没有结束符的概念的……这样的话是不是只能把system.out.print写到函数里面？？？
或者函数return newLength?

还有种办法是判断\0,读到了\0就结束循环，但是如果字符串里面本身就有\0咋办……

兰橘清檬 发表于 2014-6-17 02:33
【解题思路】
遍历 char 数组计算新数组的长度；
从后往前copy，并将空格改为 %20

for(len = 0; line[len] != '\0'; len++)

不可以这样写……\0不是结束符……

java数组和字符串是没有结束符的，和C/C++不一样