Chinaunix首页 | 论坛 | 博客
  • 博客访问: 626277
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: C/C++

2013-06-27 17:42:52


【问题一
    删除字符串中的数字并压缩字符串。如字符串“abc123de4fg56”处理后变为“abcdefg”。注意空间和效率。
解答:
    设置两个指着pfast和plast,pfast进行遍历,如果遇到数字,则pfast++;反之,把pfast所指向的字符赋值给plast,然后二者均向前走一步。
    该方法只需要遍历一次,不需要开辟新的空间,时间复杂度为O(n)。
  1. //压缩字符串
  2. void Squasd(char *str)
  3. {
  4.     assert((str != NULL));

  5.     char *pfast = str;
  6.     char *plast = str;
  7.     
  8.     while(*pfast != '\0')
  9.     {
  10.         if(*pfast <= '9' && *pfast >= '0')
  11.         {    
  12.             pfast++;
  13.         }
  14.         else
  15.         {
  16.             *plast = *pfast;
  17.             plast++;
  18.             pfast++;
  19.         }
  20.     }
  21.     *plast = '\0';
  22. }

【问题二】
    编写一个函数,将字符串中的字符‘*’移动到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中的字符‘*’的数量。
    如原始串为:ab**cd**e*12,处理后为****abcde12,函数并返回值为5。要求尽量使用少的时间和辅助空间。
解答:
    设置两个指针,从后往前,进行扫描,时间复杂度为O(n)。
  1. //将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移
  2. void Swap(char *a, char *b)
  3. {
  4.     char tmp = *a;
  5.     *a = *b;
  6.     *b = tmp;
  7. }
  8. void Remove(char *str)
  9. {
  10.     assert((str != NULL));
  11.     int length = strlen(str);
  12.     char *pfast = str + length - 1;
  13.     char *plast = str + strlen(str) - 1;

  14.     while(pfast != str && plast != str)
  15.     {
  16.         //从后向前找到第一个*
  17.         while(*pfast != '*' && pfast != str)
  18.         {
  19.             pfast--;
  20.         }

  21.         //从该*开始,向前找到第一个非*
  22.         plast = pfast;
  23.         while(*plast == '*' && plast != str)
  24.         {
  25.             plast--;
  26.         }
  27.         Swap(&(*plast), &(*pfast));
  28.         pfast--;
  29.     }
  30. }

【问题三】
    求最大连续递增数字串。如“ads3sl456789DF3456ld345AA”中的“456789”。
解答
  1. #define MAX 100
  2. void FindMaxLong(char *str)
  3. {
  4.     if(str == NULL)
  5.     {
  6.         return;
  7.     }

  8.     int max = 0;            //记录最大长度    
  9.     int last = -1;            //记录上一个字符
  10.     int endindex = 0;        //记录最长递增数字串的开始位置
  11.     int len = strlen(str);
  12.     
  13.     int result[MAX];
  14.     result[0] = 0;

  15.     int i = 0;
  16.     for(i = 0; i < len; i++)
  17.     {
  18.         if( (str[i] >= '0' && str[i] <= '9') && (str[i] - '0' > last) )
  19.         {
  20.             last = str[i] - '0';
  21.             //注意这里开始时:result[i] = result[i - 1] + 1;
  22.             //当字符串第一个字符为数字时,会出现:result[0] = result[-1] + 1;
  23.             //所以修改为如下。
  24.             result[i + 1] = result[i] + 1;    
  25.             if(result[i + 1] > max)
  26.             {
  27.                 max = result[i + 1];
  28.                 endindex = i;
  29.             }
  30.         }
  31.         else
  32.         {
  33.             last = -1;
  34.             result[i] = 0;
  35.         }
  36.     }
  37.     
  38.     printf("最长递增数字串长度为:%dn", max);
  39.     printf("最长递增数字串为:n");
  40.     for(i = endindex - max + 1; i <= endindex; i++)
  41.     {
  42.         printf("%c ", str[i]);
  43.     }
  44.     printf("n");
  45. }

【附加题】
    找到一个字符串中的一个连续子串,这个子串不能有任何两个字符是相同的,并且这个子串是符合要求的最长的。
    例如,输入“abcbef”,输出“cbef”。
