现在的位置: 首页 > 综合 > 正文

字符串

2014年09月05日 ⁄ 综合 ⁄ 共 17461字 ⁄ 字号 评论关闭

一,字符串转化

        将字符串转换成整数:atoi

        将整数转换为字符串:itoa

         浮点数与字符串的转换

1)字符串转化为整数

        需要注意的地方:

                                       考虑要缜密,注意是否为数字字符;

                                       判断是否为NULL

                                       开头的‘+’‘-’符号的判断

  1. #include "stdio.h"  
  2. #include "string.h"  
  3. #include "assert.h"  
  4.   
  5. int isDigit(char c)  
  6. {  
  7.     if(c>='0'&&c<='9')  
  8.         return 1;  
  9.     else  
  10.         return 0;   
  11.       
  12. }   
  13. int myatoi(const char *str)  
  14. {  
  15.     assert(str!=NULL);  
  16.     int count=strlen(str);  
  17.     int result=0;  
  18.       
  19.     int sign=1;  
  20.     if(str[0]=='-')  
  21.     {  
  22.         sign=-1;   
  23.     }   
  24.     else if(str[0]=='+')  
  25.     {  
  26.         sign=1;   
  27.     }   
  28.     else if(isDigit(str[0]))   
  29.     {  
  30.         result=str[0]-'0';  
  31.         sign=1;   
  32.     }   
  33.     for(int i=1;i<count;++i)  
  34.     {  
  35.         assert(isDigit(str[i]));  
  36.           
  37.         result=result*10+(str[i]-'0');  
  38.     }  
  39.       
  40.     return result;  
  41.       
  42.       
  43. }  
  44. int  main()  
  45. {  
  46.     printf("%d\n",myatoi("123"));  
  47. }  

 

别看一个这么简单的问题,实际要考虑的问题很多。还是看一下glibc的实现吧

  1. #include "stdio.h"  
  2. #include "string.h"  
  3. #include "assert.h"  
  4.   
  5. #define LONG_MAX 2147483647L   
  6. #define LONG_MIN (-2147483647L-1L)  
  7.   
  8.   
  9. long int _strtol_internal (const char *nptr, char **endptr, int base, int group)  
  10. {  
  11.     //注意要使用unsigned long否则会发生溢出,因为long int最多2147483647L ,无法表示2147483648L  
  12.     unsigned long int result = 0;  
  13.     long int sign = 1;  
  14.     //考虑前导空格  
  15.     while (*nptr == ' ' || *nptr == '\t')  
  16.         ++nptr;  
  17.     //考虑带有正负号  
  18.     if (*nptr == '-')  
  19.     {  
  20.         sign = -1;  
  21.         ++nptr;  
  22.     }  
  23.     else if (*nptr == '+')  
  24.         ++nptr;  
  25.         //如果出现非法输入  
  26.     if (*nptr < '0' || *nptr > '9')  
  27.     {  
  28.         if (endptr != NULL)  
  29.             *endptr = (char *) nptr;  
  30.         return 0L;  
  31.     }  
  32.     //考虑进制  
  33.     assert (base == 0);  
  34.     base = 10;  
  35.     if (*nptr == '0')  
  36.     {  
  37.         if (nptr[1] == 'x' || nptr[1] == 'X')  
  38.         {  
  39.             base = 16;  
  40.             nptr += 2;  
  41.         }  
  42.         else  
  43.             base = 8;  
  44.     }  
  45.     //防止非法字符   
  46.     while (*nptr >= '0' && *nptr <= '9')  
  47.     {  
  48.         unsigned long int digval = *nptr - '0';  
  49.   
  50.         //防止溢出,如果溢出了long的表示范围,则置errno   
  51.         if (result > LONG_MAX / 10 || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10 :   
  52.                   (result == ((unsigned long int) LONG_MAX + 1) / 10 && digval > ((unsigned long int) LONG_MAX + 1) % 10)))  
  53.         {  
  54.             errno = ERANGE;  
  55.             return sign > 0 ? LONG_MAX : LONG_MIN;  
  56.         }  
  57.         result *= base;  
  58.         result += digval;  
  59.         ++nptr;  
  60.     }  
  61.     return (long int) result * sign;  
  62. }  

 

         atoi函数就是这个函数讲第二个参数置为NULL,第三个参数置为10。不知道你注意到了那些空格,越界之类的判断没有。我同学说他写出来的代码最后就被要求加上了这些东西,最后还因此被卡掉了(说是考虑不够慎密,汗)。

