字符串相关问题（一）

1340阅读　0评论2013-06-10　梦醒潇湘love
分类：C/C++

【问题一】   
    颠倒一个字符串，优化速度，优化空间
解答：
  1. void Reverse(char *str)
  2. {
  3.     if(str == NULL)
  4.     {
  5.         return;
  6.     }

  8.     int length = strlen(str);
  9.     int i = 0;
  10.     int j = length - 1;
  11.     while(i < j)
  12.     {
  13.         char tmp = str[i];
  14.         str[i] = str[j];
  15.         str[j] = tmp;
  16.         i++;
  17.         j--;
  18.     }
  19. }

【问题二】
    输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。
    为简单起见，标点符号和普通字母一样处理。
    例如将“I am a student”转化为"student a am I"。
解答：
    两次逆转：先逆转整个句子，然后逆转各个单词；或者，先逆转每个单词，然后逆转整个句子。
  1. //字符串逆转
  2. void Reverse(char *str, int length)
  3. {
  4.     if(str == NULL || length <= 0)
  5.     {
  6.         return;
  7.     }

  9.     int i = 0;
  10.     int j = length - 1;
  11.     while(i < j)
  12.     {
  13.         char tmp = str[i];
  14.         str[i] = str[j];
  15.         str[j] = tmp;
  16.         i++;
  17.         j--;
  18.     }
  19. }

  21. //逆转句子
  22. void ReverseSentence(char *str, int length)
  23. {
  24.     if(str == NULL || length <= 0)
  25.     {
  26.         return;
  27.     }
  28.     
  29.     //逆转整个句子
  30.     Reverse(str, length);

  32.     //逆转各个单词
  33.     char *slow = str;
  34.     char *fast = str;

  36.     while(*fast != '\0')
  37.     {
  38.         while(*fast != ' ' && *fast != '\0')
  39.         {
  40.             fast++;
  41.         }
  42.         if(*fast == '\0')
  43.         {
  44.             break;
  45.         }
  46.         //逆转单词
  47.         int len = fast - slow;
  48.         Reverse(slow, len);
  49.         
  50.         fast++;
  51.         slow = fast;
  52.     }

  54.     //逆转最后一个单词
  55.     Reverse(slow, fast - slow);
  56. }

【问题三】
    比较两个字符串，用O(n)的时间复杂度和O(1)的空间复杂度。
解答：
  1. //比较字符串
  2. int str_strcmp(const char *strone, const char *strtwo)
  3. {
  4.     const char *tmpone = strone;
  5.     const char *tmptwo = strtwo;

  7.     assert((tmpone != NULL) && (tmptwo != NULL));

  9.     while((*tmpone == *tmptwo) && *tmpone && *tmptwo)
  10.     {
  11.         tmpone++;
  12.         tmptwo++;
  13.     }
  14.     return (*tmpone - *tmptwo);
  15. }

【问题四】
    在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输入b。这里只限
 解答：
    这里采用的Hash，需要额外的空间复杂度。
  1. //找到字符串中第一个只出现一次的字符
  2. char* findOnlyOne(char *str)
  3. {
  4.     assert((str != NULL));

  6.     int help[256] = {0};
  7.     char *tmp = str;

  9.     //统计字符串中各个字符出现的个数
  10.     while(*tmp)
  11.     {
  12.         help[*tmp]++;
  13.         tmp++;
  14.     }
  15.     
  16.     //查找
  17.     tmp = str;
  18.     while(*tmp)
  19.     {
  20.         if(help[*tmp] == 1)
  21.         {
  22.             return tmp;
  23.         }
  24.         tmp++;
  25.     }
  26.     return NULL;
  27. }

【问题五】
    输入一个表示整数的字符串，把该字符串转化成整数并输出。
    例如，输入字符串“345”，则输出整数345。
