面试35-删除字符串重复字符-删除出现在第二个字符串中的字符-第一个只出现一次的字符-hash表计数

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
char firstStrAppearOne(const char* str);// 第一个只出现一次的字符
void str1MinusStr2(char* str1,const char* str2);// 删除出现在第二个字符串中的字符
void uniqueStr(char* str);// 删除重复字符
int main()
{
    char* str="aac"; // str指向字符串常量
    cout<<firstStrAppearOne(str)<<endl;
    char str1[]="abcdefghbghc";
    str1MinusStr2(str1,"bce"); // 参数必须是指向可修改内存的指针
    cout<<str1<<endl;
    char str2[]="aaabcdefegghhgi";
   //char str2[]="abcd";
   uniqueStr(str2);
   cout<<str2<<endl;
   return 0;
}
char firstStrAppearOne(const char* str)
{
     if(str==NULL)
         return'\0';
     int hash[256]={0};
     const char* p=str;
     while(*p!='\0')
    {
        ++hash[*p];
        p++;
    }
    while(*str!='\0')
   {
       if(hash[*str]==1)
       return *str;
      ++str;
   }
      return '\0';
}
void str1MinusStr2(char* str1,const char* str2) // 这里的删除字符,是字符前移,后在新的结尾加上\0
{
      if(str1==NULL||str2==NULL)
      return;
      bool hash_flag[256]={0};
      const char* p_str2=str2;
     while(*p_str2!='\0')
    {
         hash_flag[*p_str2]=true;
         ++p_str2;
    }
// 用两个指针实现O(n)的删除移动算法, 关键在于p2的值不能受p1的影响
   char* p1=str1;
   char* p2=str1;

while(*p2!='\0'&&hash_flag[*p2]!=true) // p2的初试值设置为第一个需要删除的结点
    p2++;
   if(*p2=='\0') // 没有需要删除的返回
   return;

char tmp;
   while(*p1!='\0') // p1找到第一个需要删除的点
  {
       while(*p1!='\0'&&hash_flag[*p1]!=true)
       ++p1;
       if(*p1=='\0')
       return;
      else
     {
            while(*p2!='\0'&&hash_flag[*p2]==true) // p2找到后面第一个需要保留的字符
            ++p2;
            if(*p2=='\0')
           {
                 *p1='\0';
                 return;
           }
           else
          {
                 tmp=*p1;
                *p1=*p2;
                *p2=tmp;
           }
     }
     ++p1;
   }
}
void uniqueStr(char* str) // 同上一个算法类似,也是用两个指针
{
        if(str==NULL)
            return;
        bool flag[256]={false}; // 此处如果为true 表示前面出现过,要删除
        char* p1=str;
        char* p2=str;
        while(*p1!='\0') // 为p2设置初始值,指向第一个需要删除的字符
        {
              if(flag[*p1]==false)// 首次出现,相应为置为true
                    flag[*p1]=true;
              else // 第n>2次出现,需要删除
             {
                  p2=p1;
                  break;
              }
             ++p1;
        }
        char tmp;
        while(*p1!='\0') // 此时p1 p2都指向第一个需要删除的字符
        {
              if(flag[*p1]==false)// 首次出现,相应为置为true
                     flag[*p1]=true;
             else // 第n>2次出现,需要删除
             {
                    while(*p2!='\0'&&flag[*p2]==true)
                             ++p2;
                    if(*p2=='\0')
                   {
                        *p1='\0';
                         return;
                   }
                  else
                  {
                        flag[*p2]=true;
                        tmp=*p1;
                       *p1=*p2;
                      *p2=tmp;
                   }
            }
            ++p1;
       }
}

上一篇:学习WCF入门的第一个实例


下一篇:ELK日志管理之——kibana部署