2)itoa 函数的实现

      char *itoa( int value, char *string,int radix);

      先看一看使用:

  1. #include <stdlib.h>  
  2. #include <stdio.h>  
  3. int main(void)  
  4. {  
  5.     int number = 12345;  
  6.     char string[25];  
  7.     itoa(number, string, 10); //按十进制转换  
  8.     printf("integer = %d string = %s\n", number, string);  
  9.     itoa(number, string, 16); //按16进制转换  
  10.     printf("integer = %d string = %s\n", number, string);  
  11.     return 0;  
  12. }   

 

整形转化为字符串(这里默认十进制的转换)

  1. //整形转成字符串函数实现  
  2. //题目不难,重点考察面试者对问题考虑的全面程度  
  3. #include <iostream>  
  4. using namespace std;  
  5. void itoa_mf(int num,char str[])  
  6. {  
  7.     int sign = num;  
  8.     int i = 0;  
  9.     int j = 0;  
  10.     char temp[100];  
  11.     if(sign < 0)//如果是负数就去掉符号,将-1234转成1234  
  12.     {  
  13.         num = -num;  
  14.     }  
  15.       
  16.     do//转成字符串,1234转成"4321"  
  17.     {  
  18.         temp[i] = num % 10 + '0';  
  19.         num /= 10;  
  20.         i++;  
  21.     }while(num > 0);  
  22.     if(sign < 0)//如果是负数的话,加个符号在末尾,如:"4321-"  
  23.     {  
  24.         temp[i++] = '-';  
  25.     }  
  26.     temp[i] = '\0';  
  27.     i--;  
  28.     //将temp数组中逆序输入到str数组中  
  29.     //将"4321-" ====> "-1234"  
  30.     while(i >= 0)  
  31.     {  
  32.         str[j] = temp[i];  
  33.         j++;  
  34.         i--;  
  35.     }  
  36.     //字符串结束标识  
  37.     str[j] = '\0';  
  38. }  
  39. int main()  
  40. {  
  41.     int a = +123;  
  42.     char s[100];  
  43.     itoa_mf(a,s);  
  44.     cout << s << endl;  
  45.   
  46. }  

二,找出字符串的最长子串,要求子串的所有字符相同

         例如:str ="sssddddabcdef"  则输出字串为:dddd

  1. #include <stdlib.h>  
  2. #include <stdio.h>  
  3. #include <string.h>   
  4. char* GetSubstring(char* strSource)  
  5. {  
  6.   char* strSubstring; //用于保存得到的子串,大小在找到最大子串后再确定,作为返回值  
  7.   int nLen;           //源字符串长度  
  8.   int nCurPos;        //当前统计字符串的头指针位置(相对于原字符串第一个字符的位置)  
  9.   int nCurCount;      //当前统计字符串的长度(有相同字符组成的子字符串)  
  10.   int nPos;          //当前最长的子串的头指针位置  
  11.   int nCount;        //当前最长的子串的长度  
  12.   
  13.   nLen = strlen(strSource);  
  14.   
  15.   //初始化变量  
  16.   nCount = 1;  
  17.   nPos = 0;  
  18.   nCurCount = 1;  
  19.   nCurPos = 0;  
  20.   
  21.   //遍历整个字符串  
  22.   for(int i = 1; i < nLen; i++)  
  23.   {  
  24.     if(strSource[i] == strSource[nCurPos])//如果当前字符与子串的字符相同,子串长度增1  
  25.       nCurCount++;  
  26.     else  //如果不相同,开始统计新的子串  
  27.     {  
  28.       if(nCurCount > nCount)//如果当前子串比原先最长的子串长,把当前子串信息(起始位置 + 长度)保留下来  
  29.       {  
  30.         nCount = nCurCount;  
  31.         nPos = nCurPos;  
  32.       }  
  33.       //长度复值为1,新串的开始位置为i  
  34.       nCurCount = 1;  
  35.       nCurPos = i;  
  36.     }  
  37.   }  
  38.   
  39.   //为返回的子串分配空间(长度为nCount,由于要包括字符串结束符\0,故大小要加1)    
  40.   strSubstring = (char*)malloc(nCount + 1);  
  41.   
  42.   //复制子串(用其他函数也可以)  
  43.   for(int i = 0; i < nCount; i++)  
  44.     strSubstring[i] = strSource[nPos + i];  
  45.   strSubstring[nCount] = '\0';  
  46.   
  47.   return strSubstring;  
  48. }   
  49.   
  50. int main()  
  51. {  
  52.   //输入一个字符串strSource  
  53.   char *strSource="absceeeecd";   
  54.   char* strSubstring = GetSubstring(strSource);  
  55.   
  56.   printf("最长子串为:%s\n长度为:%d",strSubstring,strlen(strSubstring));  
  57.   
  58.   //释放strSubstring  
  59.   free(strSubstring);  
  60. }  

 

