鸡们在跳钢管舞 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

鸡们在跳钢管舞

鸡们在跳钢管舞# Joke - 肚皮舞运动

h*g2012-01-11 08:01

1 楼

You are given a string like "aaaabbbcc", do an in place conversion which
write frequency of each charater(which come continuosly) with that character
Example:
input: aaabbbccd
output: a3b2c2d1
input: aabaa
output: a2b1a2

j*e2012-01-11 08:01

2 楼

红色食用色素究竟对健康有害没有?

g*y2012-01-11 08:01

3 楼

如果全是不同的单字母，比如abab..., output就是a1b1a1b1..., 需要2N空间，没办法
in-place.

character

【在 h*****g 的大作中提到】

: You are given a string like "aaaabbbcc", do an in place conversion which
: write frequency of each charater(which come continuosly) with that character
: Example:
: input: aaabbbccd
: output: a3b2c2d1
: input: aabaa
: output: a2b1a2

s*n2012-01-11 08:01

4 楼

应该还好

【在 j****e 的大作中提到】

: 红色食用色素究竟对健康有害没有?

l*82012-01-11 08:01

5 楼

的确是。。。我怎么没想到。
如果不考虑空间的话，这道题目就是一个读指针一个写指针。如果写指针不超过读指
针，就可以inplace而且是一遍扫描完成。。可是下面的例子怎么完成？
ababaaaaaaabbbbbbbabab
a1b1a7b7a1b1
这个例子就难以保证一遍扫描了。

【在 g**********y 的大作中提到】

: 如果全是不同的单字母，比如abab..., output就是a1b1a1b1..., 需要2N空间，没办法
: in-place.
:
: character

p*g2012-01-11 08:01

6 楼

如果在国内，还是“专家”说了蒜

【在 j****e 的大作中提到】

: 红色食用色素究竟对健康有害没有?

l*82012-01-11 08:01

7 楼

如果array长度是2*n, 但是只有前n个有字母的话，可以反向读取，把结果放到最末尾
的空白空间，最后再向前移到开头。
现在考虑，如果array末尾没有多余空位，n个元素放在长度为n的array里面，而消减后
的字符串保证能放在原来的array里,也还有些tricky.比如刚才说这个例子，
ababaaaaaaabbbbbbbabab
a1b1a1b1a7b7a1b1a1b1

【在 l*********8 的大作中提到】

: 的确是。。。我怎么没想到。
: 如果不考虑空间的话，这道题目就是一个读指针一个写指针。如果写指针不超过读指
: 针，就可以inplace而且是一遍扫描完成。。可是下面的例子怎么完成？
: ababaaaaaaabbbbbbbabab
: a1b1a7b7a1b1
: 这个例子就难以保证一遍扫描了。

r*e2012-01-11 08:01

8 楼

使用跳字,牵强

【在 j****e 的大作中提到】

: 红色食用色素究竟对健康有害没有?

p*22012-01-11 08:01

9 楼

这题有人要求in place吗？

l*82012-01-11 08:01

10 楼

in place我觉得更有意思些：）

【在 p*****2 的大作中提到】

: 这题有人要求in place吗？

p*22012-01-11 08:01

11 楼

这题原题的要求是压缩，如果结果的字符串超过原串的长度则do nothing。可以先计算
一下结果字符串长度。然后in place。

【在 l*********8 的大作中提到】

: in place我觉得更有意思些：）

p*22012-01-11 08:01

12 楼

不过这个case有些麻烦
caaab
需要先占用字符。不知道还有没有其他的case要特殊处理的。

l*82012-01-11 08:01

13 楼

如果是压缩的话， ab就不用转换成a1b1了。
ababaaaaaaabbbbbbbabab
就转换成：
ababa7b7abab

【在 p*****2 的大作中提到】

: 不过这个case有些麻烦
: caaab
: 需要先占用字符。不知道还有没有其他的case要特殊处理的。

l*82012-01-11 08:01

14 楼

恩，你这个例子跟我说的类似，不过更简洁些：）

【在 p*****2 的大作中提到】

: 不过这个case有些麻烦
: caaab
: 需要先占用字符。不知道还有没有其他的case要特殊处理的。

