|
76.复杂链表的复制 题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外， 请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。 分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。 要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力， 对数据结构透彻的理解以及扎实的编程功底。 A:一开始想这道题毫无思路，如果蛮来，首先创建好正常的链表，然后考虑sibling这个分量，则需要O(n^2)的时间复杂度，然后一个技巧便可以巧妙的解答此题。看图便知。首先是原始的链表 file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(2).jpg 然后我们还是首先复制每一个结点N为N*，不同的是我们将N*让在对应的N后面，即为 file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(3).jpg 然后我们要确定每一个N*的sibling分量，非常明显，N的sibling分量的next就是N*的sibling分量。 最后，将整个链表拆分成原始链表和拷贝出的链表。 这样，我们就解决了一个看似非常混乱和复杂的问题。
1.给定单链表，检测是否有环。
2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。 如果head1==head2，那么显然相交，直接返回head1。 3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。 运用题一，我们可以检查链表中是否有环。 如果有环，那么p1p2重合点p必然在环中。从p点断开环， 方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表， 一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。
5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
78.链表和数组的区别在哪里？ 分析：主要在基本概念上的理解。
80.阿里巴巴一道笔试题 问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? http://www.cnblogs.com/yaozhongxiao/archive/2009/11/10/1600516.html 今天阿里淘宝笔试中碰到两道组合数学题，感觉非常亲切，但是笔试中失踪推导不出来 后来查了下，原来是Catalan数。悲剧啊，现在整理一下 Catalan数——卡特兰数】 一.Catalan数的定义令h(1)=1，Catalan数满足递归式：h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2该递推关系的解为：h(n) = C(2n-2,n-1)/n，n=1,2,3,...（其中C(2n-2,n-1)表示2n-2个中取n-1个的组合数） 问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 这个笔试题,很YD,因为把某个递推关系隐藏得很深. 问题分析: 我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排. 用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案. 比如000000111111就对应着 第一排:0 1 2 3 4 5 第二排:6 7 8 9 10 11 010101010101就对应着 第一排:0 2 4 6 8 10 第二排:1 3 5 7 9 11 问题转换为,这样的满足条件的01序列有多少个. 观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人 要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数. 也就是要求,0的个数大于1的个数. OK,问题已经解决. 如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个. 这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的 方法数,其通项是c(2n, n)/(n+1). 在<<计算机程序设计艺术>>,第三版,Donald E.Knuth著,苏运霖译,第一卷,508页,给出了证明: 问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n) 显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件). 在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置.然后在导致并包括这个X的部分序列中,以 S代替所有的X并以X代表所有的S.结果是一个有(n+1)个S和(n-1)个X的序列.反过来,对一垢一种类型的每个序列,我们都能 逆转这个过程,而且找出导致它的前一种类型的不允许序列.例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS.这个对应说明,不允许 的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437] 验证: 其中F表示前排,B表示后排,在枚举出前排的人之后,对应的就是后排的人了,然后再验证是不是满足后面的比前面对应的人高的要求. #include <iostream> using namespace std; int bit_cnt(int n) { int result = 0; for (; n; n &= n-1, ++result); return result; } int main() { int F[6], B[6]; int ans = 0; for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6) { int i = 0, j = 0; for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k; int ok = 1; for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;} ans += ok; } cout << ans << endl; return 0; } 结果:132 而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132 注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1) 估计出题的人也读过<<计算机程序艺术>>吧. PS: 另一个很YD的问题: 有编号为1到n(n可以很大,不妨在这里假定可以达到10亿)的若干个格子,从左到右排列. 在某些格子中有一个棋子,不妨设第xi格有棋子(1<=i<=k, 1<=k<=n) 每次一个人可以把一个棋子往左移若干步, 但是不能跨越其它棋子,也要保证每个格子至多只有一个棋子. 两个人轮流移动,移动不了的为输,问先手是不是有必胜策略. 三.Catalan数的典型应用： 1.括号化问题。矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？ 2.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数? 类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 3.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) 类似：一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 分析：对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。 不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。 反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。 因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应。 显然，不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。 （这个公式的下标是从h(0)=1开始的）
先来几组百度的面试题： =================== 81.第1组百度面试题 1.一个int数组，里面数据无任何限制，要求求出所有这样的数a， 其左边的数都小于等于它，右边的数都大于等于它。 能否只用一个额外数组和少量其它空间实现。 解答： 分析：最原始的方法是检查每一个数 array ，看是否左边的数都小于等于它，右边的数都大于等于它。这样做的话，要找出所有这样的数，时间复杂度为O(N^2)。 其实可以有更简单的方法，我们使用额外数组，比如rightMin[]，来帮我们记录原始数组array右边（包括自己）的最小值。假如原始数组为： array[] = {7, 10, 2, 6, 19, 22, 32}， 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是说，7右边的最小值为2, 2右边的最小值也是2。有了这样一个额外数组，当我们从头开始遍历原始数组时，我们保存一个当前最大值 max， 如果当前最大值刚好等于rightMin， 那么这个最大值一定满足条件。还是刚才的例子。 第一个值是7，最大值也是7，因为7 不等于 2， 继续， 第二个值是10，最大值变成了10，但是10也不等于2，继续， 第三个值是2，最大值是10，但是10也不等于2，继续， 第四个值是6，最大值是10，但是10不等于6，继续， 第五个值是19，最大值变成了19，而且19也等于当前rightMin[4] = 19, 所以，满足条件。 如此继续下去，后面的几个都满足。 #include <iostream> 2 3 using namespace std; 4 5 #define max(a,b) a>b?a:b 6 #define min(a,b) a<b?a:b 7 8 void findNum(int data[],int len) 9 {10 int* a = new int[len];11 int* b = new int[len];12 a[len-1] = data[len-1];13 for (int i = len-2;i > 0;i--)14 {15 a = min(data,a[i+1]);16 }17 18 if (data[0] <= a[1])19 {20 cout<<"0:"<<data[0]<<endl;21 }22 23 a[0] = data[0];24 if (data[1] >= a[0] && data[1] <= a[2])25 {26 cout<<"1:"<<data[1]<<endl;27 }28 29 for (int i = 1;i < len-2;i++)30 {31 a = max(data,a[i-1]);32 if (data[i+1] >= a && data[i+1] <= a[i+2])33 {34 cout<<i+1<<":"<<data[i+1]<<endl;35 }36 }37 a[len-2] = max(data[len-2],a[len-3]);38 if (data[len-1] >= a[len-2])39 {40 cout<<len-1<<":"<<data[len-1]<<endl;41 }42 }43 44 int main()45 {46 int data[10] = {1,3,2,4,6,7,5,9,11,10};47 findNum(data,10);48 } 2.一个文件，内含一千万行字符串，每个字符串在1K以内， 要求找出所有相反的串对，如abc和cba。 文件的大小上限是10G，不可能在内存操作了。考虑设计一种hash使得如果两个字符串维相反串能得出相同的hash值，然后用该hash将文件中的字符串散列到不同的文件中，再在各文件中进行匹配。比如这样的hash函数对字符串上所有字符的ascii求和，因为长度在1K以内，因此范围在int之内。更进一步，可以在上面那个hash后面再加一个字符串长度，可以得到更好的散列效果。 在各个单独文件中匹配时，如果采用的是第二种hash函数，那么该文件中的所有字符串都有相同的长度。如果hash效果好，那么这个文件应该小到可以在内存中进行操作了。将文件拷贝为两份，分别按照不同规则hash：第一份按前k位哈希，第二份将字符串的头尾进行颠倒后按前k位哈希（只是对于排序算法颠倒，不必实际颠倒）。这里的按前k位哈希只需要前k位相同能得到相同结果就好，比如第i位的ascii乘以2^i。两份拷贝中hash值相同的就很可能是要求的相反串对了，再进行实际匹配，工作量应该就可以接受了。 3.STL的set用什么实现的？为什么不用hash？ 是用红黑树实现的，红黑树是一种平衡性很好的二分查找树。要使用hash的话，就需要为不同的存储类型编写哈希函数，这样就照顾不到容器的模板性了，而是用红黑树只需要为不同类型重载operator<就可以了。
82.第2组百度面试题 2.给出一个文件，里面包含两个字段{url、size}，
83.第3组百度面试题 2.百度笔试题 原型：extern void *memmove(void *dest, const void *src, unsigned int count); 功能：由src所指内存区域复制count个字节到dest所指内存区域。说明：src和dest所指内存区域可以重叠，但复制后src内容会被更改。函数返回指向dest的指针。 功能类似于memcpy,不同的是memcpy内存区域不可重叠 例子： char *p="hello world!"; char *q=(char*)malloc(sizeof(char)*strlen(p)); memmove(q,p,sizeof(p)+1); 1.memmove 函数原型：void *memmove(void *dest, const void *source, size_t count) 返回值说明：返回指向dest的void *指针 参数说明：dest,source分别为目标串和源串的首地址。count为要移动的字符的个数 函数说明：memmove用于从source拷贝count个字符到dest，如果目标区域和源区域有重叠的话，memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中。 memmove(),如果两函数重叠，赋值仍正确进行。 如果你不能保证是否有重叠，为了确保复制的正确性，你必须用memmove void *memmove(void *dest, const void *source, size_t count) { assert((NULL != dest) && (NULL != source)); char *tmp_source, *tmp_dest; tmp_source = (char *)source; tmp_dest = (char *)dest; if((dest + count<source) || (source + count) <dest)) {// 如果没有重叠区域 while(count--) *tmp_dest++ = *tmp_source++; } else { //如果有重叠 tmp_source += count - 1; tmp_dest += count - 1; while(count--) *--tmp_dest = *--tmp; } return dest; } 84.第4组百度面试题 2010年3道百度面试题[相信，你懂其中的含金量] 1.a~z包括大小写与0~9组成的N个数 用最快的方式把其中重复的元素挑出来。 2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器， 使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...， 构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低。 首先是1/2的情况，我们一次性生成两个数值，如果是00或者11丢弃，否则留下，01为1，10为0，他们的概率都是p*(1-p)是相等的，所以等概率了。 然后是1/n的情况了，我们以5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x，此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃，这时候剩下六个:0011,0101,0110,1001,1010,1100，取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5，这时候他们的概率都是p*p*(1-p)*(1-p)相等了。 关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率。 因为C(n,i)最大是在i接近n/2的地方取得，此时我有更大比率的序列用于生成，换句话说被抛掉的更少了，这样做是为了避免大量生成了丢弃序列而使得生成速率减慢，实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等，比如C(2x,x)的概率就是[p(1-p)]^x，互等的样例空间内保证了对应的每个值取得的样例等概率。 3.有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。 要求按照query的频度排序.
85.又见字符串的问题 86. 怎样编写一个程序，把一个有序整数数组放到二叉树中？ 分析:本题考察二叉搜索树的建树方法，简单的递归结构。 关于树的算法设计一定要联想到递归，因为树本身就是递归的定义。 using namespace std;struct TreeNode { int m_nValue; TreeNode *m_pLeft; TreeNode *m_pRight;};//把一个有序整数数组放到二叉树void RecurCreateTree(int *p, int length, TreeNode *&pHead){ if (length > 0) { pHead = new TreeNode; int mid = length/2; pHead->m_nValue = p[mid]; pHead->m_pLeft = NULL; pHead->m_pRight = NULL; RecurCreateTree(p, mid, pHead->m_pLeft); RecurCreateTree(p + mid + 1, length - mid - 1, pHead->m_pRight);; } else { pHead = NULL; }}//中序递归遍历void MidRecurTraversal(TreeNode* pHead){ if (NULL != pHead) { MidRecurTraversal(pHead->m_pLeft); cout<<pHead->m_nValue<<" "; MidRecurTraversal(pHead->m_pRight); }}int _tmain(int argc, _TCHAR* argv[]){ int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,11, 12}; TreeNode *pHead = NULL; RecurCreateTree(arr, sizeof(arr)/sizeof(arr[0]), pHead); MidRecurTraversal(pHead); cout<<endl; return 0;} 而，学会把递归改称非递归也是一种必要的技术。 毕竟，递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。 但是对某些数学问题，就一定要学会用递归去解决。 87. 1.大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题） 2.求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”） 3.实现strstr功能，即在父串中寻找子串首次出现的位置。 （笔试中常让面试者实现标准库中的一些函数） 88.2005年11月金山笔试题。编码完成下面的处理函数。 函数将字符串中的字符'*'移到串的前部分， 前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。 如原始串为：ab**cd**e*12， 处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）
89.神州数码、华为、东软笔试题 1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。 2.编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符 串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0 3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等） 4.删除字符串中的数字并压缩字符串。 如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。 （下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)） 5.求两个串中的第一个最长子串（神州数码以前试题）。 如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。 90. 1.不开辟用于交换数据的临时空间，如何完成字符串的逆序 (在技术一轮面试中，有些面试官会这样问)。 2.删除串中指定的字符 （做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发） 3.判断单链表中是否存在环。 91. 1.一道著名的毒酒问题 有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。 现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。 2.有趣的石头问题 有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样， 把配对的石头和木头找出来。 92. 1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。 如果说,前面的人比后面的人高(两人身高一样认为是合适的), 那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列: 176, 178, 180, 170, 171 这些捣乱分子对为 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>, 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对) 要求： 输入: 为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。 输出： 为一个文件(out)，每行为一个数字，表示捣乱分子的对数。 详细说明自己的解题思路，说明自己实现的一些关键点。 并给出实现的代码 ，并分析时间复杂度。 限制： 输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。 思路：最简单的就是用两层循环，即考察每个元素，检查该元素后面的元素是否小于它，如果是就找到一个捣乱分子对。复杂度为O(n^2)。这道题的一种改进方案是用分治法，用到了归并排序的思想。我们可以将数组分成两部分，总的捣乱分子对为： 前半部分的捣乱分子对 + 后半部分的捣乱分子对 + X，这里的X为两部分合并中出现的捣乱分子对，什么情况下会出现呢？假设前半部分的元素范围为 A[from] 到A[mid]，后半部分的元素范围为A[mid + 1] 到A[to]，考虑前半部分的某元素A和后半部分的某元素A[j]，如果A[j] < A，由于两部分都是排好序的，因此捣乱分子对增加 mid - i + 1个，也就是说A[j]小于A, A[i+1].. A[mid]，这个关系显然成立。 参考代码： int Merge(int *pArray, int from, int mid, int to) { int i = from, j = mid + 1; int k = 0, num = 0; int *pTmp = new int[to-from+1]; while(i<=mid && j<=to) //归并排序的主框架 { if(pArray <= pArray[j]) pTmp[k++] = pArray[i++]; else { num += (mid - i + 1); //增加捣乱分子对 for(int l = i; l <= mid; l++) //输出捣乱分子 cout<<pArray[l]<<' '<<pArray[j]<<endl; pTmp[k++] = pArray[j++]; } } while(i <= mid) pTmp[k++] = pArray[i++]; while(j <= to) pTmp[k++] = pArray[j++]; for(k = from ; k <= to; k++) pArray[k] = pTmp[k - from]; delete [] pTmp; return num; } int MergeSort(int *pArray, int from, int to) { if(from < to) { int mid = (from + to) /2; int num = MergeSort(pArray, from ,mid) + MergeSort(pArray, mid+1, to); //分别算出两部分的捣乱分子对 num += Merge(pArray, from, mid, to); //合并中出现的捣乱分子对 return num; } return 0; } 93.在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。 直观想法是用两个数组a、b。a、b分别保存从前到i的最大的数和从后到i的最小的数， 一个解答：这需要两次遍历，然后再遍历一次原数组， 将所有data>=a[i-1]&&data<=b的data找出即可。 给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。 94.微软笔试题 求随机数构成的数组中找到长度大于=3的最长的等差数列9 d- x' W) w9 ?" o3 b0 R 输出等差数列由小到大: 如果没有符合条件的就输出 格式： 输入[1,3,0,5,-1,6] 输出[-1,1,3,5] 要求时间复杂度，空间复杂度尽量小 动态规划求解。设f[j]为以a,a[j]结尾的等差数列的最长长度。那么 递归方程为：f[j]=max{f[k]+1,a[k]-a==a-a[j]}，起始条件f[j]=1；伪代码如下： for(int k =0; k <n; k++) for(int i=k+1;i<n;i++) for(int j=i+1;j<n;j++) if(a[k]-a == a-a[j]) f[j] = (f[j]<f[k]+1?f[k]+1:f[j]); 而，最长长度为即为max{f[j]}，即以a,a[j]结尾，通过一次查找即可求出是那些元素组成的解。复杂度O（n^3）。 95.华为面试题 1 判断一字符串是不是对称的，如：abccba 2.用递归的方法判断整数组a[N]是不是升序排列 int is_ascending(int a[],int length){ if(length==1)return 1; if (a[length-1]>a[length]) { return 0; }else { return is_ascending(a,length-1); } } 96.08年中兴校园招聘笔试题 1．编写strcpy 函数 已知strcpy 函数的原型是 char *strcpy(char *strDest, const char *strSrc); 其中strDest 是目的字符串，strSrc 是源字符串。不调用C++/C 的字符串库函数，请 编写函数 strcpy 最后压轴之戏，终结此微软等100题系列V0.1版。 那就， 连续来几组微软公司的面试题，让你一次爽个够： ====================== 97.第1组微软较简单的算法面试题 1.编写反转字符串的程序，要求优化速度、优化空间。 2.在链表里如何发现循环链接？ 3.编写反转字符串的程序，要求优化速度、优化空间。 4.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。 5.写一个函数，检查字符是否是整数，如果是，返回其整数值。 （或者：怎样只用4行代码编写出一个从字符串到长整形的函数？） 98.第2组微软面试题 1.给出一个函数来输出一个字符串的所有排列。 2.请编写实现malloc()内存分配函数功能一样的代码。 3.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。 4.怎样编写一个程序，把一个有序整数数组放到二叉树中？ 5.怎样从顶部开始逐层打印二叉树结点数据？请编程。 6.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？
99.第3组微软面试题 1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。 现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？ a绳从两头烧，同时b绳从一头烧，当a绳烧尽时，灭掉b绳，同时c绳从两头烧，在c绳烧尽时，b绳从两头烧，结束时即为1小时15分钟。 2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。 抓取多少个就可以确定你肯定有两个同一颜色的果冻？（5秒-1分钟） 3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀， 问你如何才能准确称出4公升的水？（40秒-3分钟） 一个岔路口分别通向诚实国和说谎国。 来了两个人，已知一个是诚实国的，另一个是说谎国的。 诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国， 但不知道应该走哪条路，需要问这两个人。请问应该怎么问？（20秒-2分钟） 100.第4组微软面试题，挑战思维极限 1.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。 13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）（5分钟-1小时） 2.在9个点上画10条直线，要求每条直线上至少有三个点？（3分钟-20分钟） 3.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？ 都分别是什么时间？你怎样算出来的？（5分钟-15分钟） 终结附加题： 微软面试题，挑战你的智商 ========== 说明：如果你是第一次看到这种题，并且以前从来没有见过类似的题型， 并且能够在半个小时之内做出答案，说明你的智力超常..） 1.第一题 . 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分： 抽签决定自己的号码（1、2、3、4、5） 首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时， 按照他的方案进行分配，否则将被扔进大海喂鲨鱼 如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决， 当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼。 依此类推 条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。 问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？ 倒推法解答即可。 2.一道关于飞机加油的问题，已知： 每个飞机只有一个油箱， 飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架飞机绕地球飞半圈， 问题： 为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？ （所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场） |
[技术| 编程·课件·Linux] 100道经典算法题（76-100)
sissi
· 发布于 2012-10-21 22:31
· 3391 次阅读
转载文章时务必注明原作者及原始链接，并注明「发表于 软院网 RuanYuan.Net 」，并不得对作品进行修改。