三,求两个字符串的最大公共子字符串

        算法时间复杂度:O(n^2)

        思想:两个字符串先从第一个字串的第一个字符开始,依次与第二个字串的各个位置字串比较字串

                    需要记录下最长公共子串在str1中的位置和子串长度

  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<cassert>  
  4. using namespace std;  
  5. void findMaxSubstr(const char * str1 , const char * str2 , char * maxSubstr)  
  6. {  
  7.     assert((str1!=NULL)&&(str2!=NULL));  
  8.     assert(maxSubstr!=NULL);  
  9.     int maxPos=-1;  
  10.     int maxLen=0;  
  11.     int k;   
  12.     for(int i=0; i<strlen(str1); i++)  
  13.     {  
  14.         for(int j=0; j<strlen(str2); j++)  
  15.         {  
  16.             if(str1[i]==str2[j])  
  17.             {  
  18.                 for(k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)  
  19.                              ;  
  20.                     if(k>maxLen)  
  21.                     {  
  22.                         maxPos=i;  
  23.                         maxLen=k;  
  24.                     }  
  25.             }  
  26.         }  
  27.     }  
  28.     if(maxPos==-1)  
  29.     {  
  30.         maxSubstr[0]='\0';  
  31.     }  
  32.     else  
  33.     {  
  34.         memcpy(maxSubstr , str1+maxPos , maxLen);  
  35.         maxSubstr[maxLen]='\0';  
  36.     }  
  37. }  
  38. int main()  
  39. {  
  40.     char substr[20];  
  41.     findMaxSubstr("tianshuai" , "mynameistianshuai" , substr);  
  42.     cout<<substr<<endl;  
  43.     return 0;  
  44. }  

 

四,字符串查找并记录出现次数(普通与kmp)(观察strstr实现),替代

          函数原型:extern char *strstr(char *str1, char *str2);

   功能:找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符)

          使用:printf("%s",strstr("tianshuai","shuai")); 

                      输出:shuai

             实现:

  1. #include "stdio.h"  
  2. char *strstr(char *buf, char *sub)  
  3. {  
  4.     register char *bp;  
  5.     register char *sp;  
  6.   
  7.     if (!*sub)  
  8.         return buf;  
  9.     while (*buf)  
  10.    {  
  11.         bp = buf;  
  12.         sp = sub;  
  13.         do   
  14.         {  
  15.             if (!*sp)  
  16.                 return buf;  
  17.         } while (*bp++ == *sp++);  
  18.         buf += 1;//从下一个位置查找   
  19.     }  
  20.     return 0;  
  21. }  
  22. int main()  
  23. {  
  24.     printf("%s",strstr("tianshuai","tian"));   
  25.       
  26. }   