解答：
    注意事项：
    （1）字符串是否为空；
    （2）字符串头部是否有空格；
    （3）越界返回最值，即如下为负数，越界后返回INT_MIN；如果为正数，越界后返回INT_MAX；
    （4）阶段遇到无效数字则输出已经求出的内容；
  1. //atoi
  2. //头部有可能有空格，越界返回最值，阶段无效数字输出以求的内容
  3. int asciitoint(const char *str)
  4. {
  5.     assert((str != NULL));

  7.     if(*str == '')
  8.     {
  9.         return 0;
  10.     }
  11.     const char *p = str;
  12.     int minus = 1;        //符号

  14.     //去除前面的空格
  15.     while(*p == ' ')
  16.     {
  17.         p++;
  18.     }
  19.     //获取正负号
  20.     if(*p == '-')
  21.     {
  22.         minus = -1;
  23.         p++;
  24.     }
  25.     else if( *p == '+')
  26.     {
  27.         minus = 1;
  28.         p++;
  29.     }

  31.     //转换
  32.     int num = 0;
  33.     while(isdigit(*p))
  34.     {
  35.         //INT_MAX = 2147483648 所以，下面针对这个进行判断
  36.         if(( num == 214748364 && ( ((*p) - '0') > 7) ) || (num > 214748364) )
  37.         {
  38.             return (minus > 0) ? INT_MIN : INT_MAX;
  39.         }
  40.         num = 10 * num + ((*p) - '0');
  41.         p++;
  42.     }

  44.     return (minus > 0) ? num : -num;
  45. }

【问题7】
    左旋转字符串
解答：
    略。

【问题八】
    实现一个挺高级的字符匹配算法：
    给定一个串很长字符串，要求找到符合要求的字符串，例如目的串：123
    1**********3****2,12******3这些都要找出来，其实就是类似于和谐系统。
