40.百度研发笔试题
2)一串首尾相连的珠子(m 个)，有 N 种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有 N 中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
思路：
先将表示珠子的串in复制两遍，变成inin这样就不用余数了。
我用char型表示不同的颜色。s表示当前起始点，e表示当前结束点。
用hash[256]来存放s到e不同颜色的珠子出现次数，避免char转数字的麻烦。
先把s、e都定位在开始，e向后遍历，直到遇到N种不同颜色。
之后遍历时，s定位到下一个颜色的位置，如果总颜色数变少，e再定位到总颜色数为N的位置。
直到s的位置超过链子长度m.
理论上会遍历两遍时间复制度为O(m)，空间上如果直接用整数表示不同的珠子需要O(N)
/*
40.2)
一串首尾相连的珠子(m 个)，有 N 种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有 N 中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
*/ #include <stdio.h>
#include <stdlib.h>
#include <string.h> int shortestlengh(char * in, char ** dst, int N)
{
//变成inin的形式，避免求余
int nlen = strlen(in);
char * in2 = (char *)malloc( * nlen * sizeof(char));
memcpy(in2, in, nlen * sizeof(char));
memcpy(in2 + nlen, in, nlen * sizeof(char)); int start = , end = nlen - ;
int shortestlen = nlen;
int hash[] = {};
int colornum = ;
int s = , e = -;
//遍历所有可能的起始点
while(s < nlen)
{
while(colornum < N && e <= * nlen) //找到在当前起点下找到所有颜色的结尾
{
e++;
if(hash[int(in2[e])] == )
{
colornum++;
}
hash[int(in2[e])]++;
}
//去掉前面相同的部分
while(in2[s] == in2[s + ])
{
s++;
hash[(int)in2[s]]--;
} //更新最短的串
if(shortestlen > e - s + )
{
shortestlen = e - s + ;
start = s;
end = e;
} //更新s,从下一个颜色开始
hash[(int)in2[s]]--;
if(hash[(int)in2[s]] == )
{
colornum--;
}
s = s + ;
} *(dst) = (char *)malloc(end - start + );
memcpy(*dst, in2 + start, end - start + );
(*dst)[end - start + ] = '\0'; //注意 free(in2); return end - start + ;
} int main()
{
char * s = "addcddcbccbba";
char * d = NULL;
int n = shortestlengh(s, &d, );
printf("%d\n%s\n", n, d);
return ;
}