求子串的个数只需要略微更改一下就可以

  1. #include "stdio.h"  
  2.    
  3. int  strstr(char *buf, char *sub)  
  4. {  
  5.     register char *bp;  
  6.     register char *sp;  
  7.       
  8.     int count=0;  
  9.     int pos=0;   
  10.        
  11.     if (!*sub)  
  12.         return 0;  
  13.     while (*buf)  
  14.    {  
  15.         bp = buf;  
  16.         sp = sub;  
  17.         pos=0;   
  18.         do   
  19.         {  
  20.             pos++;   
  21.             if (!*sp)  
  22.             {  
  23.                 count++;   
  24.             }   
  25.                 //return buf;  
  26.         } while (*bp++ == *sp++);  
  27.           
  28.         buf += pos;//从下一个位置查找   
  29.     }  
  30.     return count;  
  31. }  
  32. int main()  
  33. {  
  34.     printf("%d",strstr("tianshuai,tianshuai,tianshui","tian"));   
  35.       
  36. }   

五,解析一个字符串,对字符串中重复出现的字符,只在第一次出现时保留,就是去除重复的字符。

         如:abdabbefgf -> abdefg。

         根据字符集,建立一个flag数组用来表示是否出现过。

六,给出一个函数来输出一个字符串的所有排列

        字典序生成算法问题:字典序

        采用next_permutation的算法思想,首先进行一个字符重排序找到按字典序最小的那个字符序列,以它为开端逐步生成所有排列。

七,翻转字符串

        
参考例子

八,从一个字符串中找出第一个不重复字符

         这个也比较简单,类似于5的方法。

九,去除字符串中相邻两个字符的重复

         这个应该等价于题目5

十,判断字符串是否含有回文字符子串

        枚举字符串的每个位置,作为回文串的中间位置(分偶数奇数两种情况),如果找到或者找不到都会立即停止,所以总的复杂度不超过O(n)

十一,求最长回文子串

         dp

                f[i][j] = f[i+1][j-1]

               s[i] == s[j]
         false s[i] != s[j]

        当然这里有一个小小的限定,f[i][j]表示以i,j为首尾的回文串能否构成。然后再找到一个最长的就可以算法,复杂度O(n^2)。实际上这个问题只要枚举回文串的中间位置就可以了,这样实际上就跟10一样了。不过10只需判断是否存在,这需要找到最长的那个。

当然这个问题还有更快的算法:http://richardxx.yo2.cn/articles/kmp和extend-kmp算法.html

------------------------------------------------------引用开始------------------------------------------------------------------------

             KMP的另外一个研究方向是Extend KMP(以下简称EK),它是说求得T与所有的S(i)的最长公共前缀(LCP),当然,要控制复杂度在线性以内。

             EK我第一次听说是07年baidu校园招聘的笔试题中,它当时的题目是求最长回文子串,当然这是一个耳熟能详,路人皆知可以用Suffix Array很好解决的问题。事后听一个同学说他写了三个算法:Suffix Array,Suffix Tree和EK,当时就不明白EK是什么东西,但又没当面问他,于是这个东西就搁置了很久。知道后来北大的月赛一道题说可以用EK来做,我才终于从03年林希德的文章中开始认识到它,就像KMP一样,这个算法也一下就吸引了我。
           设Q(i)表示T和S(i )的后缀的LCP,P(i)表示T和T(i)的后缀的LCP,那么和KMP一样,我们试图用P来求得Q,而P可以用自匹配求得,并且和求Q的过程相似。
           我以求P为例简要说明一下。P(2)就直接匹配即可,从i = 3开始,如下:
                      设k < i,E(k) = k + P(k) - 1,且对所有j < i,有E(k) >= E(j)。
                      那么,当E(k) >= i时,便可以推知T(i) = T( i - k + 1 ),于是如果P( i - k + 1 ) < E(k) - i + 1,那么P(i) = P( i - k + 1),否则P(i) >= P( i - k + 1 ),从E(k)开始向后匹配到E(i),有P(i) = E(i) - i + 1,并且更新 k = i;
                      还有就是E(k) < i,肯定有E(k) = i - 1,不过这个不重要,重要的是直接从i开始做暴力匹配即可得到E(i),则P(i) = E(i) - i + 1,更新k = i。
                      希望我把EK说清楚了,不过这种东西还是自己推导一下有意思,而且记忆周期更长。
           最后来罗列下题目。KMP的经典题目是POJ 2185,是要找最小覆盖矩形,如果你认为懂KMP了就去尝试它。EK的经典题是POJ 3376,有一定挑战;当然还有就是上面说的最长回文子串,提醒下用分治+EK来做是其中一种方法。
