收集一些关于字符串的面试笔试题。

1. 逆序字符串

思路：原地逆序，将字符串两边的字符逐个交换。例如，给定字符串“abcd”，逆序的过程分别是交换字符a和d，交换字符b和c。

实现1)：通过指针

char *Reverse(char *s){　　char *p = s;　　char *q = s;　　while(*q) ++q;　　q--;　　while(q > p)　　{　　　　 char t = *p;        *p++ = *q;        *q-- = t;　  　　}    return s;}

实现2）：递归法

char *Reverse(char *s,int left,int right){    if(left >= right)        return s;    char t  = s[left];    s[left] = s[right];    s[right] = t;    Reverse(s,left+1,right-1);}

 

2. 找出字符串中第一次只出现一次的字符

思路：巧妙的利用STL中的map容器，代码很简单。

int FirstNotRepeatingChar(string str) {    map
     
       mp;    for(int i=0; i
     

 

3. 字符串的排列

输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串abc，acb，bac，bca，cab和cba。

思路：递归法，通过交换遍历第k位可能的所有字符。

void PermutationHelp(vector
     
       &ans, int k, string str) //遍历第k位的所有可能{    if(k == str.size() - 1)        ans.push_back(str);    unordered_set
      
        us;  //记录出现过的字符    sort(str.begin() + k, str.end());  //保证按字典序输出    for(int i = k; i < str.size(); i++)    {        if(us.find(str[i]) == us.end()) //只和没交换过的换        {              us.insert(str[i]);            swap(str[i], str[k]);            PermutationHelp(ans, k + 1, str);            swap(str[i], str[k]);  //复位        }    }} vector
       
         Permutation(string str) {    vector
        
          ans;    PermutationHelp(ans, 0, str);    return ans;}
        
       
      
     

 

4. 字符串转换为数字，《primer 5th》p328中提供封装的函数。

C语言实现：

int Mystoi(char *str){    if(str==NULL)    {        printf("Invalid Input");        return -1;    }    while(*str==' ' || *str=='  '){        str++;    }    int nSign = (*str=='-') ? -1:1 ;    if(*str=='+' || *str=='-')    {        str++;    }    int res = 0;    while(*str>='0' && *str <='9')    {        res = res*10 + (*str-'0');        str++;    }    return res*nSign;}

 

5. 数字转换为字符转

C语言实现：

char* Myitos(int num){    static char str[1024];    //这里必须要static, 因为局部变量是要释放掉的 见见《Primer 5th》p185    int sign = num, i=0, j=0;    char temp[11];    if(sign<0){        num = -num;    };    do{        temp[i] = num%10+'0';        num /= 10;        i++;    }while(num>0);    if(sign<0){        temp[i++]='-';    }    temp[i]='\0';    i--;    while(i>=0){        str[j]=temp[i];        j++;        i--;    }    str[j]='\0';    return str;}int main(int argc, char const *argv[]){    printf("%s\n",Myitos(-12345));       return 0;}

输出 12345。

上面得两个函数如果使用c++11中的库函数，则非常简单，见《Primer 5th》p328 如下：

#include 
     
      #include 
      
       using namespace std;int main(int argc, char const *argv[]){    string s = "12345";    int i = 8888;    cout << stoi(s) << endl;      // 12345    cout << to_string(i) << endl; // 8888    return 0;}
      
     

 

6. 翻转字符串

将字符串 “I like beijing.” 翻转为 “beijing like I”

string ReverseSentence(string str) {    int len = str.size();    string res="", tmp="";    for(int i=0;i