f*****2
发帖数: 141 | 1 愁死我了，感觉思路老是和答案对不上。而且有些solution我真觉得有问题，难道是我
水平太差了？
比如这题：
Design an algorithm and write code to remove the duplicate characters in a
string without
using any additional buffer. NOTE: One or two additional variables is fine.
An extra
copy of the array is not.
FOLLOW UP
Write the test cases for this method
我一直在纠结的是这个remove，不知道怎么算remove，我的理解应该是把重复的元素删
除或置空，可程序总是测试不过。比如：
str[i] = ''; 不行，那应该怎么置空，或者删除？
看了答案，更是一头雾水。首先答案把函数返回值类型定义成void，这个我觉得不太对
，题目是要删除重复字符，那应该返回去掉重复字符之后的字符串啊，这样才能验证功
能不是。如果定义成void就算了，那这个函数里应该输出最后的字符串吧？可是函数里
又没有输出，那怎么验证功能？最郁闷的是答案给的code还编译不通过，这到底怎么回
事啊？
没看到刷题的同学说cc150的答案有问题啊，不会就我看不懂吧？愁死我了 |
p*****2
发帖数: 21240 | |
f*****2
发帖数: 141 | 3 谢谢2爷，这么多人看只有您回了。能不能麻烦二爷分析一下这题？答疑解惑一下，非
常感谢！
【在 p*****2 的大作中提到】
: 好多都是错的
|
g****o
发帖数: 547 | 4 首先尽量找一本最新版，应该是第五版的书
其次去官方网站上有勘误表，自己先校订好
最后，告诉下题号，帮你看一下这题 |
s********u
发帖数: 1109 | 5 看看是不是最新版。我感觉基本都没错，只是解法未必是简洁易懂的。 |
t**8
发帖数: 4527 | 6 input abbacdeeeab
output abcde
What't the problem?
.
【在 f*****2 的大作中提到】
: 愁死我了，感觉思路老是和答案对不上。而且有些solution我真觉得有问题，难道是我
: 水平太差了？
: 比如这题：
: Design an algorithm and write code to remove the duplicate characters in a
: string without
: using any additional buffer. NOTE: One or two additional variables is fine.
: An extra
: copy of the array is not.
: FOLLOW UP
: Write the test cases for this method
|
H*****l
发帖数: 1257 | 7 你的C的基础好像需要补一下
删掉字符后，用memcpy把后面的连带null pointer往前挪一位。
函数应该直接对着原来字符串操作的，所以不需要靠return来返回, 所以函数是void。
.
【在 f*****2 的大作中提到】
: 愁死我了，感觉思路老是和答案对不上。而且有些solution我真觉得有问题，难道是我
: 水平太差了？
: 比如这题：
: Design an algorithm and write code to remove the duplicate characters in a
: string without
: using any additional buffer. NOTE: One or two additional variables is fine.
: An extra
: copy of the array is not.
: FOLLOW UP
: Write the test cases for this method
|
p*****2
发帖数: 21240 | 8 我写了一个练练
(apply str (distinct "abbacdeeeab")) |
s********u
发帖数: 1109 | 9 首先lz你用的应该是老版本的书，新版都没这道题。
我看到题目之后的思路是，先sort，然后是用两个index或者两个指针，一个i匀速往后
遍历，另一个j匀速运动且碰到重复就往后跳。
str[i++] = str[j++];最后根据i的位置resize string。
应该没有o(n)的做法吧，除非用bitset。
每次碰到重复都删除的话，哪怕是用hash table存，看起来是一次遍历O(n)，但挪动起
来相当于是O（n^2)了。所以一定用覆盖来做这个事情，最后一起把尾巴去掉就行。 |
A***o
发帖数: 358 | 10 先别说算法，你这个str[i] = '' 是用什么语言?
.
【在 f*****2 的大作中提到】
: 愁死我了，感觉思路老是和答案对不上。而且有些solution我真觉得有问题，难道是我
: 水平太差了？
: 比如这题：
: Design an algorithm and write code to remove the duplicate characters in a
: string without
: using any additional buffer. NOTE: One or two additional variables is fine.
: An extra
: copy of the array is not.
: FOLLOW UP
: Write the test cases for this method
|
|
|
s********u
发帖数: 1109 | 11 哈哈
【在 A***o 的大作中提到】
: 先别说算法，你这个str[i] = '' 是用什么语言?
:
: .
|
s********u
发帖数: 1109 | 12 建议lz先找本简短的教程补习一下语言，无论是java或者C++。然后务必买一本新版的
cc150，旧版错误是比较多。 |
f*****2
发帖数: 141 | 13 恩，的确得补，好多年不写C了，都忘没了。我的意思是最好有返回值，如果没有也得
在子函数里输出，否则没发验证结果，但是答案既不返回也不输出，我觉得不太对
【在 H*****l 的大作中提到】
: 你的C的基础好像需要补一下
: 删掉字符后，用memcpy把后面的连带null pointer往前挪一位。
: 函数应该直接对着原来字符串操作的，所以不需要靠return来返回, 所以函数是void。
:
: .
|
f*****2
发帖数: 141 | 14 不好意思，丢人了，写matlab写多了，看着remove，总想赋空值，这样省的移动index
或pointer。C忘的差不多了，以为这样可以赋空值，不好意思
【在 A***o 的大作中提到】
: 先别说算法，你这个str[i] = '' 是用什么语言?
:
: .
|
f*****2
发帖数: 141 | 15 的确可能是版本太旧了，我用的是09年的，我也是您这个思路，但是不明白为啥要先
sort?
【在 s********u 的大作中提到】
: 首先lz你用的应该是老版本的书，新版都没这道题。
: 我看到题目之后的思路是，先sort，然后是用两个index或者两个指针，一个i匀速往后
: 遍历，另一个j匀速运动且碰到重复就往后跳。
: str[i++] = str[j++];最后根据i的位置resize string。
: 应该没有o(n)的做法吧，除非用bitset。
: 每次碰到重复都删除的话，哪怕是用hash table存，看起来是一次遍历O(n)，但挪动起
: 来相当于是O（n^2)了。所以一定用覆盖来做这个事情，最后一起把尾巴去掉就行。
|
b*******e
发帖数: 123 | 16
～～～～～这是为什么？有例子么？
【在 s********u 的大作中提到】
: 首先lz你用的应该是老版本的书，新版都没这道题。
: 我看到题目之后的思路是，先sort，然后是用两个index或者两个指针，一个i匀速往后
: 遍历，另一个j匀速运动且碰到重复就往后跳。
: str[i++] = str[j++];最后根据i的位置resize string。
: 应该没有o(n)的做法吧，除非用bitset。
: 每次碰到重复都删除的话，哪怕是用hash table存，看起来是一次遍历O(n)，但挪动起
: 来相当于是O（n^2)了。所以一定用覆盖来做这个事情，最后一起把尾巴去掉就行。
|
f*****2
发帖数: 141 | 17 麻烦大家帮我看看哪有错误，为什么老师运行时候有错误？非常感谢！
void remove_duplicate_value(char* str)
{
int i, j, len;
char *newStr;
len = strlen(str);
for (i = 1; i < len; i++)
{
for (j = i-1; j >= 0; j--)
{
if (str[i] == str[j])
{
int k = i+1;
while (str[i] == str[k] && k <= len)
{
k++;
}
if (str[i] != str[k])
str[i] = str[k];
else
strncpy(newStr, str, i);
}
}
}
puts(newStr);
} |
A***o
发帖数: 358 | 18 newStr 没初始化
【在 f*****2 的大作中提到】
: 麻烦大家帮我看看哪有错误，为什么老师运行时候有错误？非常感谢！
: void remove_duplicate_value(char* str)
: {
: int i, j, len;
: char *newStr;
: len = strlen(str);
: for (i = 1; i < len; i++)
: {
: for (j = i-1; j >= 0; j--)
: {
|
s********u
发帖数: 1109 | 19 不sort的话，你重复的字母不会到一起去啊。因为他不允许用其他数据结构记录重复的
字母，所以只能先排序再做啦。反正只要用in place的sort方式就行了，比如者qsort
，heapsort。
【在 f*****2 的大作中提到】
: 的确可能是版本太旧了，我用的是09年的，我也是您这个思路，但是不明白为啥要先
: sort?
|
s********u
发帖数: 1109 | 20 字符串不就是个字符数组么。
打个比方，就是aaaaaaaaaaa，然后你除了第一个，每次看到a都想把他删除，那样的话
相当于将后面的字符全部左移一位，这就是O（n),每次都是O(n)，那就是O(n^2)
就跟你删除数组里面的元素是一样的。
【在 b*******e 的大作中提到】
:
: ～～～～～这是为什么？有例子么？
|
b*******e
发帖数: 123 | 21 喔，这个意思。谢谢。
【在 s********u 的大作中提到】
: 字符串不就是个字符数组么。
: 打个比方，就是aaaaaaaaaaa，然后你除了第一个，每次看到a都想把他删除，那样的话
: 相当于将后面的字符全部左移一位，这就是O（n),每次都是O(n)，那就是O(n^2)
: 就跟你删除数组里面的元素是一样的。
|