嗯,下次打算说下Suffix Array,主要是它那个传说中的线性DC3算法,不过我现在还没把握能不能简单的把它说清楚,姑且认为可以吧。

------------------------------------------------------引用结束------------------------------------------------------------------------

十二,字符串移位包含的问题

            题目:给定两个字符串S1与S2,要求判定S2是否能够被通过s1作循环移位得到的字符串包含,例如,给定s1=AABCD与S2=CDAA,返回true;给定s1=ABCD 与 s2=ACBD,返回false.

            直接枚举匹配或者比较s2能否匹配s1s1,以第一个为例也就是说比较AABCDAABCD和CDAA。

十三,strlen strcpy(注意重叠)

  1. #include "stdio.h"  
  2. #include "assert.h"  
  3.    
  4. char *<span>strcpy</span> (char *dest,const char *src)  
  5. {  
  6.     assert(src!=NULL);   
  7.     char *temp=dest;  
  8.     while((*dest++=*src++)!='\0')  
  9.             ;  
  10.     return dest;  
  11. }  
  12.   
  13. int main()  
  14. {  
  15.     char *dest;  
  16.     char *src="tianshuai";  
  17.     <span>strcpy</span>(dest,src);  
  18.     printf("%s",dest);   
  19. }   

上面这个比较复杂,再看FreeBsd的实现

 

 char *strcpy(char * __restrict to, const char * __restrict from)

 {

        char *save = to;

        for (; (*to = *from) != 0; ++from, ++to);

        return(save);

 }

十四,去掉中文中的英文字符

            主要根据字节的第一位进行判断。

十五,求一个字符串中连续出现次数最多的子串

            
参考博文

题目1:编码完成下面的处理函数。函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函数并返回值为5。(要求使用尽量少的时间和辅助空间)

  1. int MoveStar(char* str)  
  2. {  
  3.     assert(str != NULL);  
  4.     char *p1 = str+strlen(str)-1;  
  5.     char *p2 = str+strlen(str)-1;  
  6.     while(p1 >= str)  
  7.     {  
  8.         if(*p1 != '*')  
  9.             *p2-- = *p1;  
  10.         p1--;  
  11.     }  
  12.     int count = p2-p1;  
  13.     while(p2 >= str)  
  14.     {  
  15.         *p2-- = '*';  
  16.     }  
  17.     return count;  
  18. }  


题目2:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。

思路:我们首先对X和Y两段分别进行翻转操作,这样就能得到(X)T(Y)T,接着对(X)T(Y)T进行翻转操作,得到((X)T(Y)T)T=YX。

  1. void ReverseStr(char* pStart, char* pEnd)  
  2. {  
  3.     assert(pStart!=NULL && pEnd!=NULL);  
  4.   
  5.     while (pStart < pEnd)  
  6.     {  
  7.         char ch = *pStart;  
  8.         *pStart = *pEnd;  
  9.         *pEnd = ch;  
  10.         pStart++;  
  11.         pEnd--;  
  12.     }  
  13. }  
  14.   
  15. char* LeftRotateStr(char* str, int n)  
  16. {  
  17.     assert(str!=NULL && n>=0);  
  18.   
  19.     int length = strlen(str);  
  20.     if (length < n)  return;  
  21.     char* pFirstStart = str;  
  22.     char* pFirstEnd = str+n;  
  23.     char* pSecondStart = str+n+1;  
  24.     char* pSecondEnd = str+length-1;  
  25.   
  26.     ReverseStr(pFirstStart, pFirstEnd);  
  27.     ReverseStr(pSecondStart, pSecondEnd);  
  28.     ReverseStr(pFirstStart, pSecondEnd);  
  29.   
  30.     return str;  
  31. }  

参考资料:http://zhedahht.blog.163.comhttp://blog.csdn.net/crazy_zhao/article/details/6295487



          

抱歉!评论已关闭.