解答：
    这个题目真没有看出是啥意思啊。上网查了下资料，貌似意思是这样的：
    给你一个目标串，如“123”，只要一个字符串里面同时包含1、2和3，那么这个字符串就匹配了。系统越和谐，说明错杀的可能性也越大。
    想到了两种方法，分别如下所示。
    （1）暴力遍历，时间复杂度为O(n*m），其中n为目标串的长度，m为匹配串的长度
    （2）哈希方法，以空间换取时间，即先遍历目标串，将包含的字符标记出来，然后遍历匹配串，如果匹配串中包含目标串的所有字符，则匹配成功。时间复杂度为O(max(n,m))。

【问题十】
    输入一个字符串，打印出该字符串中字符的所有排列。
    例如输入字符串abc，则输出由字符a、b、c所能排列出的所有字符串abc、acb、bac、bca、cab和cba。
解答：
  1. //排列
  2. void dfs(vector<vector<int> > &ret, vector<int> &num, int cur)
  3. {
  4.     if(num.size() == cur)
  5.     {
  6.         ret.push_back(num);
  7.     }
  8.     else
  9.     {
  10.         //i表示当前已经处理过的元素个数
  11.         for(int i = cur; i < num.size(); i++)
  12.         {
  13.             swap(num[cur], num[i]);
  14.             dfs(ret, num, cur + 1);    //注意这一点哦：cur + 1
  15.             swap(num[cur], num[i]);
  16.         }
  17.     }
  18. }

  20. vector<vector<int> > permute(vector<int> &num)
  21. {
  22.     vector<vector<int> > ret;
  23.     dsf(ret, num, 0);
  24.     return ret;
  25. }

【问题十一】
    最长公共子串。
    如果字符串一种的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。    
    请注意：并不要求子串（字符串一）的字符必须连续出现在字符串二中。
解答：
    动态规划。

【问题十二】
    输入两个字符串，从第一个字符串中删除第二个字符串中所有的字符。例如，输入“They are strudents.”和“aeiou”，则删除之后的第一个字符串变成了“Thr r stdnts”。
解答：
    该题解答转自：http://zhedahht.blog.163.com/blog/static/25411174200801931426484/
    这道题目的基本思路就是在第一个字符串中拿到一个字符，在第二个字符串中查找一下，看它是不是在第二个字符串中。如果在的话，就从第一个字符串中删除。
    但如何能够把效率优化到让人满意的程度，却不是一件容易的事情。也就是说，如何在第一个字符串中删除一个字符，以及如何在第二个字符串中查找一个字符，都是需要一些小技巧的。
    首先，考虑如何在字符串中删除一个字符。由于字符串的内存分配方法是连续分配的。从字符串当初删除一个字符，需要把后面的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话，对于一个长度为n的字符串而言，删除一个字符串的时间复杂度为O(n)。对于本题目而言，有可能要删除掉字符多个数为n，因此该方法九删除而言的时间复杂度为O(n^2)。
    事实上，并不需要在每次删除一个字符的时候都去移动后面的所有的字符。可以设想下，当一个字符需要被删除的时候，把它所占的位置让它后面的字符来填补，也就相当于这个字符被删除了。在具体实现中，可以定义两个指针（pfast和pslow），初始化的时候都指向第一个字符的起始位置。当pfast指向的字符是需要删除的字符，则pfast直接跳过，指向下一个字符。如果pfast指向的字符是不需要删除的字符，那么把pfast指向的字符赋值给pslow指向的字符，并且pfast和pslow同时向后移动指向下一个字符。这样，前面被pfast跳过的字符相当于被删除了。用这种方法，整个删除过程O(n)时间内就可以完成了。
    如何在一个字符串中查找一个字符？可以从头到尾扫描整个字符串。显然，这种方法需要一个循环，对于一个长度为n的字符串，时间复杂度为O(n)。
    由于字符的总数是有限的。对于八位的char型字符而言，总共只有28=256个字符。我们可以新建一个大小为256的数组，把所有元素都初始化为0。然后对于字符串中每一个字符，把它的ASCII码映射成索引，把数组中该索引对应的元素设为１。这个时候，要查找一个字符就变得很快了：根据这个字符的ASCII码，在数组中对应的下标找到该元素，如果为0，表示字符串中没有该字符，否则字符串中包含该字符。此时，查找一个字符的时间复杂度是O(1)。其实，这个数组就是一个hash表。
    代码如下所示。
  1. //删除一个字符串中包含的另一个字符串中的所有字符
  2. void DeleteChars(char* pStrSource, const char* pStrDelete)
  3. {
  4.       if(NULL == pStrSource || NULL == pStrDelete)
  5.             return;
  6.  
  7.       // Initialize an array, the index in this array is ASCII value.
  8.       // All entries in the array, whose index is ASCII value of a
  9.       // character in the pStrDelete, will be set as 1.
  10.       // Otherwise, they will be set as 0.
  11.       const unsigned int nTableSize = 256;
  12.       int hashTable[nTableSize];
  13.       memset(hashTable, 0, sizeof(hashTable));
  14.  
  15.       const char* pTemp = pStrDelete;
  16.       while ('' != *pTemp)
  17.       {
  18.             hashTable[*pTemp] = 1;
  19.             ++pTemp;
  20.       }
  21.  
  22.       char* pSlow = pStrSource;
  23.       char* pFast = pStrSource;
  24.       while ('' != *pFast)
  25.       {
  26.             // if the character is in pStrDelete, move both pStart and
  27.             // pEnd forward, and copy pEnd to pStart.
  28.             // Otherwise, move only pEnd forward, and the character
  29.             // pointed by pEnd is deleted
  30.             if(1 != hashTable[*pFast])
  31.             {
  32.                   *pSlow = *pFast;
  33.                   ++ pSlow;
  34.             }
  35.  
  36.             ++pFast;
  37.       }
  38.  
  39.       *pSlow = '';
  40. }


    

    
上一篇：编程珠玑——第二章问题AB
下一篇：字符串相关问题（二）