【第三轮】6.16-6.22 CareerCup 1.4

【解题思路】
1. With additional memory cost, use stringbuffer.
2. Inplace, needs to do more 'char shift'. Every time it encounters a space, move chars followed backward. Always keep tack of the current 'tail'
【时间复杂度】
O(N)
【空间复杂度】
1. O(N) 2.O(1)
【gist link】
https://github.com/FinalF/CarrerUp/blob/master/spaceReplace.java

sanguine 发表于 2014-6-25 16:10
a bug in your code!

the char[] cannot change the length after initial, but in your code, you ju ...

是这样的，不过题里说You may assume that the string has sufficient space at the end of the string to hold the additional characters，所以放后面是没关系的不会out of bound

heycinderella 发表于 2014-6-25 23:24
是这样的，不过题里说You may assume that the string has sufficient space at the end of the string t ...

都没去翻书==看来还是有必要多翻翻书啊==


就这个纠结了这么久原来书上已经假定好了%>_<%

sanguine 发表于 2014-6-25 23:28
都没去翻书==看来还是有必要多翻翻书啊==

哈哈有时候是会这样，题得仔细看呀

sanguine 发表于 2014-6-25 16:04
1. two for loops in your code, which means the Time Complexity maybe O(n^2), actually you can begi ...

1.谢谢指正，其实我更乐意用链表来实现这道题。。。。。
2.那个output可以省略，不知道当时为何保留下来了。。。已删除。

sanguine 发表于 2014-6-25 03:38
for(len = 0; line[len] != '\0'; len++)

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

谢谢提醒啦

sanguine 发表于 2014-6-25 03:25
请问下，用函数用了void， main如何输出呢？

虽然public void replaceSpace(char[] str, int length)  ...

输出的话可以用 System.out.print() 吧，当遇到 '\0' 时终止输出；因为原题目有考虑 cpp 的情况，所以我理解是原字符串中不会出现 '\0'，'\0' 只作为终止符出现。

另外多谢提醒 java 中没有 终止符的概念。因为题目要求说 if implementing in Java, please use a character array so that you can perform this operation in place，所以我就用了 char[] 而不是 String

兰橘清檬 发表于 2014-6-26 13:39
输出的话可以用 System.out.print() 吧，当遇到 '\0' 时终止输出；因为原题目有考虑 cpp 的情况，所以我 ...

恩，题目肯定是用char[]作为参数的，这个题估计目的也就是实现函数==main函数好像只能用\0来判断输出，毕竟没有终止符

Java其实本来就不推荐这样做的orz……

sanguine 发表于 2014-6-25 22:55
恩，题目肯定是用char[]作为参数的，这个题估计目的也就是实现函数==main函数好像只能用\0来判断输出，毕 ...

对呀～可能为了 cpp 和 java 都能写所以这样出题吧

【解题思路】
把所有的string转化为char，碰到空格就转化为'%20'（感谢沙发给予的启发）
【时间复杂度】
O(N)
【空间复杂度】
o(1)（谁能告诉我什么事空间复杂度？）
【gist link】
老规矩无gist，贴代码
public class Stringtest{
        public static void main(String[] args){
                String t = "da ben dan     ";
                char[] result = new char[t.length()];
                int k = t.length()-1;
                while(t.charAt(k)== ' ')
                        k--;
                int j = 0;
                for(int i = 0; i<=k;i++){
                        if(t.charAt(i)!=' '){
                                result[j] = t.charAt(i);
                                j++;
                        }
                        else{
                                result[j] = '%';
                                result[j+1] = '2';
                                result[j+2] = '0';
                                j +=3;
                        }
                }
                System.out.println();
                for(int m = 0; m<=j; m++)
                        System.out.print(result[m]);
        }
}