由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求STRING COMPRESSION一题C++解法(CC150 1.5)
相关主题
相关话题的讨论汇总
话题: char话题: prunner话题: pkeeper话题: p0话题: int
进入JobHunting版参与讨论
1 (共1页)
u*****o
发帖数: 1224
1
很经典的一题,
Compress a given string "aabbbccc" to "a2b3c3"
constraint: inplace compression, no extra space to be used
CC150的答案是JAVA的。。而且我觉得那个方法挺麻烦的,在网上搜了半天,似乎
AMAZON, GOOGLE都出过这题啊,很希望牛牛们能给个C++的解法,关键是
abcd 我的CODE RETURN a1b1c1d1啊。。还有如果COUNT>10,也不行。。反正各种弱。。。
k*******t
发帖数: 144
2
CC给的答案时间和空间都是O(n). 你确实是inplace compression么?

。。

【在 u*****o 的大作中提到】
: 很经典的一题,
: Compress a given string "aabbbccc" to "a2b3c3"
: constraint: inplace compression, no extra space to be used
: CC150的答案是JAVA的。。而且我觉得那个方法挺麻烦的,在网上搜了半天,似乎
: AMAZON, GOOGLE都出过这题啊,很希望牛牛们能给个C++的解法,关键是
: abcd 我的CODE RETURN a1b1c1d1啊。。还有如果COUNT>10,也不行。。反正各种弱。。。

s******o
发帖数: 78
3
你确认这货可以inplace?
b******7
发帖数: 92
4
分两步:先压缩连续出现次数大于1的字符,再压缩连续出现次数为1的字符
int print_number(int num, char * buf)
{
assert(num >0);
char * p = buf;
while(num > 0)
{
*p++ = num%10 + '0';
num /= 10;
}
//[buf,p) reverse
int len = p - buf;
for(p--;buf < p; buf++,p--)
{
char tmp = *buf;
*buf = *p;
*p = tmp;
}
return len;
}
void compress(char * src)
{
if(src == NULL || *src == '\0') return;
char * p0 = src;
int singlenum = 0;
char * start = src;
while(*start != '\0')
{
char * p = start + 1;
while(*p != '\0' && *p == *start) p++;
*p0++ = *start;
if(p - start > 1)
{
int len = print_number(p-start,p0);
p0 += len;
}
else
singlenum ++;
start = p;
}
p0 --;
char * tail = p0 + singlenum;
*(tail+1) = '\0';
while(p0 >= src)
{
if(*p0 >= '0' && *p0 <= '9')
{
while(*p0 >= '0' && *p0 <= '9')
*tail-- = *p0--;
*tail-- = *p0--;
}
else
{
*tail-- = '1';
*tail-- = *p0--;
}
}
}
d******l
发帖数: 98
5
你们弄的这么麻烦吖。。CC给出3种方法。 第三种方法 可以适用c++,虽然辅助方法多
了点, 但这些方法都是一个 模型, 以后可以适用在其他题中, 举一反三。
以上个人见解。初做算法题,还请大家多多交流 :)
r**h
发帖数: 1288
6
对于每个字符,直接数当前字符出现的数量
如果大于1那么还要append上数字
def compress(s):
s = list(s)
l = len(s)
i, k = 0, 0
while i s[k] = s[i]
k += 1
j = i+1
while j j += 1
count = j-i
if count>1:
s[k] = str(count)
k += 1
i = j
s = s[:k]
return "".join(s)

print("", compress(""))
print("abc", compress("abc"))
print("aabbbccc", compress("aabbbccc"))
print("aaaaaaaaaaaaaaaaa", compress("aaaaaaaaaaaaaaaaa"))
输出
abc abc
aabbbccc a2b3c3
aaaaaaaaaaaaaaaaa a17
J****3
发帖数: 427
7
char *compress(char* str){
int rlen;
int len = strlen(str);
char* dest = (char*)malloc(sizeof(char)*(2*len+1));
int j = 0;
for(int i = 0; i < len; i++){
dest[j++] = str[i];
rlen = 1;
while(i+1 < len && str[i] == str[i+1]){
rlen++;
i++;
}
dest[j++] = rlen+'0';
}
dest[j] = '\0';
return dest;
}
O(n) 但是不是inplace的 你看看行不
d******l
发帖数: 98
8
都是大牛。 : )
u*****o
发帖数: 1224
9
JC你好, 请问你的ALGORITHM可以HANDLE rlen>10的情况吗?
就是这句,还是只适用rlen在2-9之间的CASE吧?
dest[j++] = rlen+'0';

