【第三轮】6.16-6.22 CareerCup 1.5

readman 发表于 2014-6-25 21:33
input : abc;
output: a1b1c1;

没懂==我的输出结果也是abc，而不是a1b1c1啊……

我是先压缩，得到a1b1c1,然后判断a1b1c1长度大于abc，所以返回了abc

你这种方法先计算长度如果大于或等于的话直接返回结果，确实减少了很多操作，也不需要开辟新的O(n)的空间，但是同时，如果长度小于原字符串的话，不仅重新开辟了O(n)的空间，又重新traverse了一遍，这样复杂度虽然还是线性，但是不就变成2n了？

sanguine 发表于 2014-6-25 21:44
没懂==我的输出结果也是abc，而不是a1b1c1啊……

我是先压缩，得到a1b1c1,然后判断a1b1c1长度大于abc ...

- = 良好的代码习惯是必要的.
题目明确写出要先检验是不是长于原始数据....

jaly50 发表于 2014-6-23 20:07
【解题思路】
从左向右数每个字符连续出现的个数，然后output.concat(s).concat(count(s)
如果output.len ...

Don't use String, using StringBuffer or StringBuilder instead!

if you use string,the time complexity will be O(n^2), because every time you update the character in the string, it will create a new string instead of modify on the original one

below is the open source code of concat() method:

1.   public String concat(String str) {       
   
2. int otherLen = str.length();       
   
3. if (otherLen == 0) {            
   
4. return this;
   
5.         }
   
6.         char buf[] = new char[count + otherLen];
   
7.         getChars(0, count, buf, 0);
   
8.         str.getChars(0, otherLen, buf, count);
   
9.         return new String(0, count + otherLen, buf);
   
10.     }

复制代码

【解题思路】
Use a string buffer to construct the compressed string. iterate the original string, if current char is the same as the previous one, increase the counter; otherwise, append previous char and its counter, reset current char and counter. Finally, compare the length of constructed string with the original one
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://github.com/FinalF/Carrer ... ingCompression.java

【解题思路】
Use a string buffer to construct the compressed string. iterate the original string, if current char is the same as the previous one, increase the counter; otherwise, append previous char and its counter, reset current char and counter. Finally, compare the length of constructed string with the original one
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://github.com/FinalF/Carrer ... ingCompression.java

solution 1
Traverse each character in the string, compare the current char with the previous one, if equals, count++, otherwise, appends the previous char and count into the StringBuilder
[count: the occurrence of the same consecutive characters]
Time Complexity: O(n)
Space Complexity: O(n)
Tip: Here, we must use StringBuilder or StringBuffer rather than String. Because the String is immutable, every time we add a character into the string, it will create a new String and eventually the Time Complexity will be O(n^2)

solution 2
The same idea with the first solution
Improve: Instead check the length at the end, in this method, Scan first to count the length of the Compress String, if the length is large than the original, return original. In this way, do not need extra O(n) space to build the Compress String. Otherwise, more O(n) time needed to build Compress String, and the time Complexity will be O(2n)
Instead of using the StringBuilder, we use char[] to implements this method.
Time Complexity: O(n)
Space Complexity: O(1) or O(n)

The Code Link: http://www.jyuan92.com/post-316

sanguine 发表于 2014-6-25 06:44
没懂==我的输出结果也是abc，而不是a1b1c1啊……

我是先压缩，得到a1b1c1,然后判断a1b1c1长度大于abc ...

我好像两个都输出了
我回去研究一下

sanguine 发表于 2014-6-25 20:53
It's wrong……

the string aabcccccaaa would become a2blc5a3

Thx for advice but I ran the case you provided and the output was correct : )

【解题思路】
traverse the string and count duplicate characters
and put corresponding result into a new string
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/f5f92df4db35ca55fa6b

【解题思路】This problem is still a pointer problem, use two pointer to record the start position and end position of a sequence of same characters, then append the character to the new string, as well as the number.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】
https://gist.github.com/5448908bb0831ef19c8b.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
"";
"a";
"aa";
"aabb";
"aaabbbcc";