Q1:Write code to reverse a C-Style String.
Q2:Design an algorithm and wirte code to remove the duplicate characters in a string without using any additional buffer.
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <string> #include <algorithm> using namespace std; /**************************/ /*Reverse a C-style String*/ /**************************/ void reverse(char * str) { char *end=str; char tmp; if(str) { while(*end) ++end; } --end; while(str<end) { tmp=*str; *str++ = *end; *end--=tmp; } } /*********************************************/ /*Remove the duplicate characters in a string*/ /*********************************************/ /*No Additional Memory*/ static void removeDuplicates(char str[]) { if(str==NULL) return; int len=strlen(str); if(len<2) return; int tail=1;//tail指向未含重复字符的字符串的下一位,等待被赋值 for(int i=1;i<len;++i) { //遍历一遍字符串 int j; for(j=0;j<tail;++j) { //j遍历0-tail中指向的已统计的无重复字符 if(str[i]==str[j]) break;//遇到重复的字符只是简单跳过 } if(j==tail) { //若之前的字符都无重复,则j=tail,str[i]添加进无重复字符串中 str[tail]=str[i]; ++tail; } } str[tail]=0; } /*With Additional Memory of Constant Size*/ static void removeDuplicatessEff(char str[]) { if(str==NULL) return; int len=strlen(str); if(len<2) return; //ASCⅡ码8位 bool *hit=new bool[256]; for(int i=0;i<256;++i) hit[i]=false; hit[str[0]]=true; int tail=1; for(int i=1;i<len;++i) { if(!hit[str[i]]) { str[tail]=str[i]; ++tail; hit[str[i]]=true; } } str[tail]=0; } int main() { char tmp1[]="abcababababa"; char tmp2[]="abcababababa"; char tmp3[]="abcdfe"; removeDuplicates(tmp1); removeDuplicatessEff(tmp2); reverse(tmp3); cout << tmp1 <<endl; cout << tmp2 <<endl; cout << tmp3 <<endl; }