之所以说是一个解法,是因为这是我暂时能想到的线性时间复杂度的算法,需要遍历约2m遍,这里把算法列出来,仅供参考。

题目:

有一串首尾相连的珠子,共有m个,每一个珠子有一种颜色,并且颜色的总数不超过n(n<=10),求连续的珠子的颜色总数为n时,长度最小的区间。可简述思路或者给出伪代码,并且给出时间和空间复杂度分析。(baidu 2011校园招聘笔试题目)

拿到这个题目,我首先想到的是暴力搜索。即对每个珠子,都搜索以该珠子为结尾的最短符合题意的序列。但是这样比较的时间复杂度特别高,应该是m的指数,显然是不可取的,通过简单的分析我们能够发现,在搜索过程中,我们进行了许多冗余的比较。本着空间换时间的想法,我们有没有办法把这些比较记录下来,然后去掉这些冗余呢?答案是肯定的。

我想到的一个算法,里面用到了一些动态规划的思想,可以在线性时间内完成题目。首先为了方便描述,让我们假设珠子不是首尾相连。让我们以数组a[m]来表示珠子的序列,用1-n数字来表示颜色,则算法思路如下:

  1. 定义一个数组least[m];对于a[i]的元素,least[i]表示珠子序列中以珠子a[i]为结尾的包含所有颜色的最短序列的长度;
  2. 定义一个数组save[n+1]; 这个数组的元素save[i]表示颜色i上一次出现的位置,初始化为-1;注意这里的i表示颜色而不是珠子!
  3. 定义一个数组next[m];对于a[i]的元素,next[i]表示当前珠子的颜色下一次出现的位置;初始化为-1;
  4. 定义两个指针 i 和 j ,初始化为0,即指向a[0];
  5. 首先遍历一遍a[m],将每个珠子的颜色下一次出现的位置填充到next[i]中;具体做法是利用数组save[n+1]保存颜色c上一次出现的位置d,当再次出现c时,将next[d]设置为当前位置。这部分可以在O(m)时间内完成,具体代码中还可以优化。
  6. 将指针j向右滑动
  7. 判断 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]也不应该被包括在最短序列里。)
  8. 如果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);
}

当然,这个算法未必就是一个很好的算法,如果你有更好的方法,欢迎留言讨论。

anyShare分享到:

9 Responses to “一个百度笔试中的首尾相连的珠子问题解法”

  1. Robbin says:

    呵呵,你也去考试百度?怎么样,现在拿到百度的offer了吗

  2. 小李 says:

    楼主厉害,同是学计算机的,算是师兄了吧,我今年大二下,想问下毕业直接能够进百度的机会有多大呢?现在开始准备就业,需要做哪些准备?一直在考研还是工作之间犹豫。。。。。。

    • sponge says:

      考研和就业完全是考自己喜好。百度不难进,尤其是现在大规模招人。本科生也有不少进去的,而且干的一点也都不差。不过研究生要多一些。多准备基础,多做算法题,ACM之类,适当做一些项目

  3. xx says:

    请教一下,
    你平时是不是很喜欢看算法的书什么的?有了一定的积累才能做到自己写算法吧?

    • sponge says:

      @xx 呵呵。。我算法很一般,这些都不是什么比较难的算法,平时在实验室也不怎么用,就是为了找工作才看看的。如果平时注意积累,真工作的时候会很牛

  4. gyro says:

    正在看软件的笔试面试题。发现楼主的博客不错。顺便说一下我的想法。这个问题跟最小子序列和很像。我的思路也差不多,向后扫描时,尽量丢弃前面不需要的部分。
    1、设一个position[n],表示每个颜色的球最后出现的位置,初试先设为-1
    2、遍历珠子。遍历到第i个珠子时,将这个颜色的position[color] = i;然后看position,如果仍有-1表示还需继续遍历。如果都不是-1,那当前的最小串是max(position)-min(position)。并与先前记录的一个minlength比较,保留较小值。
    不知是否正确,请指正
    另外希望自己也能进入百度,呵呵

  5. lzj509649444 says:

    我有一个O(n)的解法,请楼主看看,这种思考是否严谨!http://blog.csdn.net/lzj509649444/article/details/7045946,这是我博客里面的解法。

  6. aaa says:

    #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;
    }

Leave a Reply to lzj509649444

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).