趋势科技2011校园招聘的一道编程笔试题

题目：编写一个函数int search(char *text)，text为输入的字符串，从字符串中找出一个最长的不含重复字符的子字符串，例如“axdbx”,返回4，子字符串为“axdb”，而“axdbxce”,返回5，子字符串为“dbxce”。

以下是我的答案，当然，较当时答题时的答案少有改动，但思路是一样的，毕竟答题时没有环境让我去debug。该算法时间复杂度为O(n)。并且不需要反复重置pos数组，每次访问到重新赋值即可。

下载: search.cpp
  1. #include <iostream.h>
  2. #include <string.h>
  3.  
  4. int search(char *text)
  5. {
  6.     int pos[256]; //用于记录字符最近一次出现的位置，使用ASC码做索引
  7.     int maxL = 0;   //记录最大长度
  8.     int start = 0;   //记录连续字符串的起始位置
  9.     int end = strlen(text), i, tL;  //end为字符串text上界
  10.     for (i=0; i<128; i++) pos[i] = -1;  //为每个字符初始化位置
  11.    
  12.     for (i=0; i<end; i++)   //遍历字符串
  13.     { 
  14.         int index = text[i];   //得到当前字符索引
  15.         if (pos[index] >= start)    //当前字符在起始位置之后出现过，则出现重复
  16.         {
  17.             tL = i - start;         //计算长度
  18.             if (tL > maxL) maxL = tL;  //若大于maxL，则记录
  19.            
  20.             start = pos[index] + 1;    //重置start位置，为重复的字符之后一个位置
  21.         }
  22.        
  23.         pos[index] = i;              //记录当前字符位置
  24.     }
  25.  
  26.     //末尾处理
  27.     tL = i - start;
  28.     if (tL > maxL) maxL = tL;
  29.  
  30.     return maxL;
  31. }
  32.  
  33. void main()
  34. {
  35.     char a[]="xabc123eDd56xesdADBfjkg";
  36.  
  37.     cout<<search(a)<<endl;
  38. }

Joke.li 原创

转载请注明出处