一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 630|回复: 14
收起左侧

[CareerCup] 【第四轮】3.30-4.5 Career Cup 1.5

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:31:31 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


JamesJi 发表于 2015-3-31 23:28:31 | 显示全部楼层
【解题思路】
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】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-1 03:54:53 | 显示全部楼层
【解题思路】
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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-1 12:18:16 | 显示全部楼层
【解题思路】
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,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-2 15:50:15 | 显示全部楼层
[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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-3 09:29:12 | 显示全部楼层
[solution]
扫一遍string,用一个count记录char出现的次数,用一个last记录之前的char,若相同count++,若不同保存之前的char和count,重置count。
[time]
O(n)
[space]
O(n)
[gist]
https://gist.github.com/chongtianzs/350a1064c730d885078b

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-4 07:37:37 | 显示全部楼层
【解题思路】
/**
* 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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-4 07:37:49 | 显示全部楼层

。。。

本帖最后由 slaink 于 2015-4-4 08:18 编辑

网络太差又双🐔了请帮忙删除谢谢。。。
回复 支持 反对

使用道具 举报

mything 发表于 2015-4-4 13:17:50 | 显示全部楼层
【解题思路】
扫描输入,如果当前字母和之前字母相同,计数加一,否则重置计数器为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" ,

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-5 02:13:29 | 显示全部楼层
【解题思路】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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-4-6 06:58:17 | 显示全部楼层
【解题思路】
* 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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-6 10:57:52 | 显示全部楼层
【解题思路】
扫一遍如果相同count++,如果不同,count重置为1,同时把之前的count append到之前的字符后。

【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/songpu2015617/7b1e335600a5e5986518

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-6 12:34:48 | 显示全部楼层

[solution]
scan the string, use a prev value and a counter to keep track of the repeat of a char, and then update the compressed string accordingly.
[time]
O(n)
[space]
O(n)
[gist]
https://gist.github.com/kelly-us/b1777dc1dc582cf253ad

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

beer 发表于 2015-4-6 21:01:18 | 显示全部楼层
【解题思路】
Tips:
* Use two pointer to make the begin of repeat String snippet and current char, and
* a counter to mark the num of the repeat String snippet
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://github.com/drinkbeer/Cod ... /src/CC150_1_5.java
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 12:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表