一串长为M的珠子,珠子的颜色有N种(N<10)。求包含N种颜色的最短连续珠串。
创新互联建站科技有限公司专业互联网基础服务商,为您提供成都二枢服务器租用托管,高防主机,成都IDC机房托管,成都主机托管等互联网服务。//两个指针,开始的时候都指向某一个位置,移动前一个指针,直到两个指针直接包含了所有颜色的珠子。
//此时记下len。
//然后向前移动后面的指针,再调整最前面的指针,直到重新满足两个指针间包含了所有的颜色,比较此时的len和之前的len,取最小值。
//如此移动,直到后面的指针回到起始位置。
//时间复杂度是O(N),空间复杂度是O(1)
#includeusing namespace std; void Search(char* src,char* ch) { int varies = 0;//多少种颜色 char* begin = src; memset(ch, 0, sizeof(char) * 256); while (*begin++) { if (ch[*begin - '0']++ == 0) { ++varies; } } //此时varies存储共有多少种颜色 int MinLength = 0; int curLength = 0; char* prev = src; char* cur = src; int curVaries = 0; char* ret = NULL; memset(ch, 0, sizeof(char) * 256); while (1) { curLength = 0; curVaries = 0; cur = prev; memset(ch, 0, sizeof(char) * 256); while (curVaries != varies) { if (++ch[*cur - '0']==1) curVaries++; ++cur; ++curLength; if (*cur == '\0') cur = src; } if (MinLength == 0 || MinLength > curLength) { MinLength = curLength; ret = prev; } if (MinLength == varies) break;//得到最短的 ++prev; if (*prev =='\0') break; } int flag = 1; int index = 0; for (int i = 0; i < MinLength; ++i) { if (ret[i] == '\0') flag = 0; if (flag == 1) ch[i] = ret[i]; else ch[i] = src[index++]; } ch[MinLength] = '\0'; } void Test1() { char* src = "abbcdabcddddacgd"; char ch[256] = { 0 }; Search(src,ch); cout< 创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网站栏目:字符串匹配之通配符问题--创新互联
本文路径:http://cdxtjz.cn/article/ggoeo.html