【第四轮】3.30-4.5 Career Cup 1.5

1.5 Implement a method to perform basic string compression using the counts
of repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】
扫描输入，如果当前字母和之前字母相同，计数加一，否则重置计数器为1，之前字母设为当前字母
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link]
https://gist.github.com/n2iw/630917d5b1087c128380
【test case】(optional，如果觉得比较好，欢迎贴出来分享）
                null <=  null ,
                "" <=  "" ,
                "a" <=  "a" ,
                "aa" <=  "aa" ,
                "ab" <=  "ab" ,
                "abc" <=  "abc" ,
                "aaaabc" <=  "aaaabc" ,
                "a4b2c1" <=  "aaaabbc" ,
                "a5b1c1" <=  "aaaaabc" ,
                "a5b1c2" <=  "aaaaabcc" ,

【解题思路】First thing is to see whether the compressed string will be larger than the original string. If so, return the original string. If not, traverse the string and count the unique characters and their frequency. concatenate them into anew string.
【时间复杂度】O(n+k^2) n is the length og the original string, k is the number of unique characters in the original string
【空间复杂度】O(k)
【gist link] https://github.com/StephenWeiXu/ ... blob/master/1_5.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）
https://github.com/StephenWeiXu/ ... blob/master/1_5.cpp

【解题思路】
* When we want to add something to a string constantly and without knowing the total length,
* StringBuilder is a good choice.
* We check whether the adjacent elements are same. if so, we increase count number; if not, we output the count number,
* new character and reset the count number to 1.
* Please be aware that at the end, we cannot detect the different adjacent elements, but we still need to add the count number.

【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/leonw007/ef69b87b8ec03c1a7d08
【test case】included in the above link

【解题思路】
Use StringBuffer, first change the original string to CharArray[], then scan the whole array. New a res to store result. If there is a same, count ++, then append it to StringBuffer
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/f218761e65c2da766ef2

【test case】

【解题思路】
Brute force
* go through the String  to  count the repeat sequence and   put   char+count to new string
* compare the length of new string and  original string to decide which one  is returned
*
【时间复杂度】
O(n)
after read the book  solution find  this
"because string concatenation operates in 0(n^2)"
* so it is o(n^2)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/f154e37453aa1d7ebd91

【解题思路】
use one iteration and a pre variable to compare the adjacent char
use a counter to record the same letter occurrence
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link]
python solution
https://gist.github.com/zhangjiang2013/acda7c7faf6726f4e5a5
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

[solution]
process from left to right, count the number of adjacent chars and create the compressed string
[time]
O(n)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/08722d22d49b05ef1ede

[solution]
扫一遍string，用一个count记录char出现的次数，用一个last记录之前的char，若相同count++，若不同保存之前的char和count，重置count。
[time]
O(n)
[space]
O(n)
[gist]
https://gist.github.com/chongtianzs/350a1064c730d885078b

【解题思路】
建立一个和原数组长度相同的新数组，然后遍历原数组里的值并按照题目规则插值给新数组，同时更新新数组index，每次插值前检查数组index是否即将溢出，如果溢出返回原数组。
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... mpresssamechar-java

【解题思路】
/**
* Compress a string.
*
* Traverse through this string, if reach a character
* that is differ from its previous character, store
* previous character and its count, and put that new
* character into buffer, set counter to 1.
*/
【时间复杂度】  * Time complexity: O(n)
【空间复杂度】  * Space complexity: O(n)
【gist link] https://github.com/bxshi/intervi ... unt_compression.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）https://github.com/bxshi/intervi ... c/test/1_5_test.cpp

网络太差又双🐔了请帮忙删除谢谢。。。