【100题】第四十题 百度研发笔试题
一，题目
1）设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。
2）一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
3）设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，则中国人民，人民中国都有效。要求：
*系统每秒的查询数量可能上千次；
*词语的数量级为10W；
*每个词至多可以与1W个词搭配
当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。
第一题解法：
借助辅助栈，保存最小值，且随时更新辅助栈中的元素。
例如：
1）push 2 6 4 1 5
stack A stack B（辅助栈）
4: 5 1 //push5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push进A的元素1小于B中栈顶元素2
2: 4 2 //push 4,min=p->[0]=2 |
1: 6 2 //push 6,min=p->[0]=2 |
0: 2 2 //push 2,min=p->[0]=2 |
push第一个元素进A，也把它push进B，当向A push的元素比B中的元素小， 则也push进B，即更新B。否则，不动B，保存原值。
向栈A push元素时，顺序由下至上。辅助栈B中，始终保存着最小的元素。
2）pop栈A中元素，5 1 4 6 2
A B ->更新
4: 5 1 1 //pop 5,min=p->[3]=1 |
3: 1 1 2 //pop 1,min=p->[0]=2 |
2: 4 2 2 //pop 4,min=p->[0]=2 |
1: 6 2 2 //pop 6,min=p->[0]=2 |
0: 2 2 NULL //pop2,min=NULL v
当pop A中的元素小于B中栈顶元素时，则也要popB中栈顶元素。
第二题解法：
题目类似于：给定一个很长的字符串str还有一个字符集比如{a,b,c}找出str里包含{a,b,c}的最短子串（这里str首尾相连）
比如，字符集是a,b,c，字符串是abdcaabc，则最短子串为abc
思路：先从index=0处搜索，每检查一颗珠子，响应的颜色数量+1，如果是新的颜色则总颜色数+1.
当颜色总数为n时，找到第一个满足条件的连续序列。
1>从该序列起始处搜索，若搜索处的颜色数量不为1，则表明该串还有别的珠子有该颜色，继续往前搜索并更新该序列，起始索引位置+1.
若搜索处颜色数量为1，停止搜索。
2>比较最佳序列长与当前序列长，更新最佳序列。记录当前序列起始位置。
从第一个满足条件的序列继续index++，并检查1,2条件。
如果不是首尾相连的：
#include <iostream>using namespace std;#define MAXN 10int colors[MAXN];//record the counter of one colorint colorsCounter;void find(int arr[],int len, int colorsNeed){ int bestStartIndex = 0; int bestLen = len; int lastStartIndex = 0; int firstFoundEnoughPearls = len; /*这里求的是没有绕过环的最小子串长度*/ for ( int i=0; i<len; ++i) { if (!colors[arr[i]]) colorsCounter++; colors[arr[i]]++; if (colorsCounter==colorsNeed) { firstFoundEnoughPearls = i; // } //if (firstFoundEnoughPearls!=len) //{ int j = lastStartIndex; while (colors[arr[j]]>1) { colors[arr[j]]--; ++j; } if (i-j+1<bestLen){ bestStartIndex = j; bestLen = i-j+1; if (bestLen==colorsNeed) break; } lastStartIndex = j; } } /*这里求的是绕过尾部的子串，然后到当前开始地方的递归*/ for (int i=0; i<firstFoundEnoughPearls; ++i) { if (!colors[arr[i]]) colorsCounter++; colors[arr[i]]++; int j = lastStartIndex; while (colors[arr[j]]>1) { colors[arr[j]]--; ++j; } if (i-j+1+len<bestLen) { bestStartIndex = j; bestLen = i-j+1+len; if (bestLen==colorsNeed) break; } lastStartIndex = j; } int offset = bestStartIndex; cout<<"bestStartIndex = "<<bestStartIndex<<endl; for (int i=0; i<bestLen;) { cout << arr[i+offset] << " "; ++i; if (i+offset>=len) offset = 0-i; } cout << endl;}int main(){ int arr[] = {1,2,3,3,2,1,4,1,2,3,2,6,4,5,2,6,2,3,4,1,2,5,2,3,4,5,6}; int m = sizeof(arr)/sizeof(arr[0]); int n = 6; find(arr,m,n); return 0;} 用二维向量表示10w个词之间的搭配信息。每个词-词搭配信息占用一个bit，共 10w * 10w bit，大概160MByte.分词完成后，可以在O(1)时间内完成搭配信息的查询。