一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.5

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-15 23:21:03 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 wrj5518 于 2014-6-15 23:21 编辑

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】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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

asdw3276 发表于 2014-6-19 01:58:52 | 显示全部楼层
小柯西 发表于 2014-6-19 01:44
- -我的回复也不光是针对你23楼的讨论的。。
那既然是取平均复杂度。。再回到你这道题的算法,我也不觉 ...

这道题空间复杂度确实不是O(1),这个没错。。。
回复 支持 1 反对 0

使用道具 举报

atlas1017 发表于 2014-6-16 07:02:00 | 显示全部楼层
【解题思路】
先检查是不是长度变短 变短就compress
**没有解决出现超过10的问题呢 回头再看吧= =
【时间复杂度】
N
【空间复杂度】
N
【gist link】
https://gist.github.com/atlas1017/d53c4f08b2a7a942df4e
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-6-16 10:13:20 | 显示全部楼层
【解题思路】
since we may need to return the original string, we cannot destroy it. So, create a new string to store the compression result, and compare their length to decide which string to return.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/77db3602a516a6a1da68
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 13:49:03 | 显示全部楼层
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to build compressed string, length check is done before the final output
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/16b8e16d190c16ceb149
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】user-interaction is included in the code
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 13:52:25 | 显示全部楼层
【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Concatenate character and count to a new string, return it if the length is shorter
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】
  https://gist.github.com/habina/d3eabcba9c86e7855052
【test case】
  "aabcccccaaa "
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 14:34:36 | 显示全部楼层

【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Concatenate character and count to a new string, return it if the length is shorter
【时间复杂度】
  O(N)
【空间复杂度】
  O(N)
【gist link】
https://gist.github.com/gaoyike/188d4e09eb110097b964
【test case】
  "aabcccccaaa "
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 14:36:36 | 显示全部楼层
jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 14:37:29 | 显示全部楼层
jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 14:38:31 | 显示全部楼层
jing0328 发表于 2014-6-16 13:49
【解题思路】use int array of length 256 as a counter for each character and create a stringbuffer to ...

aaaaaaaabbbbbbbbaa

your code : a10b8

should be : a8b8a2
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 14:50:03 | 显示全部楼层
readman 发表于 2014-6-16 14:38
aaaaaaaabbbbbbbbaa

your code : a10b8

哦哦哦 没仔细看题 谢谢指出来啊 我等会改改
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-17 02:49:24 | 显示全部楼层
【解题思路】
遍历原 string 建立新 string,比较二者长度选择返回值
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/fcbfaf6b4100d99918ea
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 09:22:50 | 显示全部楼层
【解题思路】
就是直接做,从前向后遍历。在循环的中间检查一下compressed之后的string是不是比原来的sting长,如果是的话就直接返回原来的string即可。
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_5-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
None
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-17 09:54:23 | 显示全部楼层
【解题思路】Compare current character and its next character, if they are different or encounter the boundary, append it and its count to result. Otherwise increase the count by 1 and move to the next character.
【时间复杂度】O(n) for going through all the characters.
【空间复杂度】O(n) for storing the result string.
【gist link】https://gist.github.com/30d8ea8624913bf7c18f.git
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
input : " ". expect : " ". input : "". expect : "".
input : Null. expect : Null.
input : "a". expect : "a"
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-17 18:03:06 | 显示全部楼层
【解题思路】就是用计数器来计数,最后来比较大小
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/2769ad688dd4ffe386c9
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-17 20:49:30 | 显示全部楼层
【解题思路】遍历一遍字符串,用一个boolean标记是否第一次遇到该字符,第一次遇到append进StringBuilder里,然后计数,直到遇到不同的字符,将统计的次数append进StringBuilder里,重置boolean标记。
【时间复杂度】O(n)
【空间复杂度】StringBuilder可以自动扩容,average O(n)
【gist link】https://gist.github.com/chouclee/b57b6915366b87cdff44
【test case】"aaaaaaaaaaaaaaaaaaaaaaaa" ,"aaaaabbbbb      ","","abc","aaaabbbbc","呵呵呵呵呵呵","呵呵"
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 23:36:58 | 显示全部楼层
小柯西 发表于 2014-6-17 09:54
【解题思路】Compare current character and its next character, if they are different or encounter the ...

谢点评~
我的代码如果是处理全部相同字符的字符串,时间其实还是O(n)。可能我代码比较乱,不好意思~
fill the count那段确实写错了,已经修改。
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 23:37:51 | 显示全部楼层
小柯西 发表于 2014-6-17 09:54
【解题思路】Compare current character and its next character, if they are different or encounter the ...

还有,应该怎么写“点评”啊?点“回复“好像不对的样子。。
回复 支持 反对

使用道具 举报

asdw3276 发表于 2014-6-17 23:48:15 | 显示全部楼层
本帖最后由 asdw3276 于 2014-6-17 23:50 编辑

【解题思路】遍历一遍字符串,用两个char存放当前读取的字符和上一个字符。如果两者相等,计数加1。如果两者不等,写入当前计数到result中,然后将count设为0。然后更新两个char。 最后比较result和原字符串的长度。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/8da1d8560fe3897442d8
【test case】""    " "   "a" "aa" "ab" "aaa"   "aaaaaabbbaaa" "aaaaaabbba"
感谢所有给我code review的小伙伴
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-18 02:51:26 | 显示全部楼层
【解题思路】
compare the current character with the previous one, if equals, cnt++, otherwise, appends the previous char and cnt to the stringbuffer and updates the previous char and cnt. cnt is the occurrence of the same consecutive characters. Once done, compare the length with the original one, if not less than the original one, return the original one.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/7fd763f020e29d9c482d

====================================
【Follow up Question】
Can you decompress the compressed string generated from your code? (In my case: NO), If not, how would you do that? (Thinking......)
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-6-18 11:12:03 | 显示全部楼层

【解题思路】
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/monkerek/b2051b2d48ccbcfe1db2
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-19 02:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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