一串首尾相連的珠子（m個），有N種顏色（N《=10），設(shè)計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。并分析時間復(fù)雜度與空間復(fù)雜度。
這道題在網(wǎng)上著名的帖子
微軟等公司數(shù)據(jù)結(jié)構(gòu)+算法面試100題系列 有詳細(xì)的描述，算法思想好像是
此題猶如在一個長字符串中找出其中一段，其中有一個字符集合的所有字符，并且這段字符串要最短，當(dāng)然，這個長字符串是首位相連的?？梢远x一個head和一個tail標(biāo)識字符串的頭和尾。定義一個數(shù)組charset【256】，用這個數(shù)組記錄集合中的字符出現(xiàn)的次數(shù)，之所以數(shù)組大小是256，大概是要用數(shù)組下標(biāo)來標(biāo)識字符。剛開始head=tail=0，tail++直到字符集合中所有的字符數(shù)都不為0為止，然后head++直到字符集合中某個字符的數(shù)變?yōu)?，這是便得到一個字符段。當(dāng)tail>=m時，tail=tail%m，當(dāng)head為m時算法結(jié)束.
- #include<stdio.h>
- #include<string.h>
-
- int isallin(int* chararray,char* charset);
-
- void findshortest(char* str,char* charset,int* begin,int* length);
-
- int main()
- {
- char* str = "fuckyouworld!whyamihere.";
- char* charset = "fu !";
- int begin,length;
- findshortest(str,charset,&begin,&length);
- printf("%d-%d",begin,length);
- getchar();
- }
- int isallin(int* chararray,char* charset)
- {
- int setlen = strlen(charset);
- int i;
- for(i = 0;i < setlen;i++)
- if(chararray[charset[i]] == 0)
- return 0;
- return 1;
- }
- void findshortest(char* str,char* charset,int* begin,int* length)
- {
- int head,tail;
- head = tail =0;
- int chararray[256] = {0};
- int stringlength = strlen(str);
- int shortestlength = stringlength;
- int shortesthead = 0;
- while(head < stringlength)
- {
-
- while(!isallin(chararray,charset)){
-
- if(head == 0 && tail == stringlength){
- *begin = 0;*length = 0;
- return;
- }
- chararray[str[tail % stringlength]] = chararray[str[tail % stringlength]] + 1;
- tail++;
- }
- while(isallin(chararray,charset)){
- chararray[str[head % stringlength]] = chararray[str[head % stringlength]] - 1;
- head++;
- }
- if(shortestlength > tail - head + 1){
- shortestlength = tail - head + 1;
- shortesthead = head - 1;
- }
- }
- *begin = shortesthead % stringlength;
- *length = shortestlength;
- }
|
