【第三轮】6.16-6.22 CareerCup 1.5

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

是的。如果原字符串有数字就无法还原了，那如果没有数字呢

【解题思路】
         * Go through each character in the input string, compare it with the
         * previous one, count the frequency.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/XiaoxiaoLi/fa251f9f537c536a74ba

解题思路：　从左到右遍历ｓｔｒｉｎｇ,然后数之后相同字符的个数，放到新string里面去，下次检验过的字符的下一个开始．

时间：　O(n)　时间复杂度是n吧？　虽然有两个循环但是不检验重复的　
空间：Ｏ（n）
gist: https://gist.github.com/daisyang/c986085ccf159e1f8187

求帮忙检验对不对

serolins 发表于 2014-6-20 09:23
不需要用两次scan吧，一次就够了的。

对的～～　谢谢哈～～改了

【解题思路】
Scan through the whole string and compress, it will stop either:
1. the compress string exceed the length of original string, in which we return original one
2. finish compression and return result

【时间复杂度】
O(N) for scanning through string

【空间复杂度】
O(N) for saving the compression result

PS: There seems to be a way to do in place compression, since we can use some special character to indicate the 'gap' created by compression, and reversing back the original string if we need to return that.

【gist link】
https://gist.github.com/chrislukkk/d6a1827124ac7d47534c

【解题思路】
遍历原来string，如果后一个字符和前一个字符相同，count++，如果不相同，前一个字符写到新string里，count=1。 最后比较两个string长度
【时间复杂度】
   O(n)
【空间复杂度】
不知道要怎么算？
【gist link】https://gist.github.com/yokiy/8dcfbd745317c5c9b46e

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

我看大家都是compress完了最后一步比较length大小，像书里这样先扫一遍最后结果的length也要多出个O（N），如果是用StringBuffer的话，真的能减少时间么？求解谢谢！

heycinderella 发表于 2014-6-20 23:42
我看大家都是compress完了最后一步比较length大小，像书里这样先扫一遍最后结果的length也要多出个O（N） ...

StringBuffer和String的区别, 请看http://www.programcreek.com/2014 ... -vs-by-constructor/