C++常见笔试题（一）字符串

1. 实现字符串常用的四个库函数

1.1 strcpy

char *strcpy(char *strDest,const char *strSrc)
{
      assert((strDest!=nullptr)&&(strSrc!=nullptr));
      char *p = strDest;
      while((*strDest++ = *strSrc++));
      return p;
}

1.2 strlen

int strlen(char *str)
{
     int len = 0;
     while(str[len] !='\0')
          len++;
     return len;
}

1.3 strcat

char *strcat(char *str1,const char *str2)
{
    char *p = str1;
    while(*str1)
      str1++;
    while( (*str1++ = *str2++)!='\0');
    return p;
}

1.4 strcmp

  int strcmp(const char *str1,const char *str2)
{
    while((*str1==*str2)&& *str1 != '\0') 
    {
         str1++;
         str2++;
    }  

    if(*str1>*str2) return 1;
    else if(*str1<*str2) return -1;
    else return 0;
}

2. 计算字符串里出现的特定子串的次数

int appearTimes(char *str,char *subStr)
{ 
    int num = 0;
    while(*str != '\0')
    {
        char *q = str;
        char *p = subStr;
        while((*p ==*q)&&(*p!='\0')&&(*q!='\0'))
        {
            p++；
            q++;
        }
        if(*p=='\0') num++;
        str++;
    }
        return num;
}

3. 打印出字符串里最长的无重复字符的子串

void printLongStr(string str)
{
    //保存不重复的临时子串  
    string tmp;
    //保存不重复的所有子串
    vector<string> svec;
    //记录每次开始查找字符的相对位置
    int relative = 0;
    //记录当前字符在临时字符串中的位置
    int pos = 0;

    for(int i=0;i<str.size();i++)
    {
        tmp.push_back(str[i]);
        pos = tmp.find(str[i]);
        if(pos<0)
        {
            tmp.push_back(str[i]);
        }
        else
        {
            svec.push_back(tmp);
            tmp.clear();
            relative = relative + pos +1;
            i = relative;
        }
    }
     svec.push_back(tmp);
     //寻找最大的不重复子串的长度
    vector<string>::iterator it = svec.begin();
    int maxSize = 0;
    for(; it!=svec.end(); ++it)
    {
        if((*it).size()>maxSize)
            maxSize = (*it).size();
    } 
//打印最大长度的不重复子串
    for (it = svec.begin(); it != svec.end(); ++it)
    {
        if ((*it).size() == maxSize)
        {
            cout << *it << endl;
        }
    }
}

4. 在一个字符串中找到第一个只出现一次的字符,并返回它的位置

int FindFirstCharPlace(const char *str)
{
      int *p=str;
      int i = 0;
      map<char,unsigned int> strmap;
      while(*p!='\0')
      {
          strmap[*p]++;
      }
      while(*str !='\0')
      {
          i++;
          if(strmap[*str]==1)
          return i;
      }
     return -1;  
}

5. 给定两个字符串A和B，判断A中是否包含由B中字符重新排列成的新字符串,在 A 中出现的 B 字符串里的字符不需要连续或者有序

bool checkNewStr(const char *str1,const char *str2)
{
    char *p = str1;
    char *q = str2;
    map<char,unsigned int> strmap1;
    map<char,unsigned int> strmap2;
    while(*q != '\0')
    {
      strmap2[*q]++;
      q++;
    }
    while(*p != '\0')
    {
      strmap1[*p]++;
      p++;
    }
    map<char,unsigned int>::iterator iter = strmap2.begin();
    for(;it !=strmap2.end();*it++)
    {
        if((strmap1.find(it->first)->second) < it->second)
          return false;         
    }
     return true;
}

6. 数字转字符串

string changeToStr(int num)
{
    string strnum = nullptr;
    if(num==0)
        return "0";
    while(num!=0)
    {
        int temp = num%10;
        char c = temp + '0';
        strnum.push_back(c);
        num/=10;
    }
    reverse(strnum.begin(),strnum.end())
    return strnum;
}

7. 字符串逆置

7.1 折半法

char *reserve(char *strSrc)
{
    if(strSrc == NULL) return NULL;
    int len = strlen(strSrc);
    char *p = stSrc;
    char *q = strSrc+len-1;
    while(p<q)
    {
        char temp = *p;
        *p = *q;
         *q = temp;
         p++;
         q--;
    }
    return strSrc;
}

7.2 异或法（无需申请中间变量）

char *reserve(char *strSrc)
{
    if(strSrc == NULL) return NULL;
    int len = strlen(strSrc);
    char *p = strSrc;
    char *q = strSrc + len -1;
    while(p<q)
    {
        *p ^= *q;
        *q ^= *p;
        *p ^= *q;
        p++;
        q--;
    }
    return strSrc;
}

7.3 字符串逆序，单词不变

char *reserve(char *strSrc)
{
    if(strSrc==NULL) return NULL;
    char *q = char[strlen(strSrc)+1];
    int t = 0,k =0;
    int i = strlen(strSrc)-1;
    int j = strlen(strSrc);
    while(i>0)
    {
        while(strSrc[i]!=' '&&i!=0)
            i--;
        t = i; 
        if(i!=0)
        {
          while(i<j)
          {
              q[k++] = strSrc[i++];                       
          }
          q[k++] = ' ';
          i = t - 1;
          j = t;
        } 
      else
      {
            while(i<j)
          {
              q[k++] = strSrc[i++];                       
          }
          i = t;
      } 
    }
    return q;
}

8. 下次继续

引用