v***n
发帖数: 562 | 1 CH 1
Remove duplicate character from a string without any extra buffer.
答案应该错了。
谢谢 | p****n
发帖数: 294 | 2 string里只有 ascii码？ 有空格吗？完全不能用buffer还是得在O(1)范围内？ | g*****i
发帖数: 2162 | 3 建议下次多解释下问的问题吧,比如你说但应该错了,那你至少说一下你为啥觉得错吧.
这题看你怎么理解remove duplicate了. 比如有2个a,是只保留一个,还是都不保留?
书里给的答案是保留一个.
【在 v***n 的大作中提到】
: CH 1
: Remove duplicate character from a string without any extra buffer.
: 答案应该错了。
: 谢谢
| c****p
发帖数: 6474 | 4 我觉得他的意思是答案用了一个额外的表来记录字母出现的次数，这个不算没用extra
buffer。我个觉得可以用bitset来做，128个合法ASCII基本字符集，四个32-bit（或者
两个long）变量就够了。
【在 g*****i 的大作中提到】
: 建议下次多解释下问的问题吧,比如你说但应该错了,那你至少说一下你为啥觉得错吧.
: 这题看你怎么理解remove duplicate了. 比如有2个a,是只保留一个,还是都不保留?
: 书里给的答案是保留一个.
| g*****i
发帖数: 2162 | 5 书里给了两个答案吧,第二个是你说的256的数组,第一个就类似brute force比较,没用
额外空间.
extra
【在 c****p 的大作中提到】
: 我觉得他的意思是答案用了一个额外的表来记录字母出现的次数，这个不算没用extra
: buffer。我个觉得可以用bitset来做，128个合法ASCII基本字符集，四个32-bit（或者
: 两个long）变量就够了。
| v***n
发帖数: 562 | 6 谢谢回复！
我跑了一个test case
char[] str = {'a', 'b', 'a', 'd', 'c', 'e', 'b'};
但是，最后两个'b'都保留了。
【在 g*****i 的大作中提到】
: 建议下次多解释下问的问题吧,比如你说但应该错了,那你至少说一下你为啥觉得错吧.
: 这题看你怎么理解remove duplicate了. 比如有2个a,是只保留一个,还是都不保留?
: 书里给的答案是保留一个.
| v***n
发帖数: 562 | 7 我说的第一个brute force那个错了。
【在 g*****i 的大作中提到】
: 书里给了两个答案吧,第二个是你说的256的数组,第一个就类似brute force比较,没用
: 额外空间.
:
: extra
| c****p
发帖数: 6474 | 8 我也测试了一下，，木有问题。
【在 v***n 的大作中提到】
: 谢谢回复！
: 我跑了一个test case
: char[] str = {'a', 'b', 'a', 'd', 'c', 'e', 'b'};
: 但是，最后两个'b'都保留了。
| k****n
发帖数: 369 | 9 不管你用bit buffer还是int array，都不能算O(1)。。。
extra
【在 c****p 的大作中提到】
: 我觉得他的意思是答案用了一个额外的表来记录字母出现的次数，这个不算没用extra
: buffer。我个觉得可以用bitset来做，128个合法ASCII基本字符集，四个32-bit（或者
: 两个long）变量就够了。
| c****p
发帖数: 6474 | 10 这个要看怎么理解。。
严格说这么用buffer的size是constant，是和O(1)一个级别的，
虽然说一般字符串都没有一百多个字节那么长。
我觉得把bit buffer理解为“少量的additional space”而不是“extra buffer”是可
以接受的。【 在 kevinn (Kevinn) 的大作中提到: 】 |
|
