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 | |
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 | |
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
|
|
|
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 | |
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的话不输出数字嘛
|
|
|
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?
|
|
|
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,也不行。。反正各种弱。。。
|
