百度20140925面试算法题一道

本文主要是介绍百度20140925面试算法题一道，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：一个char数组只包含a,b,c,d,e五种字符，设计一种算法，找出一个包含五种字符的最小区间【a,b】，数组是循环的

O（n）算法：

/*
*一个char数组只包含a,b,c,d,e五种字符，
*设计一种算法，找出一个包含五种字符的最小区间【a,b】
*数组是循环的
*/
#include<iostream>
using namespace std;
void find(char array[], int size)
{int count[5];for(int i = 5; i <= size; i++)//区间宽度从5开始，遍历数组中所有区间{for(int index = 0; index < 5; index++)count[index] = 0;//将a,b,c,d,e的个数都初始化为0//下面遍历数组，对于前i个数，将对应的字符数加1//每遍历后面一个数，相当于把区间往后移一位，所以需要将前面区间的第一位字符从count数组中去除（减1）//对于每个区间，将count数组的数相乘就能判断是否包含了五种字符for(int begin = 0; begin < size + i - 1; begin++){int tmp_begin = begin;if(begin < i)count[array[begin] - 'a']++;else {count[array[begin - i] - 'a']--;if(begin >= size)tmp_begin = begin - size;count[array[tmp_begin] - 'a']++;}if(begin >= i - 1 && count[0] * count[1] * count[2] * count[3] * count[4] != 0)//a,b,c,d,e个数相乘，判断是否至少有一个为0{cout << '[' << begin - i + 1 << ',' << tmp_begin << ']' << endl;return;}}}
}

已知有O（n）算法，另外想。

这篇关于百度20140925面试算法题一道的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---