40.百度研发笔试题（栈、算法）引用自：zp155334877
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。 并分析时间复杂度与空间复杂度。3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，
则中国人民 人民中国都有效。要求：*系统每秒的查询数量可能上千次；
*词语的数量级为10W； *每个词至多可以与1W个词搭配当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。
思路：
1）同100-2
2）这个我暂时只想到了O(n^2)的方法。就是遍历所有子串，然后判断这个子串是否包含了所有的颜色。，不过，我隐约还感觉到如果用后缀树可能会更高效，先采用2倍增法在O(n)时间内建立后缀树，然后只要找到包含所有颜色的最短前缀就行了。。
3）没看懂什么意思，不过看起来也只是泛泛的谈一下就可以了。
贴上第个问题的代码：
/*================================================*\40.百度研发笔试题（栈、算法）引用自：zp1553348771)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民 人民中国都有效。要求：*系统每秒的查询数量可能上千次；*词语的数量级为10W；*每个词至多可以与1W个词搭配当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。\*================================================*/#includeusing namespace std;void question2(){ int index[15] = {0,0,1,0,0,0,0,0,0,1,0,0,0,0,2}; int color[3] = {0}; int m = 15; int n = 3; int minLen = m; int beginRes = 0; int endRes = 0; int sum = 0; for(int begin = 0 ; begin < m ; ++begin){ for(int k = 0 ; k < n ; ++k){ color[k] = 0; } sum = 0; for(int end = begin ; end - begin < m ; ++end){ if(0 == color[index[end%m]]){ color[index[end%m]] = 1; ++sum; } if(n == sum){ if(end - begin < minLen){ minLen = end - begin; beginRes = begin; endRes = end%m; } break; } } } if(endRes > beginRes){ for(int i = beginRes ; i <= endRes ; ++i){ cout << index[i]; } cout << endl; }else{ for(int i = beginRes ; i<= endRes + m ; ++i){ cout << index[i%m]; } cout << endl; }}int main(){ question2(); system("pause"); return 1;}