解法:
    时间复杂度为O(n)的算法,具体思路如下所示:
    以"abcbef"这个串为例子,用一个数组pos记录每个元素曾出现的下标,初始化为-1。从str[0]开始,依次考察每个字符,例如pos['a'] == 0,说明‘a'还没有出现过,令pos['a'] = 0,视为将’a'加入到当前串中,同时长度加+1,同理pos['b'] = 1,pos['c'] = 2,考察str[3],pos['b'] != -1,说明‘b'在前面已经出现过了,此时可得到一个不重复串“abc”,刷新当前的最大长度,然后更新pos['b']以及起始串位置。
    具体过程如下:
    (1)建立一个256个单元的数组,每一个单元代表一个字符,数组中保存上次该字符出现的位置;
    (2)依次读入字符串,同时维护数组的值;
    (3)如果遇到冲突的,考察当前起始串位置到冲突字符的长度,如果大于当前最大长度,则更新当前最大长度并维护冲突字符的位置,更新起始串的位置,继续第二步;
  1. //最长不重复的连续子串
  2. char* GetMaxSubStr(char *str)
  3. {
  4.     int i = 0;

  5.     //hash记录每个字符的出现位置
  6.     int hash[256];                
  7.     //初始化
  8.     for (i = 0; i < 256; i++)    
  9.     {
  10.         hash[i] = -1;
  11.     }

  12.     int CurrentStart = 0, CurrentLength = 0;
  13.     int MaxStart = 0, MaxEnd = 0;

  14.     int strLen = strlen(str);
  15.     
  16.     for(i = 0; i < strLen; i++)
  17.     {
  18.         int index = str[i];
  19.         if(CurrentStart > hash[index])            //如果没有重复
  20.         {
  21.             hash[index] = i;
  22.         }
  23.         else
  24.         {
  25.             CurrentLength = i - CurrentStart; //当前长度
  26.             if(CurrentLength > MaxEnd-MaxStart)//如果当前长度最长
  27.             {
  28.                 MaxEnd = i;
  29.                 MaxStart = CurrentStart;
  30.             }
  31.             CurrentStart = hash[index] + 1; //更新当前最长的起点
  32.             hash[index] = i;                 //更新字符出现的位置
  33.         }
  34.     }
  35.     if (MaxEnd == 0)                         //没有重复字符,返回源串
  36.     {
  37.         char* reStr = new char[strLen + 1];
  38.         strcpy(reStr, str);
  39.         return reStr;
  40.     }

  41.     CurrentLength = strLen - CurrentStart; //当前长度
  42.     if(CurrentLength > MaxEnd - MaxStart) //如果当前长度最长
  43.     {
  44.         MaxEnd = strLen;
  45.         MaxStart = CurrentStart;
  46.     }
  47.     //获取最大长度和最大连续不重复子串
  48.     int MaxLength = MaxEnd - MaxStart;
  49.     printf("长度为: %dn", MaxLength);
  50.     char* reStr = new char[MaxLength + 1];
  51.     memset(reStr, 0, MaxLength + 1);
  52.     strncpy(reStr, str + MaxStart, MaxLength);
  53.     return reStr;
  54. }

【问题五】
    已知一个字符串,比如“aderwsde”,寻找其中一个子字符串比如“sde”的个数。如果没有找到,则返回0;否则返回该子字符串的个数。
解答:
    利用strstr()或KMP算法进行匹配。

【问题六】
    给出一个函数来复制两个字符串 A 和 B。字符串 A 的后几个字节和字符串 B 的前几个字节重叠。
解答:
    分析:记住,这种题目往往就是考你对边界的考虑情况。
    具体思路没有想到。

【问题七】
    对称字符串的最大长度。
    输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。
解答:
    参考:http://www.cnblogs.com/wolenski/archive/2012/07/08/2581837.html
    分析:可能很多人都写过判断一个字符串是不是对策的函数,这个题目可以看成是该函数的加强版。
  
引子:判断字符串是否对称
    要判断一个字符串是不是对称的,不是一件很难的事情。我们可以先得到字符串的首尾两个字符,判断是不是相等。如果不相等,那么该字符串肯定不是对称的;否则继续判断里面的两个字符是不是相等。基于这个思路,写出如下代码:
  1. ////////////////////////////////////////////////////////////////
  2.  // Whether a string between pBegin and pEnd is symmetrical?
  3.  ////////////////////////////////////////////////////////////////
  4.  bool IsSymmetrical(char* pBegin, char* pEnd)
  5.  {
  6.         if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
  7.                return false;
  8.   
  9.         while(pBegin < pEnd)
  10.         {
  11.                if(*pBegin != *pEnd)
  12.                       return false;
  13.   
  14.                pBegin++;
  15.                pEnd --;
  16.         }
  17.   
  18.         return true;
  19.  }
    要判断一个字符串pstring是不是对策的,我们只需要调用IsSymmetrical(pstring, &pstring[strlen(pstring) - 1])就可以了。
