首页 / 软件开发 / 数据结构与算法 / 百度研发笔试题解析： 一串首尾相连的珠子（m个），有N种颜色（N<=10）

百度研发笔试题解析： 一串首尾相连的珠子（m个），有N种颜色（N<=10）2014-12-24题目：

一串首尾相连的珠子（m个），有N种颜色（N<=10），

设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。

并分析时间复杂度与空间复杂度。

分析：

使用一个额外的数组存储颜色计数: colors[N]，并且定义一个颜色个数遍历int cn=0;

使用数组a[m]表示首尾相连的珠子。

遍历数组a，统计对应的颜色，如果等于颜色的个数等于N，记录下开始位置i，和结束位置j, 得到遍历的字符串长度j-i+1, 如果字符串的长度最小，则输出i,j。

时间复杂度为：O（n）,

空间复杂度为：O（1*N）

具体实现如下：

#include<iostream>#include<string.h>using namespace std;//m string a:0,1,...,m-1//N colors:0,1,...,N-1//#define m 10#define N 3int findmin（int a[m], int colors[N], int& begin, int& end）{begin = 0;end = -1;int i = 0;int j = 0;int cn = 0;int minlen = m;colors[a[0]] ++;cn ++;while（i < m）{//memset（colors, 0, N*sizeof（int））;//j = i;bool bl = false;while（j== 0 || j ！= i）{if（bl）{if（colors[a[j]] == 0）cn ++;colors[a[j]] ++;}bl = true;if（cn == N）{int len = j -i +1;if（len < 0）len += m;if（len < minlen）{begin = i;end = j;minlen = j - i + 1;}break;}j = （j+1）%m;}if（i == j && minlen == m）break;colors[a[i]] = colors[a[i]] - 1;if（colors[a[i]] == 0）cn --;i++;}return minlen;}int main（）{int a[m] = {2,1,0,1,1,2,1,0,1,1};int c[N] = {0,0,0};int begin= 0, end = 0;int minlen = findmin（a, c, begin, end）;int i = 0;cout << "string: ";while（i < m）{cout << a[i] << ",";i ++;}cout << " minlen: " << minlen << endl;cout << begin << "," << end << endl;}

输出如下：

string: 2,1,0,1,1,2,1,0,1,1, minlen: 3

0,2

作者：csdn博客 hhh3h