1
精选微软等公司数据结构精选微软等公司数据结构精选微软等公司数据结构精选微软等公司数据结构++++算法面试算法面试算法面试算法面试100100100100 题题题题
---------------- 答案答案答案答案((((第第第第 21-40 题题题题)))) V0.3 版版版版
作者前言：作者前言：作者前言：作者前言：
1.首先恭喜你，你确实得到了一份不错的资源。
送给你一句话，饮水当思源。
2.本来可以把这份第 21-40的答案弄成
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
形式的，
那样的话，大家可以直接复制黏贴其中的源码，直接上机验证。
//虽然其中大部分源码，我已经编译调试了，能保证基本的精准。
3.但我实在实在无法忍受大量大量的人，随意任意转载，
却不注明作者本人我 和出处，有的甚至私自据为己有。所以..见谅。
还是这句话，展示自己的思考结果，是一种骄傲。
其它资源，下载地址：
[第 1 题-60题汇总]微软等数据结构+算法面试 100题
http://download.csdn.net/source/2826690
[答案V0.2版]精选微软数据结构+算法面试 100 题[前 20题]//修正
http://download.csdn.net/source/2813890
//此份答案是针对最初的V0.1版本，进行的校正与修正。
[答案V0.1版]精选微软数据结构+算法面试 100 题[前 25题]
http://download.csdn.net/source/2796735
[第二部分]精选微软等公司结构+算法面试 100题[前 41-60 题]：
http://download.csdn.net/source/2811703
[第一部分]精选微软等公司数据结构+算法经典面试 100题[1-40题]
http://download.csdn.net/source/2778852
更多资源，下载地址：
http://v_july_v.download.csdn.net/
若你对以下答案，有任何问题，欢迎联系我：
My E-mail：
zhoulei0907@yahoo.cn
或者，直接回复于此帖上：
[推荐] [整理]算法面试：精选微软经典的算法面试 100题[前 40-60题]
http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html
July、2010年 11月 14日，晚，于东华理工。
2
第 21212121题
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列 1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
//此题与第 14 题差不多，再次不做过多解释。
//July、2010/10/22。
#include
#include
using namespace std;
void qiujie(int sum, int n)
{
static list ilist;
if(n < 1 || sum < 1)
return;
if(sum > n)
{
ilist.push_front(n);
qiujie(sum-n, n-1);
ilist.pop_front();
qiujie(sum, n-1);
}
else
{
cout<::iterator it = ilist.begin(); it != ilist.end(); ++it)
cout << " " << *it;
cout << endl;
}
}
int main()
{
int m, n;
cout<<"请输入你要等于多少的数值m:"<>m;
cout<<"请输入你要从 1.....n数列中取值的 n："<>n;
qiujie(m,n);
return 0;
}
Administrator
附注
在计算组合的时候，怎么知道还有多少个数字要加，给出的参考代码有问题
3
///////////////////////////////////////////
请输入你要等于多少的数值m:
10
请输入你要从 1.....n数列中取值的 n：
8
2 8
3 7
4 6
1 4 5
2 3 5
1 2 3 4
Press any key to continue
///////////////////////////////////////
第 22222222题：
有 4 张红色的牌和 4 张蓝色的牌，主持人先拿任意两张，
再分别在A、B、C 三人额头上贴任意两张牌，
A、B、C 三人都可以看见其余两人额头上的牌，
看完后让他们猜自己额头上是什么颜色的牌，
A 说不知道，B说不知道，C 说不知道，然后 A说知道了。
请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？
//July、2010/10/22
//今是老妈生日，祝福老妈，生日快乐。!:).
4张 r 4张 b
有以下 3 种组合：
rr bb rb
1.B，C 全是一种颜色
B C A
bb.rr bb.rr
2.
B C A
bb rr bb/RR/BR,=>A:BR
rr bb =>A:BR
4
3.
B C A
BR BB RR/BR, =>A:BR
//推出A:BR 的原因，
//如果 A 是 RR，
//那么，当ABC 都说不知道后，B 最后应该知道自己是 BR 了。
//因为 B 不可能 是 RR 或 BB。
4.
B C A
BR BR BB/RR/BR
//推出A:BR 的原因
//如果，A是 BB，那么 B=>BR/RR，
//如果 B=>RR,那么一开始，C就该知道自己是 BR 了。
//如果 B=>BR,
//最后，也还是推出=>A:BR
//至于程序，暂等高人。
第 23232323题：
用最简单， 最快速的方法计算出下面这个圆形是否和正方形相交。"
3D 坐标系 原点(0.0,0.0,0.0)
圆形:
半径 r = 3.0
圆心 o = (*.*, 0.0, *.*)
正方形:
4个角坐标;
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
*/
参考：
http://www.cssdn.net/thread-10486-1-2.html
5
第 24242424题：
1.反转链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
2.合并链表。
pPrev<-pNode<-pNext
ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL) //pNode<=>m
{
ListNode* pNext = pNode->m_pNext; //n保存在 pNext 下
//如果 pNext 指为空，则当前结点 pNode 设为头。
if(pNext == NULL)
pReversedHead = pNode;
// reverse the linkage between nodes
pNode->m_pNext = pPrev;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
或者，这样写：
head->next -> p-> q
template
Node* Reverse(Node* head)
{
p=head->next;
while(p)
{
q=p->next; //p->next先保存在 q下
p->next=head->next; //p掉头指向 head->next
head->next=p; //p赋给 head->next
p=q; //q赋给 p。
//上俩行即，指针前移嘛...
}
return head;
6
第 25252525题：
写一个函数,它的原形是 int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数 outputstr所指内存。
例如："abcd12345ed125ss123456789"的首地址传给 intputstr 后，函数将返回 9，
outputstr所指的值为 123456789
//leeyunce
这个相对比较简单，思路不用多说，跟在序列中求最小值差不多。未经测试。有错误欢迎指
出。
int continumax(char *outputstr, char *intputstr)
{
int i, maxlen = 0;
char * maxstr = 0;
while (true)
{
while (intputstr && (*intputstr<'0' || *intputstr>'9')) //skip all non-digit characters
{
intputstr++;
}
if (!intputstr) break;
int count = 0;
char * tempstr = intputstr;
while (intputstr && (*intputstr>='0' && *intputstr<='9')) //OK, these characters are
digits
{
count++;
intputstr++;
}
if (count > maxlen)
{
maxlen = count;
maxstr = tempstr;
}
}
for (i=0; i(strlen(pStr));
8
if(nLength > 0 || n == 0 || n > nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the strint
ReverseString(pSecondStart, pSecondEnd);
// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);
}
}
return pStr;
}
// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
9
27.27.27.27.跳台阶问题
题目：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。
求总共有多少总跳法，并分析算法的时间复杂度。
首先我们考虑最简单的情况。如果只有 1 级台阶，那显然只有一种跳法。
如果有 2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳 1级；另外一种就是一
次跳 2 级。
现在我们再来讨论一般情况。我们把 n 级台阶时的跳法看成是 n 的函数，记为 f(n)。
当 n>2 时，第一次跳的时候就有两种不同的选择：一是第一次只跳 1 级，
此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目，即为 f(n-1)；
另外一种选择是第一次跳 2级，此时跳法数目等于后面剩下的 n-2级台阶的跳法数目，即为
f(n-2)。
因此 n 级台阶时的不同跳法的总数 f(n)=f(n-1)+(f-2)。
我们把上面的分析用一个
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
总结如下：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到这里，相信很多人都能看出这就是我们熟悉的 Fibonacci序列。
int jump_sum(int n) //递归版本
{
assert(n>0);
if (n == 1 || n == 2) return n;
return jump_sum(n-1)+jump_sum(n-2);
}
int jump_sum(int n) //迭代版本
{
assert(n>0);
if (n == 1 || n == 2) return n;
int an, an_1=2, an_2=1;
for (; n>=3; n--)
{
an = an_2 + an_1;
an_2 = an_1;
an_1 = an;
}
return an;
}
10
28.28.28.28.整数的二进制表示中 1111 的个数
题目：输入一个整数，求该整数的二进制表达中有多少个 1。
例如输入 10，由于其二进制表示为 1010，有两个 1，因此输出 2。
分析：
这是一道很基本的考查位运算的面试题。
包括微软在内的……
一个很基本的想法是，我们先判断整数的最右边一位是不是 1。
接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位了，
再判断是不是 1。
这样每次移动一位，直到这个整数变成 0 为止。
现在的问题变成怎样判断一个整数的最右边一位是不是 1 了。
很简单，如果它和整数 1 作与运算。由于 1 除了最右边一位以外，其他所有位都为 0。
因此如果与运算的结果为 1，表示整数的最右边一位是 1，否则是 0。*/
得到的代码如下：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution1(int i)
{
int count = 0;
while(i)
{
if(i & 1)
count ++;
i = i >> 1;
}
return count;
}
可能有读者会问，整数右移一位在数学上是和除以 2 是等价的。
那可不可以把上面的代码中的右移运算符换成除以 2 呢？答案是最好不要换成除法。
因为除法的效率比移位运算要低的多，
在实际编程中如果可以应尽可能地用移位运算符代替乘除法。
这个思路当输入 i 是正数时没有问题，但当输入的 i 是一个负数时，
11
不但不能得到正确的 1 的个数，还将导致死循环。
以负数 0x80000000 为例，右移一位的时候，
并不是简单地把最高位的 1 移到第二位变成 0x40000000，
而是 0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，
因此移位后的最高位会设为 1。
如果一直做右移运算，最终这个数字就会变成 0xFFFFFFFF而陷入死循环。
为了避免死循环，我们可以不右移输入的数字 i。
首先 i 和 1 做与运算，判断 i 的最低位是不是为 1。
接着把 1 左移一位得到 2，再和 i做与运算，就能判断 i的次高位是不是 1……
这样反复左移，每次都能判断 i 的其中一位是不是 1。基于此，我们得到如下代码：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution2(int i)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(i & flag)
count ++;
flag = flag << 1;
}
return count;
}
29.29.29.29.栈的 pushpushpushpush、poppoppoppop 序列
题目：输入两个整数序列。其中一个序列表示栈的 push顺序，
判断另一个序列有没有可能是对应的 pop 顺序。
如果我们希望 pop 的数字正好是栈顶数字，直接 pop 出栈即可；
如果希望 pop 的数字目前不在栈顶，我们就到
push序列中还没有被 push到栈里的数字中去搜索这个数字，
并把在它之前的所有数字都 push进栈。
如果所有的数字都被 push进栈仍然没有找到这个数字，表明该序列不可能是一个 pop 序列。
12
////////////////////////////////////
我们来着重分析下此题：
push序列已经固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 4 5 3 2 1
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
1.要得到 4 5 3 2 1的 pop序列，即 pop的顺序为 4->5->3->2->1
首先，要 pop4，可让 push5 之前，pop4，然后 push5，pop5
然后发现 3 在栈顶，直接 pop 3..2..1
2.再看一序列，
push pop
--- -- -> /---->
5 4 3 2 1 / 4 3 5 1 2
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
想得到 4 3 5 1 2 的 pop 序列，是否可能? 4->3->5->1->2
同样在 push5之前，push 了 4 3 2 1，pop4，pop 3，然后再 push 5，pop5
2
再看栈中的从底至上是 1 ，由于 1 2已经在栈中，所以只能先 pop2，才能 pop1。
所以，很显然，不可能有 4 3 5 1 2的 pop 序列。
所以上述那段注释的话的意思，即是，
如果，一个元素在栈顶，直接 pop 即可。如果它不在栈顶，那么从 push序列中找这个元素
找到，那么 push 它，然后再 pop 它。否则，无法在 那个顺序中 pop。
//////////////////////////////////////
//////////////////////////////////////
push序列已经固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 3 5 4 2 1 //可行
| 5 | 1 4 5 3 2 //亦可行，不知各位，是否已明了题意?:)..
13
| 4 |
| 3 |
| 2 |
|___1__|
///////////////////////////////////////////////
今早我也来了，呵。
昨晚，后来，自个又想了想，要怎么才能 pop 想要的一个数列?
push序列已经固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 5 4 3 2 1
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
比如，当栈中已有数列 2
1
而现在我随机 要 pop4，一看，4不在栈中，再从 push序列中，
正好，4在 push队列中，push4进栈之前，还得把 4前面的数，即 3 先 push进来，。
好，现在，push 3, push 4，然后便是想要的结果：pop 4。
所以，当我要 pop 一个数时，先看这个数 在不在已经 push的 栈顶，如果，在，好，直接
pop它。
如果，不在，那么，从 push序列中，去找这个数，找到后，push 它进栈，
如果 push队列中它的前面还有数，那么 还得把它前面数，先 push进栈。
如果铺设队列中没有这个数，那当然 就不是存在这个 pop 结果了。
不知，我说明白了没?：）.接下来，给一段，参考程序：
//有误之处，恳请指正。July、2010/11/09。:)。
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;
if(pPush && pPop && nLength > 0)
{
const int *pNextPush = pPush;
const int *pNextPop = pPop;
// ancillary stack
std::stack stackData;
14
// check every integers in pPop
while(pNextPop - pPop < nLength)
{
// while the top of the ancillary stack is not the integer
// to be poped, try to push some integers into the stack
while(stackData.empty() || stackData.top() != *pNextPop)
{
// pNextPush == NULL means all integers have been
// pushed into the stack, can't push any longer
if(!pNextPush)
break;
stackData.push(*pNextPush);
// if there are integers left in pPush, move
// pNextPush forward, otherwise set it to be NULL
if(pNextPush - pPush < nLength - 1)
pNextPush ++;
else
pNextPush = NULL;
}
//After pushing, the top of stack is still not same as
// pPextPop, pPextPop is not in a pop sequence
// corresponding to pPush
if(stackData.top() != *pNextPop)
break;
// Check the next integer in pPop
stackData.pop();
pNextPop ++;
}
// if all integers in pPop have been check successfully,
// pPop is a pop sequence corresponding to pPush
if(stackData.empty() && pNextPop - pPop == nLength)
bPossible = true;
}
return bPossible;
}
15
30.30.30.30.在从 1111 到 nnnn的正数中 1111 出现的次数
题目：输入一个整数 n，求从 1到 n这 n个整数的十进制表示中 1出现的次数。
例如输入 12，从 1到 12这些整数中包含 1 的数字有 1，10，11和 12，1一共出现了 5次。
分析：这是一道广为流传的 google 面试题。
我们每次判断整数的个位数字是不是 1。如果这个数字大于 10，除以 10 之后再判断个位数
字是不是 1。
基于这个思路，不难写出如下的代码：*/
int NumberOf1(unsigned int n);
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
int number = 0;
// Find the number of 1 in each integer between 1 and n
for(unsigned int i = 1; i <= n; ++ i)
number += NumberOf1(i);
return number;
}
int NumberOf1(unsigned int n)
{
int number = 0;
while(n)
{
if(n % 10 == 1)
number ++;
n = n / 10;
}
return number;
}
////////////////////////////////////////////
这个思路有一个非常明显的缺点就是每个数字都要计算 1在该数字中出现的次数，因此时间
复杂度是O(n)。
当输入的 n 非常大的时候，需要大量的计算，运算效率很低。
各位，不妨讨论下，更好的解决
办法
鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载
。:)...
16
31.31.31.31.华为面试题：
一类似于蜂窝的结构的图，进行搜索最短路径（要求 5 分钟）
基于虚信道路由算法
为了在六角形蜂窝网络
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
最短路径的算法，我们使用虚信道技术来避免死锁。
////////////////////////////////////
算法 2（Double XY 算法）：
输入：当前节点坐标（Xcurrent，Ycurrent，Zcurrent），目的节点坐标（Xdest，Ydest，Zdest）,
节点类型NodeFlag 以及源节点 Z 向坐标 Zsource。
输出：选择的输出通道 Channel。
过程：
///////////////////////////////////
Xoffset :＝ Xdest － Xcurrent;
Yoffset :＝ Ydest － Ycurrent;
Zoffset :＝ Zdest － Zcurrent;
Zsrcoffset :＝ Zsource － Zdest；
if (Zoffset ≥ 0 and
( Zsrcoffset > 0 or Zsrcoffset = 0 )) then
if (NodeFlag = Black) then
if (Xoffset > 0) then
Channel := X0+;
if (Yoffset > 0) then
Channel := Y0+;
if (Zoffset > 0) then
Channel := Z+;
if (NodeFlag = White) then
if (Xoffset < 0) then
Channel := X0－;
if (Yoffset < 0) then
Channel := Y0－;
if (Zoffset ≤ 0 and Zsrcoffset < 0) then
if (NodeFlag = White) then
if (Xoffset < 0) then
Channel := X1－;
if (Yoffset < 0) then
Channel := Y1－;
if (Zoffset < 0) then
Channel := Z－;
17
if (NodeFlag = Black) then
if (Xoffset > 0) then
Channel := X1+;
if (Yoffset > 0) then
Channel := Y1+;
if (Xoffset = 0 and Yoffset = 0 and Zoffet = 0) then
Channel := internal;
第 31 题，完。
32.32.32.32.
有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序；
要求：通过交换 a,b 中的元素，使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
求解思路：
当前数组 a 和数组 b的和之差为
A = sum(a) - sum(b)
a 的第 i 个元素和 b 的第 j个元素交换后，a 和 b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设 x = a[i] - b[j]
|A| - |A'| = |A| - |A-2x|
假设 A > 0,
当 x 在 (0,A)之间时，做这样的交换才能使得交换后的 a 和 b 的和之差变小，
x越接近 A/2效果越好,
如果找不到在(0,A)之间的 x，则当前的 a 和 b 就是答案。
所以算法大概如下：
在 a 和 b中寻找使得 x在(0,A)之间并且最接近 A/2 的 i和 j，交换相应的 i和 j元素，
重新计算A 后，重复前面的步骤直至找不到(0,A)之间的 x为止。
/////////////////////////////////////////
算法
18
1. 将两序列合并为一个序列，并排序，为序列 Source
2. 拿出最大元素 Big，次大的元素 Small
3. 在余下的序列 S[:-2]进行平分，得到序列max，min
4. 将 Small 加到max 序列，将 Big 加大 min 序列，重新计算新序列和，和大的为 max，小
的为min。
////////////////////////////////////////////////
def mean( sorted_list ):
if not sorted_list:
return (([],[]))
big = sorted_list[-1]
small = sorted_list[-2]
big_list, small_list = mean(sorted_list[:-2])
big_list.append(small)
small_list.append(big)
big_list_sum = sum(big_list)
small_list_sum = sum(small_list)
if big_list_sum > small_list_sum:
return ( (big_list, small_list))
else:
return (( small_list, big_list))
tests = [ [1,2,3,4,5,6,700,800],
[10001,10000,100,90,50,1],
range(1, 11),
[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
]
for l in tests:
l.sort()
print
print "Source List:\t", l
l1,l2 = mean(l)
print "Result List:\t", l1, l2
print "Distance:\t", abs(sum(l1)-sum(l2))
print '-*'*40
19
输出结果
Source List: [1, 2, 3, 4, 5, 6, 700, 800]
Result List: [1, 4, 5, 800] [2, 3, 6, 700]
Distance: 99
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 50, 90, 100, 10000, 10001]
Result List: [50, 90, 10000] [1, 100, 10001]
Distance: 38
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result List: [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]
Distance: 1
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List: [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance: 21
33.33.33.33.
实现一个挺高级的字符匹配算法：
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来
其实就是类似一些和谐系统。。。。。
分析：
自然匹配就是对待匹配的每个字符挨个匹配
设你的待匹配字串长度位 n,模式字符串长度位m.
对于待匹配字符串中的任意一个字符最坏情况下要匹配 m次，也就是说这个字符不在模式
字符串中。
所以最坏情况下总共是m*n 此匹配，时间复杂度就是O(m*n)
倘若使用 hash表对待字符串进行 hash处理 O(n)的时间复杂度，那么对于模式字符串中的任
意字符，
仅需一次 hash 判断就可以得知是否在待匹配字符串中出现。
最坏仅需m 次就可以得到结果。时间复杂度为O(m)或者O(n);
与此题相类似：
就是给一个很长的字符串 str 还有一个字符集比如{a,b,c} 找出 str里包含{a,b,c}的最短子
串。
要求O(n)?
20
比如，字符集是 a,b,c，字符串是 abdcaabcx，则最短子串为 abc。
用两个变量 front rear 指向一个的子串区间的头和尾
用一个 int cnt[255]={0}记录当前这个子串里 字符集 a,b,c 各自的个数，
一个变量 sum记录字符集里有多少个了
rear 一直加，更新 cnt[]和 sum的值，直到 sum等于字符集个数
然后 front++,直到 cnt[]里某个字符个数为 0，这样就找到一个符合条件的字串了
继续前面的操作，就可以找到最短的了。
//还有没有人，对此题了解的比较深的? 望 也多阐述下...:)。
34.34.34.34.实现一个队列。
队列的应用场景为：
一个生产者线程将 int 类型的数入列，一个消费者线程将 int 类型的数出列
生产者消费者线程演示
一个生产者线程将 int 类型的数入列，一个消费者线程将 int 类型的数出列
#include
#include
#include
#include
#include
using namespace std;
HANDLE ghSemaphore; //信号量
const int gMax = 100; //生产(消费)总数
std::queue q; //生产入队,消费出队
//生产者线程
unsigned int __stdcall producerThread(void* pParam)
{
int n = 0;
while(++n <= gMax)
{
//生产
q.push(n);
cout<<"produce "<sum，则更新 sum=b;
若 b
2 using namespace std;
3
4 int ** a;
5 int **sum;
6 int max_array(int *a,int n)
7 {
8 int *c = new int [n];
9 int i =0;
10 c[0] = a[0];
11 for(i=1;imax_sum)
21 max_sum = c[i];
22 delete []c;
23 return max_sum;
24
25 }
26 int max_matrix(int n)
27 {
28 int i =0;
29 int j = 0;
30 int max_sum = -65535;
31 int * b = new int [n];
32
33 for(i=0;i max_sum)
3 max_sum = sum;
44 }
45 }
46 delete []b;
47 return max_sum;
48 }
49 int main()
50 {
51 int n;
52 cin >> n;
53
54 a = new int *[n];
55 sum = new int *[n];
56 int i =0;
57 int j =0;
58 for(i=0;i>a
![微软等数据结构算法面试100题[第21-40题答案]](https://swf.iask.com/PEs9MtYaE2r_all.svg?ssig=NdeiaUUW7Q&Expires=1719279176&KID=sina,ishare&range=0-367387)
浙公网安备 33021202002483