楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
wendychueng 2014-6-22 14:08:08 | 只看该作者
全局:

【解题思路】
Create a result string, if the previous char equals to the current char, count +1, when meet a different char, store the previous one and its count to the reuslt
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/yupingzhang/1659e49f3cc5318ed7ce
回复

使用道具 举报

🔗
jason51122 2014-6-22 14:19:09 | 只看该作者
全局:
【解题思路】First calculate the new length for compressed string. If it is larger than old length, return old string. Then create a new char array with new length. Traverse string from the beginning again to fill in all chars.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/15970f1b868f49a756a8
回复

使用道具 举报

🔗
jaly50 2014-6-23 20:07:36 | 只看该作者
全局:
【解题思路】
从左向右数每个字符连续出现的个数,然后output.concat(s[i]).concat(count(s[i])
如果output.length>input.length,那么return input, else return output
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】
  https://gist.github.com/jaly50/e8a78495c0282315cf8a
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
  /**
* test case 1:
*    The input string is:Helloooooooooo,  Julllllieeeeeeeeeeeeeeeeeeeeeeeeeeeeeee!!!!!!!!!!!!!!!!!!!!!!!!
*     After compressed, the string is:H1e1l2o10,1 2J1u1l5i1e31!24
* test case 2:
*    The input string is:Helloo,  Julllllie!
*     After compressed, the string is:Helloo,  Julllllie!
* */

点评

给你code review啦~最近在忙毕业和签证的事,晚了点,sorry啦  发表于 2014-6-24 21:22
回复

使用道具 举报

🔗
ivycheung1208 2014-6-24 08:38:15 | 只看该作者
全局:
本帖最后由 ivycheung1208 于 2014-6-23 20:25 编辑

【解题思路】
scan the string, count the current repeating character, when meet a different character, concatenate the previous character and it's count to the output string. After traversing, compare the original string and the "compressed" one, return whichever is shorter.
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/171ee49f1d204b4e643c
【test case】
null -> null
aas -> aas
aaas -> aaas
aaaas -> a4s1
aaaasd -> aaaasd
aaaaaaaaaassaa -> a10s2a2
...
Q: 题目说可以assume只有大小写字母,这条信息有什么优化的可能么?

看了些前面关于decompression的讨论,发现这条假设在这个情境下就可以避免问题啦,要恢复应该也没什么问题了

另外,看起来StringBuffer是Jave才有的问题,C++里string是mutable的,和Java里的StringBuffer几乎是一样的效果,嗷……






回复

使用道具 举报

🔗
ivycheung1208 2014-6-24 09:08:25 | 只看该作者
全局:
wilbert 发表于 2014-6-18 18:44
我举个例子吧, a1和111个a都能compress出a111,我们现成的这种算法是无法还原的。

所以题目里说assume都是letter耶…这样就没有这个问题啦!
回复

使用道具 举报

🔗
sanguine 2014-6-25 20:53:13 | 只看该作者
全局:
atlas1017 发表于 2014-6-16 07:02
【解题思路】
先检查是不是长度变短 变短就compress
**没有解决出现超过10的问题呢 回头再看吧= =

It's wrong……

the string aabcccccaaa would become a2blc5a3

not a5b1c5
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
sanguine 2014-6-25 21:21:21 | 只看该作者
全局:
林微熙 发表于 2014-6-19 06:07
【解题思路】
  Save the first character. Iterate and compare next character, increment count
  Con ...

不懂==为什么mydogismaotou输出的是m1y1d1o1g1i1s1m1a1o1t1o1u1

得到的m1y1d1o1g1i1s1m1a1o1t1o1u1长度大于mydogismaotou,不应该输出原来的字符串即mydogismaotou吗?
回复

使用道具 举报

🔗
sanguine 2014-6-25 21:29:01 | 只看该作者
全局:
readman 发表于 2014-6-16 14:34
【解题思路】
  Save the first character. Iterate and compare next character, increment count
  C ...

很好奇为什么做成这个样子?写成2个函数,为什么先计算count?

我是直接把input compress,然后比较两个字符串长度的大小,输出对应的字符串

你的方法哪里优化了呢?
回复

使用道具 举报

🔗
readman 2014-6-25 21:33:44 | 只看该作者
全局:
sanguine 发表于 2014-6-25 21:29
很好奇为什么做成这个样子?写成2个函数,为什么先计算count?

我是直接把input compress,然后比较两 ...

input : abc;
output: a1b1c1;

The purpose of compression is to reduce the length of string, which in this case, is not
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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