【第三轮】6.16-6.22 CareerCup 1.5

readman 发表于 2014-6-20 23:51
StringBuffer和String的区别, 请看http://www.programcreek.com/2014/03/create-java-string-by-double-q ...

这个博客好赞！！

【解题思路】
Go through the string and calculate how many duplicates each char has, it larger than 2, the string needs compressing.
Then go through the string again and for each char, count duplicates of each char, push the char and the count into the StringBuilder.
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】https://gist.github.com/nealhu/f633212a765f31388f5b

【解题思路】遍历字符串，创建一个新的字符串保存压缩后的字符串，然后比较长度，然后返回
【时间复杂度】O（n）
【空间复杂度】O（n）
【gist link】https://gist.github.com/weazord/aa1aaac89d066a798b7e

【解题思路】Start from index 0 ,compare every 2 characters, if they are the same, count the number, else, append the char in another String, and add the count to the string, then clear the count. At the end, get the length of the new string, return the short one.
【时间复杂度】O（n）
【空间复杂度】O（n）
【gist link】https://gist.github.com/bitcpf/f8a3615255a8808bddc6

【解题思路】
traverse the string directly and count #characters. Then check whether the result is smaller than input string.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】https://gist.github.com/tangxukai/38980fda9d5fca54a44d

【解题思路】
遍历该字符串，统计连续相同字符，将字符和统计数写入字符串。
【时间复杂度】
O(n + k^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】遍历一遍字符串，定义一个char类型的temp，存放上一个读取的字符。定义一个count，定义temp的累计数。temp起始值为字符串的第一个字符，count初始化为1.若当前字符与temp一样，则count++，若不一样，则输出temp+count字符串，temp重设为当前字符，count初始为1.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/guchang/3cdb48dfd26a185330f8
【test case】
null  output:null
""    output:""
" " output:" "
"a"  output:"a"
"aa"  output:"aa"
"ab" output:"ab"
"呵呵呵呵呵哈哈哈哈bbbbaaa"  output:"呵5哈4b4a3"
"aaaaabcde"  output:"aaaaabcde"

【解题思路】
         从前往后，两两判断是否相同，
         * 1).相同，计数器增加1（初始值始终为1），继续向后判断；
         * 2).直到前后不等，则将当前位置对应字符和计数器值顺次存入buf缓冲区
         * 3).当i指向倒数第二个数时，为最后一次比较，若相同，则加1，若不同，将当前值直接输入buf，跳出循环
         * 4).这时，最后一个字符的比较信息还没有存入buf,因此在for循环外再存一次。
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/a8d87a8ba456d872bcb9.git

【test case】
aaabbbbb aac---->a3b5 1a2c1; aaabbaac---->aaabbaac

【解题思路】: 写了两种实现方式：纯 C-string 的操作，也支持"aaaaaaaaaaaab"和普通"aaaabbccd"的 test case
                                               利用C++ string object, 主要是 concatenate 直接用 ‘+’ 就行了，比较简洁和大家用java写的思路是一样的
                    之前一直对c-string 和 c++ string object不熟悉，导致这一章的一些题老是去用char array 操作，容易出错，代码也不简洁。 做到第五题才开窍。
【时间复杂度】
                     O(n)
【空间复杂度】
                     O(n)
【gist link】    看str_compress2(), 比较简洁！
                     https://gist.github.com/xun-gong/295dbd999829a0fc7aba

【解题思路】
Create StringBuilder, compare and count, add into string, in the end, compare the length, then return.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/UncleGarden/6ea4bdb039d7f0b1fd0a