解法一:O(n^3)的算法
    现在我们试着得到对称字符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串,并逐个判断是不是对策的。如果一个字符串是对称的,我们就得到它的长度。这样经过比较,就能得到最长的对称子字符串的长度了。于是,可以写出如下代码:
  1. ////////////////////////////////////////////////////////////////
  2.  // Get the longest length of its all symmetrical substrings
  3.  // Time needed is O(T^3)
  4.  ////////////////////////////////////////////////////////////////
  5.  int GetLongestSymmetricalLength_1(char* pString)
  6.  {
  7.         if(pString == NULL)
  8.                return 0;
  9.   
  10.         int symmeticalLength = 1;
  11.   
  12.         char* pFirst = pString;
  13.         int length = strlen(pString);
  14.         while(pFirst < &pString[length - 1])
  15.         {
  16.                char* pLast = pFirst + 1;
  17.                while(pLast <= &pString[length - 1])
  18.                {
  19.                       if(IsSymmetrical(pFirst, pLast))
  20.                       {
  21.                             int newLength = pLast - pFirst + 1;
  22.                             if(newLength > symmeticalLength)
  23.                                    symmeticalLength = newLength;
  24.                       }
  25.   
  26.                       pLast++;
  27.                }
  28.   
  29.                pFirst++;
  30.         }
  31.   
  32.         return symmeticalLength;
  33.  }
    我们来分析一下上述方法的时间效率。由于我们需要两重while循环,每重循环需要O(n)的时间。另外,我们在循环中调用了IsSymmetrical,每次调用也需要O(n)的时间。因此整个函数的时间效率是O(n^3)。
    通常O(n^3)不会是一个高效的算法。如果我们仔细分析上述方法的比较过程,我们就能发现其中有很多重复的比较。假设我们需要判断一个子字符串具有aAa的形式(A是aAa的子字符串,可能含有多个字符)。我们先把pFirst指向最前面的字符a,把pLast指向最后面的字符a,由于两个字符相同,我们在IsSymtical函数内部向后移动pFirst,向前移动pLast,以判断A是不是对称的。接下来若干步骤之后,由于A也是输入字符串的一个子字符串,我们需要再一次判断它是不是对称的。也就是说,我们重复多次地在判断A是不是对称的。
    造成上述重复比较的根源在于IsSymmetrical的比较是从外向里进行的。在判断aAa是不是对称的时候,我们不知道A是不是对称的,因此需要花费O(n)的时间来判断。下次我们判断A是不是对称的时候,我们仍然需要O(n)的时间。

解法二:O(n^2)的算法
    如果换一种思路,我们从里向外来判断。也就是先判断字符串A是不是对称的。如果A不是对称的,那么该子字符串两端各延长一个字符得到字符串肯定不是对称的。如果A对称,那么只需要判断A两端延长的一个字符是不是相等,如果相等,则延长后的字符串是对称的。因此在知道A是否对称之后,只需要O(1)的时间就知道aAa是不是对称的。
    可以根据从里向外的思路写出如下代码。
  1. ////////////////////////////////////////////////////////////////
  2.  // Get the longest length of its all symmetrical substrings
  3.  // Time needed is O(T^2)
  4.  ////////////////////////////////////////////////////////////////
  5.  int GetLongestSymmetricalLength_2(char* pString)
  6.  {
  7.         if(pString == NULL)
  8.                return 0;
  9.   
  10.         int symmeticalLength = 1;
  11.        
  12.         char* pChar = pString;
  13.         while(*pChar != '')
  14.         {
  15.                // Substrings with odd length
  16.                char* pFirst = pChar - 1;
  17.                char* pLast = pChar + 1;
  18.                while(pFirst >= pString && *pLast != '' && *pFirst == *pLast)
  19.                {
  20.                       pFirst--;
  21.                       pLast++;
  22.                }
  23.   
  24.                int newLength = pLast - pFirst - 1;
  25.                if(newLength > symmeticalLength)
  26.                       symmeticalLength = newLength;
  27.   
  28.                // Substrings with even length
  29.                pFirst = pChar;
  30.                pLast = pChar + 1;
  31.                while(pFirst >= pString && *pLast != '' && *pFirst == *pLast)
  32.                {
  33.                       pFirst--;
  34.                       pLast++;
  35.                }
  36.   
  37.                newLength = pLast - pFirst - 1;
  38.                if(newLength > symmeticalLength)
  39.                       symmeticalLength = newLength;
  40.   
  41.                pChar++;
  42.         }
  43.   
  44.         return symmeticalLength;
  45.  }
    回帖中指出了原文的问题:
    char *pChar =pString
           char* pFirst = pChar - 1;时,pFirst指向一个未知区域了,那后面的int newLength = pLast - pFirst - 1;是不是有问题!
    循环可以不用在pChar = pString处开始,而在pChar = pString + 1处开始,那么奇数长度的代码不变,偶数长度的代码改一下就行了:
           pFirst = pChar - 1;
           pLast = pChar ;
    由于子字符串的长度可能是奇数也可能是偶数。长度是奇数的字符串是从只有一个字符的中心向两端延长出来,而长度为偶数的字符串是从一个有两个字符的中心向两端延长出来。因此我们的代码要把这种情况都考虑进去。
    在上述代码中,我们从字符串的每个字符串两端开始延长,如果当前的子字符串是对称的,再判断延长之后的字符串是不是对称的。由于总共有O(n)个字符,每个字符可能延长O(n)次,每次延长时只需要O(1)就能判断出是不是对称的,因此整个函数的时间效率是O(n2)。
    



    













阅读(1497) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~