之所以说是一个解法，是因为这是我暂时能想到的线性时间复杂度的算法，需要遍历约2m遍，这里把算法列出来，仅供参考。
题目：
有一串首尾相连的珠子，共有m个，每一个珠子有一种颜色，并且颜色的总数不超过n(n<=10)，求连续的珠子的颜色总数为n时，长度最小的区间。可简述思路或者给出伪代码，并且给出时间和空间复杂度分析。（baidu 2011校园招聘笔试题目）
拿到这个题目，我首先想到的是暴力搜索。即对每个珠子，都搜索以该珠子为结尾的最短符合题意的序列。但是这样比较的时间复杂度特别高，应该是m的指数，显然是不可取的，通过简单的分析我们能够发现，在搜索过程中，我们进行了许多冗余的比较。本着空间换时间的想法，我们有没有办法把这些比较记录下来，然后去掉这些冗余呢？答案是肯定的。
我想到的一个算法，里面用到了一些动态规划的思想，可以在线性时间内完成题目。首先为了方便描述，让我们假设珠子不是首尾相连。让我们以数组a[m]来表示珠子的序列，用1-n数字来表示颜色，则算法思路如下：
- 定义一个数组least[m]；对于a[i]的元素，least[i]表示珠子序列中以珠子a[i]为结尾的包含所有颜色的最短序列的长度；
- 定义一个数组save[n+1]; 这个数组的元素save[i]表示颜色i上一次出现的位置，初始化为－1；注意这里的i表示颜色而不是珠子！
- 定义一个数组next[m]；对于a[i]的元素，next[i]表示当前珠子的颜色下一次出现的位置；初始化为－1；
- 定义两个指针 i 和 j ，初始化为0，即指向a[0]；
- 首先遍历一遍a[m]，将每个珠子的颜色下一次出现的位置填充到next[i]中；具体做法是利用数组save[n+1]保存颜色c上一次出现的位置d，当再次出现c时，将next[d]设置为当前位置。这部分可以在O(m)时间内完成，具体代码中还可以优化。
- 将指针j向右滑动
- 判断 i<j 和 ( a[i]==a[j] 或者 next[i] < j ) 两个条件是否成立，如果不成立，least[j]=j-i+1 ，然后执行6；如果成立，i++，继续执行7。（ 判断a[i]==a[j]是因为如果a[i]==a[j]，则a[i]-a[j]之间的序列不够成最短序列；判断next[i]<j的因为在a[i]到a[j]之间存在颜色a[i]，因此a[i]也不应该被包括在最短序列里。）
- 如果j = n，则遍历完成，找到least[m]中最小的数的位置，则就能找到符合题意的最小序列。
当然，我们需要考虑到珠子首尾相连。我们可以让j=n之后，从0开始重新循环，直到 i=n 或 j到达位置s，位置s表示从a[0]开始，第一个出现所有颜色的位置。
下面是我使用C语言实现的代码，在实际代码中，next[j]我是一边挪动 j 一边填充的。代码如下：
#include <stdio.h> #define CNUMBER 4 //颜色的个数 int find(int *a, int n){ int number = CNUMBER; //定义一个计数器，目的是找到上面所说的第一个出现所有颜色的位置s int save[number+1]; //颜色上一次出现的位置 int next[n]; //元素颜色下一次出现的位置 int least[n]; //以该元素结尾的最短序列 int i, j; for(i=0;i<CNUMBER+1;i++){ //初始化 save[i]=-1; } for(i=0;i<n;i++){ //初始化 next[i]=-1; } i = 0; for(j=0;j<n;j++){ if(number!=0) least[j]=-1; //将还没有出现所有颜色的位置的least设为－1，下面会用到 if(save[a[j]]==-1){ //save[i]为-1表明该颜色i第一次出现 save[a[j]]=j; number--; } else{ next[save[a[j]]]=j; //设置next save[a[j]]=j; //把save[i]设为当前位置，用于下一次使用 } while(i<j){ if(a[i]==a[j]||next[i]!=-1) //i++的条件 i++; else break; } if(number == 0 ) least[j]=j-i+1; //计算least } j=0; while(least[j]==-1 &&i<n ){ //这个循环的目的是为了满足首尾相接的条件而让j从头开始 next[save[a[j]]]=j; while(i<n){ if(a[i]==a[j]||(next[i]>i||next[i]<j)&&next[i]!=-1) //next[i]>i||next[i]<j 表示a[i]表示的颜色下次出现在i和j之间 i++; else break; } least[j]=j+n-i+1; j++; } for(i=0;i<n;i++) printf("%d ", least[i]); //我这里最终将所有least打印出来，可以更改下让把符合题意的序列打印出来 printf("\n"); } int main(){ int n; int a[100]; scanf("%d", &n); //n表示珠子的长度 int i; for(i=0;i<n;i++) scanf("%d", &a[i]); //输入珠子 find(a, n); } |
当然，这个算法未必就是一个很好的算法，如果你有更好的方法，欢迎留言讨论。
呵呵，你也去考试百度？怎么样，现在拿到百度的offer了吗
@Robbin 恩 拿到了 后来决定去那里了
楼主厉害，同是学计算机的，算是师兄了吧，我今年大二下，想问下毕业直接能够进百度的机会有多大呢？现在开始准备就业，需要做哪些准备？一直在考研还是工作之间犹豫。。。。。。
考研和就业完全是考自己喜好。百度不难进，尤其是现在大规模招人。本科生也有不少进去的，而且干的一点也都不差。不过研究生要多一些。多准备基础，多做算法题，ACM之类，适当做一些项目
请教一下，
你平时是不是很喜欢看算法的书什么的？有了一定的积累才能做到自己写算法吧？
@xx 呵呵。。我算法很一般，这些都不是什么比较难的算法，平时在实验室也不怎么用，就是为了找工作才看看的。如果平时注意积累，真工作的时候会很牛
正在看软件的笔试面试题。发现楼主的博客不错。顺便说一下我的想法。这个问题跟最小子序列和很像。我的思路也差不多，向后扫描时，尽量丢弃前面不需要的部分。
1、设一个position[n],表示每个颜色的球最后出现的位置，初试先设为-1
2、遍历珠子。遍历到第i个珠子时，将这个颜色的position[color] = i;然后看position，如果仍有-1表示还需继续遍历。如果都不是-1，那当前的最小串是max（position）-min（position）。并与先前记录的一个minlength比较，保留较小值。
不知是否正确，请指正
另外希望自己也能进入百度，呵呵
我有一个O(n)的解法，请楼主看看，这种思考是否严谨！http://blog.csdn.net/lzj509649444/article/details/7045946，这是我博客里面的解法。
#include
#include
using namespace std;
int main() {
string s;
cin >> s;
// get number of different colors
int a[255];
memset(a, 0, sizeof(a));
int colorn = 0;
for (int i = 0; i < s.size(); ++i)
if (a[s[i]] == 0)
a[s[i]] = 1, colorn++;
s += s.substr(0, s.size() - 1);
memset(a, 0xff, sizeof(a));
int n = s.size(), x = 0, y = -1, meetcolor = 0, retx = 0, rety = n -1;
while(++y < n - 1) {
if (a[s[y]] == -1)
meetcolor++;
a[s[y]] = y;
while(a[s[x]] != x) x++;
if (meetcolor == colorn && y - x < rety - retx)
retx = x, rety = y;
}
cout << s.substr(retx, rety - retx + 1) << endl;
return 0;
}