l*82012-01-11 08:01

15 楼

如果caaab要转换成c1a3b1的话，
可以用三个指针。
第一个i 预扫描，计算到目前为止，是否有足够的space存储要求的字符串，并累计end
_position
第二个指针 j 从 i开始逆向读，
第三个指针从 end_position 开始逆向写

【在 p*****2 的大作中提到】

: 不过这个case有些麻烦
: caaab
: 需要先占用字符。不知道还有没有其他的case要特殊处理的。

h*d2012-01-11 08:01

16 楼

if you are not required to print the "1", you should be able to do that, rig
ht... like a3b2c2d

character

【在 h*****g 的大作中提到】

h*l2012-01-11 08:01

17 楼

我觉得走3遍就好了
第一次把所有不是单独出现的字符写好，
比如 caaab变成 ca3b
然后走一遍 ca3b，看看有多少字符是没有数字1的
然后倒过来写，不是数字加字幕的，就加一个1

rig

【在 h****d 的大作中提到】

: if you are not required to print the "1", you should be able to do that, rig
: ht... like a3b2c2d
:
: character

p*22012-01-11 08:01

18 楼

rig
原题是u要求a1的。

【在 h****d 的大作中提到】

: if you are not required to print the "1", you should be able to do that, rig
: ht... like a3b2c2d
:
: character

h*d2012-01-11 08:01

19 楼

i was asked the same question in an amazon interview... in that one, the 1 i
s not required and the interviewer hinted that i could do it in place...

【在 p*****2 的大作中提到】

:
: rig
: 原题是u要求a1的。

w*x2012-01-11 08:01

20 楼

先走一遍计算需要空间, 然后倒着来一趟

p*22012-01-11 08:01

21 楼

i
那不是走一遍就可以了？

【在 h****d 的大作中提到】

: i was asked the same question in an amazon interview... in that one, the 1 i
: s not required and the interviewer hinted that i could do it in place...

w*o2012-01-11 08:01

22 楼

能否讲讲，这个"倒着来一趟"是干什么的？
谢谢！

【在 w****x 的大作中提到】

: 先走一遍计算需要空间, 然后倒着来一趟

l*82012-01-11 08:01

23 楼

How do you apply your algorithm on
ababaaaaaaabbbbbbbabab
or
caaab ?

【在 w****x 的大作中提到】

: 先走一遍计算需要空间, 然后倒着来一趟

w*o2012-01-11 08:01

24 楼

这道题还有一个tricky的地方，就是要用到类似itoa()的,有的字符可能重复几十次，
可能要占用多余一个字符的位置去存。

character

【在 h*****g 的大作中提到】

w*x2012-01-11 08:01

25 楼

没仔细看, 既然没要求in-place就别费那个脑筋了.

【在 l*********8 的大作中提到】

: How do you apply your algorithm on
: ababaaaaaaabbbbbbbabab
: or
: caaab ?

p*22012-01-11 08:01

26 楼

几百，几千，几万次都又可能吧？

【在 w****o 的大作中提到】

: 这道题还有一个tricky的地方，就是要用到类似itoa()的,有的字符可能重复几十次，
: 可能要占用多余一个字符的位置去存。
:
: character

s*r2012-01-11 08:01

27 楼

只处理出现次数小于10的情况，但是可以很容易修改处理出现次数多余9次的情况。
我写的，见笑了：
/***********************************************************************
*********************/
/* Compress a String: AAABBCDDDD will be A3B2CD4 */
//
private static String compressString(String str)
{
char[] chars = str.toCharArray();
char current = chars[0];
int count = 1;
int indexCounter = 1;
int shiftBack = 0;
for(int i = 1; i< chars.length; i++){
if (current == chars[i]){
count++;
chars[indexCounter] = Integer.toString(count).charAt(0);
}
else
{
current = chars[i];
//shift array back to fill up any vacant slots
shiftBack += count > 2 ? (count-2) : 0;
//reset count to start next group
count = 1;
if (shiftBack > 0)
{
chars[i - shiftBack] = chars[i];
}
indexCounter = i - shiftBack + 1;
}
}
return new String(chars,0, (indexCounter + (count > 1 ? 1 : 0)) );
}