【在 J****3 的大作中提到】
: char *compress(char* str){
: int rlen;
: int len = strlen(str);
: char* dest = (char*)malloc(sizeof(char)*(2*len+1));
: int j = 0;
: for(int i = 0; i < len; i++){
: dest[j++] = str[i];
: rlen = 1;
: while(i+1 < len && str[i] == str[i+1]){
: rlen++;

u*****o
发帖数: 1224
10
你这个SOLUTION很好啊,我喜欢!!PYTHON就是这么美丽!!但很多不是APPLICABLE
TO C++的。。比如PYTHON的LIST可以HOLD MIXED 数据结构,所以
数字和字母可以同时出现,但C++就得用一个CHAR ARRAY吭哧吭哧的一个个复制,
而且a12必须占3个位置,总之各种不美丽!
要不我也攻攻PYTHON,用PYTHON去面试得了。。。

【在 r**h 的大作中提到】
: 对于每个字符,直接数当前字符出现的数量
: 如果大于1那么还要append上数字
: def compress(s):
: s = list(s)
: l = len(s)
: i, k = 0, 0
: while i: s[k] = s[i]
: k += 1
: j = i+1

相关主题
进入JobHunting版参与讨论
J****3
发帖数: 427
11
楼主说的对 handle 那种情况还需要费劲

【在 u*****o 的大作中提到】
: JC你好, 请问你的ALGORITHM可以HANDLE rlen>10的情况吗?
: 就是这句,还是只适用rlen在2-9之间的CASE吧?
: dest[j++] = rlen+'0';

J****3
发帖数: 427
12
处理楼主考虑的那种情况 可以再开个 char temp[] 存如rlen
比如 sprintf(temp, "%d", rlen);
然后再写入dest

【在 J****3 的大作中提到】
: 楼主说的对 handle 那种情况还需要费劲
p****e
发帖数: 3548
13
脑抽了,再改改
string strcompression(string s){
int size = s.size();
if(size < 2) return s;
int i = 0, j = 1, k =0;
char c = s[i];
while(j < size){
while(j j++;
continue;
}
s[i++] = c;
if(j - k > 1){
int num = j - k;
stack ss;
while(num > 0){
ss.push((num % 10) + '0');
num /= 10;
}
while(!ss.empty()){
s[i++] = ss.top();
ss.pop();
}
}
c = s[j];
k = j;
}
return s.substr(0, i);
}
r**h
发帖数: 1288
14
感谢捧场:)
Python在处理数组和字符串的时候的确是有一些优势,不过我觉得遇到链表/树/图这些
还是C++比较方便一点儿

【在 u*****o 的大作中提到】
: 你这个SOLUTION很好啊,我喜欢!!PYTHON就是这么美丽!!但很多不是APPLICABLE
: TO C++的。。比如PYTHON的LIST可以HOLD MIXED 数据结构,所以
: 数字和字母可以同时出现,但C++就得用一个CHAR ARRAY吭哧吭哧的一个个复制,
: 而且a12必须占3个位置,总之各种不美丽!
: 要不我也攻攻PYTHON,用PYTHON去面试得了。。。

r**h
发帖数: 1288
15
C++ style的string最后应该没有\0吧?
r*********n
发帖数: 4553
16
你这个不对吧
abc => a1b1c1 ?

【在 r**h 的大作中提到】
: 对于每个字符,直接数当前字符出现的数量
: 如果大于1那么还要append上数字
: def compress(s):
: s = list(s)
: l = len(s)
: i, k = 0, 0
: while i: s[k] = s[i]
: k += 1
: j = i+1

u*****o
发帖数: 1224
17
这个用STACK HANDLE count>10的办法也很巧妙啊!谢谢你td!
唉板上真是卧虎藏龙啊。葱白你们!

【在 p****e 的大作中提到】
: 脑抽了,再改改
: string strcompression(string s){
: int size = s.size();
: if(size < 2) return s;
: int i = 0, j = 1, k =0;
: char c = s[i];
: while(j < size){
: while(j: j++;
: continue;

r**h
发帖数: 1288
18
他的要求不是说如果count是1的话不输出数字嘛

【在 r*********n 的大作中提到】
: 你这个不对吧
: abc => a1b1c1 ?

J****3
发帖数: 427
19
恩 C style的有
r*********n
发帖数: 4553
20
那如果要输出1呢?
Compress a given string "aabbbccc" to "a2b3c3"
constraint: inplace compression, no extra space to be used
assumption : output size will not exceed input size.. ex input:"abb" -> "
a1b2" buffer overflow.. such inputs will not be given.
http://www.careercup.com/question?id=7449675

【在 r**h 的大作中提到】
: 他的要求不是说如果count是1的话不输出数字嘛
相关主题
进入JobHunting版参与讨论
p****e
发帖数: 3548
21
我的那个改改就可以了

【在 r*********n 的大作中提到】
: 那如果要输出1呢?
: Compress a given string "aabbbccc" to "a2b3c3"
: constraint: inplace compression, no extra space to be used
: assumption : output size will not exceed input size.. ex input:"abb" -> "
: a1b2" buffer overflow.. such inputs will not be given.
: http://www.careercup.com/question?id=7449675

b******7
发帖数: 92
22
要求inplace,和cc150上题不一样。你仔细想想,并注意这个case
"abcddddddddddefg"==> a1b1c1d10e1f1g1
我想不到除我给的方法外更简便的方法了

【在 d******l 的大作中提到】
: 你们弄的这么麻烦吖。。CC给出3种方法。 第三种方法 可以适用c++,虽然辅助方法多
: 了点, 但这些方法都是一个 模型, 以后可以适用在其他题中, 举一反三。
: 以上个人见解。初做算法题,还请大家多多交流 :)

r**h
发帖数: 1288
23
的确如果要求inplace且1也算的话,要扫两遍了

【在 b******7 的大作中提到】
: 要求inplace,和cc150上题不一样。你仔细想想,并注意这个case
: "abcddddddddddefg"==> a1b1c1d10e1f1g1
: 我想不到除我给的方法外更简便的方法了

h**o
发帖数: 548
24
1)请问为什么malloc 是 2*len + 1?
2)如何处理让caller知道你返回dest,他应该用后 删去,还是你返回原str, 他不用删
dest。(如果dest比str长)

【在 J****3 的大作中提到】
: char *compress(char* str){
: int rlen;
: int len = strlen(str);
: char* dest = (char*)malloc(sizeof(char)*(2*len+1));
: int j = 0;
: for(int i = 0; i < len; i++){
: dest[j++] = str[i];
: rlen = 1;
: while(i+1 < len && str[i] == str[i+1]){
: rlen++;

J****3
发帖数: 427
25
2*len+1 是这种情况 abc-> a1b1c1
第二个是啥意思?没大看明白?你是说要在原字符串上操作 Inplace的意思么?

【在 h**o 的大作中提到】
: 1)请问为什么malloc 是 2*len + 1?
: 2)如何处理让caller知道你返回dest,他应该用后 删去,还是你返回原str, 他不用删
: dest。(如果dest比str长)

h**o
发帖数: 548
26
char *compress(char* str){
...
char* dest = (char*)malloc(sizeof(char)*(2*len+1));
...
};
cc150说如果COMPRESSION比原str短,才用新的dest。否则还用原来的str。那caller怎
么知道你返回的是原来的str,所以他不用free dest, 还是你返回了dest,需要caller
free 掉dest哪?

【在 J****3 的大作中提到】
: 2*len+1 是这种情况 abc-> a1b1c1
: 第二个是啥意思?没大看明白?你是说要在原字符串上操作 Inplace的意思么?

k*****o
发帖数: 1972
27
挺好的。
问问,“no extra space to be used”
一般是什么意思?
不能复制数组?

【在 r**h 的大作中提到】
: 对于每个字符,直接数当前字符出现的数量
: 如果大于1那么还要append上数字
: def compress(s):
: s = list(s)
: l = len(s)
: i, k = 0, 0
: while i: s[k] = s[i]
: k += 1
: j = i+1

J****3
发帖数: 427
28
这个是都在新开辟的空间dest上操作 无论长短都返回dest吧

caller

【在 h**o 的大作中提到】
: char *compress(char* str){
: ...
: char* dest = (char*)malloc(sizeof(char)*(2*len+1));
: ...
: };
: cc150说如果COMPRESSION比原str短,才用新的dest。否则还用原来的str。那caller怎
: 么知道你返回的是原来的str,所以他不用free dest, 还是你返回了dest,需要caller
: free 掉dest哪?

h**o
发帖数: 548
29
你的意思是说如果dest比原str还长,就把str拷给dest,依然返回dest?

【在 J****3 的大作中提到】
: 这个是都在新开辟的空间dest上操作 无论长短都返回dest吧
:
: caller

J****3
发帖数: 427
30
是啊

【在 h**o 的大作中提到】
: 你的意思是说如果dest比原str还长,就把str拷给dest,依然返回dest?
相关主题
进入JobHunting版参与讨论
h**o
发帖数: 548
31
thx

【在 J****3 的大作中提到】
: 是啊
J****3
发帖数: 427
32
客气 这个是要O(n) space的 方法吧 不是inplace的

【在 h**o 的大作中提到】
: thx
r*c
发帖数: 167
33
O(N), in place.
void CompressString(char *pRunner, const int len)
{
if(pRunner == NULL || strlen(pRunner) < len ||strlen(pRunner) == 1)
return;

char *pRunnerOrig = pRunner;
char *pKeeper = pRunner; //keeps the last char admitted to the resulting
string, so always increment it before writing back
int nCount = 0;
while(*pRunner != '\0')
{
if(*pRunner != *pKeeper)
{
pKeeper++;
if(pKeeper != pRunner)
*pKeeper = *pRunner;
if(nCount > 1)
{
*pKeeper = (char)(nCount + '0');

//set for the next iteration
pKeeper++;
*pKeeper = *pRunner;
nCount = 1; //we already have one at hand
}
}
else
nCount++;
pRunner++;
}

pKeeper++;
*pKeeper = '\0';
}
h*****g
发帖数: 944
34
这个算法的decompress 应该怎么实现?

。。

【在 u*****o 的大作中提到】
: 很经典的一题,
: Compress a given string "aabbbccc" to "a2b3c3"
: constraint: inplace compression, no extra space to be used
: CC150的答案是JAVA的。。而且我觉得那个方法挺麻烦的,在网上搜了半天,似乎
: AMAZON, GOOGLE都出过这题啊,很希望牛牛们能给个C++的解法,关键是
: abcd 我的CODE RETURN a1b1c1d1啊。。还有如果COUNT>10,也不行。。反正各种弱。。。

h****b
发帖数: 157
35
string compressString(string input)
{
if (input.empty())
return input;
char temp[100];
char last = input.at(0);
int count = 1;
string val="";
for(int i=1;i {
if (input.at(i)==last)
{
count++;
}
else
{
val = val.append(1,last);
itoa(count, temp,10);
val.append(temp);
count=1;
last = input.at(i);
}
}
val = val.append(1,last);
itoa(count, temp,10);
val.append(temp);
return val;
}

。。

【在 u*****o 的大作中提到】
: 很经典的一题,
: Compress a given string "aabbbccc" to "a2b3c3"
: constraint: inplace compression, no extra space to be used
: CC150的答案是JAVA的。。而且我觉得那个方法挺麻烦的,在网上搜了半天,似乎
: AMAZON, GOOGLE都出过这题啊,很希望牛牛们能给个C++的解法,关键是
: abcd 我的CODE RETURN a1b1c1d1啊。。还有如果COUNT>10,也不行。。反正各种弱。。。

1 (共1页)
进入JobHunting版参与讨论
相关主题
相关话题的讨论汇总
话题: char话题: prunner话题: pkeeper话题: p0话题: int