【第三轮】6.16-6.22 CareerCup 1.4

donnice 发表于 2014-6-29 05:35
【解题思路】
把所有的string转化为char，碰到空格就转化为'%20'（感谢沙发给予的启发）
【时间复杂度】
...

public class Stringtest{
        public static void main(String[] args){
                String t = "da ben dan sha bi a";
                int p = 0;
                for(int n = 0; n<t.length();n++){
                        if(t.charAt(n) == ' ')
                                p++;
                }
                int k = t.length()+2*p+1;
                char[] result = new char[k];
                int j = 0;
                for(int i = 0; i<t.length();i++){
                        if(t.charAt(i)!=' '){
                                result[j] = t.charAt(i);
                                j++;
                        }
                        else{
                                result[j] = '%';
                                result[j+1] = '2';
                                result[j+2] = '0';
                                j =j+3;
                        }
                }
                for(int m = 0; m<=j; m++)
                        System.out.print(result[m]);
        }
}
楼上有些错误，不好意思……

【解题思路】
use C++ STL
traverse the original string and replace spaces
with "%20" directly
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/JoshuaTang/b496371d59d78975a919

【解题思路】First count the number of blanks to get the final length of the string, then use to pointer from end, one is original end and one is final end, to assign value of the first pointer to the second one, when encounter a blank, just replace it with "%20". This problem can be classified as a pointer problem.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/dbd99efe90b525b4c381.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
(' a     ', 2)
(' a     ', 2)
('  a            ', 5)
('a  b  c             ', 7)
('      ', 1)

【解题思路】
compute the new length of the string (use %20 instead of spaces);
start traversal from the end of the string;
copy characters from its old position to the new position, replace spaces with %20 when copying

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/6116286529243aade71a