【第三轮】6.16-6.22 CareerCup 1.5

【解题思路】
Create a result string, if the previous char equals to the current char, count +1, when meet a different char, store the previous one and its count to the reuslt
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/yupingzhang/1659e49f3cc5318ed7ce

【解题思路】First calculate the new length for compressed string. If it is larger than old length, return old string. Then create a new char array with new length. Traverse string from the beginning again to fill in all chars.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/15970f1b868f49a756a8

【解题思路】
从左向右数每个字符连续出现的个数，然后output.concat(s[i]).concat(count(s[i])
如果output.length>input.length,那么return input, else return output
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】
  https://gist.github.com/jaly50/e8a78495c0282315cf8a
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
  /**
* test case 1:
*    The input string is:Helloooooooooo,  Julllllieeeeeeeeeeeeeeeeeeeeeeeeeeeeeee!!!!!!!!!!!!!!!!!!!!!!!!
*     After compressed, the string is:H1e1l2o10,1 2J1u1l5i1e31!24
* test case 2:
*    The input string is:Helloo,  Julllllie!
*     After compressed, the string is:Helloo,  Julllllie!
* */

【解题思路】
scan the string, count the current repeating character, when meet a different character, concatenate the previous character and it's count to the output string. After traversing, compare the original string and the "compressed" one, return whichever is shorter.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/171ee49f1d204b4e643c
【test case】
null -> null
aas -> aas
aaas -> aaas
aaaas -> a4s1
aaaasd -> aaaasd
aaaaaaaaaassaa -> a10s2a2
...
Q: 题目说可以assume只有大小写字母，这条信息有什么优化的可能么？

看了些前面关于decompression的讨论，发现这条假设在这个情境下就可以避免问题啦，要恢复应该也没什么问题了

另外，看起来StringBuffer是Jave才有的问题，C++里string是mutable的，和Java里的StringBuffer几乎是一样的效果，嗷……

wilbert 发表于 2014-6-18 18:44
我举个例子吧， a1和111个a都能compress出a111，我们现成的这种算法是无法还原的。

所以题目里说assume都是letter耶…这样就没有这个问题啦！

atlas1017 发表于 2014-6-16 07:02
【解题思路】
先检查是不是长度变短 变短就compress
＊＊没有解决出现超过10的问题呢 回头再看吧= =

It's wrong……

the string aabcccccaaa would become a2blc5a3

not a5b1c5

林微熙 发表于 2014-6-19 06:07
【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Con ...

不懂==为什么mydogismaotou输出的是m1y1d1o1g1i1s1m1a1o1t1o1u1

得到的m1y1d1o1g1i1s1m1a1o1t1o1u1长度大于mydogismaotou，不应该输出原来的字符串即mydogismaotou吗？

readman 发表于 2014-6-16 14:34
【解题思路】
  Save the first character. Iterate and compare next character, increment count
  C ...

很好奇为什么做成这个样子？写成2个函数，为什么先计算count?

我是直接把input compress，然后比较两个字符串长度的大小，输出对应的字符串

你的方法哪里优化了呢？

sanguine 发表于 2014-6-25 21:29
很好奇为什么做成这个样子？写成2个函数，为什么先计算count?

我是直接把input compress，然后比较两 ...

input : abc;
output: a1b1c1;

The purpose of compression is to reduce the length of string, which in this case, is not