CCI习题1-3:Remove Duplications in String

By | 2012 年 11 月 13 日

直接从头到尾扫描,用一个int来做hash表。
代码默认输入字符在’a’ – ‘z’之间,如果超出的话用作hash表的int扩展一下就行了,算法本身不变。



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 are fine. An extra copy of the array is not.
FOLLOW UP
Write the test cases for this method.



代码

<

pre>

//
// main.cpp
// CCI.1.3.RemoveDuplicationsInString
//
// Created by Qiu Xiangyu on 12-11-13.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

using namespace std;

void removeDuplicate(char cstr) {
if (cstr == NULL) {
return;
}
int map = 0;
char * curloc = cstr;
while(
cstr != ‘\0’) {
int hashc = *cstr – ‘a’;
int bit = 1 << hashc;
if (!(map & bit)) {
//no exist char
map = map | bit;
*curloc = *cstr;
++curloc;
}
++cstr;
}
*curloc = ‘\0’;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input below:\n”;
char cstr[200];
scanf(“%s”,cstr);
cout<<“Input:”<<cstr<<endl;

//process
removeDuplicate(cstr);
cout<<"Result : "<<cstr<<endl;

return 0;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注