天天看點

一串首尾相連的珠子(m個),有N種顔色(N《=10),設計一個算法,取出其中一段,要求包含所有N中顔色,并使長度最短。并分析時間複雜度與空間複雜度

#include <iostream>
#define COLOR 3
#define LENGTH 10
using namespace std;
//假定m=10,n=3
int GetLength(int* zhuzi);//傳回一段包含所有顔色的長度
bool IsAllColor(int* color);//判斷是否含有所有顔色
int main()
{
	int zhuzi[LENGTH+1] = {1,2,1,2,3,1,1,2,2,3,0};//存放相應的顔色1~n,最後一位存放0,标記結束
	cout<<GetLength(zhuzi)<<endl;
	return 0;
}
int GetLength(int* zhuzi)
{
	int result = 0;
	int *p = zhuzi;
	int color[COLOR] = {0};//表示1~n每一種顔色的數目


	while(*p!=0&&!IsAllColor(color))
	{
		color[(*p++)-1]++;
		result++;
	}
	p = zhuzi + 1;
	if(IsAllColor(color))
		return result<GetLength(p)?result:GetLength(p);
	else
		return LENGTH;//表示沒有找到一個包含所有顔色的段,就傳回全長

}
bool IsAllColor(int* color)
{
	for(int i=0;i<COLOR;i++)
	{
		if(color[i]==0)
			return false;
	}
	return true;
}
           

繼續閱讀