名企招聘经典面试编程题集锦[第31-40题]

31、在O（1）时间内删除链表结点

题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：

分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，

更重要的是，还能考察我们对时间复杂度的理解。

void DeleteNode(listNode*& head , listNode* node){if(head==NULL || node==NULL)return;if(node->next!=NULL){listNode* nextNode = node->next;node->next = nextNode->next;node->value = nextNode->value;delete node;}else if(head==node){delete head;head = NULL;}else{listNode* helper = head;while(helper->next!=node)helper = helper->next;helper->next = NULL;delete node;}}

32、找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

void FindNumbers(int* data, int length,int& num1,int& num2){if(data==NULL || length<2)return;int result = 0;for(int i=0;i!=length;++i)result^=*(data+i);int helper = 1;while(!(helper & result))helper = helper<<1;num1 = 0;num2 = 0;for (int i=0;i!=length;++i){if(helper & *(data+i))num1^= *(data+i);elsenum2^= *(data+i);}}

33、找出链表的第一个公共结点
题目：两个单向链表，找出它们的第一个公共结点。

分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。

listNode* FindFirstSameNode(listNode* head1,listNode* head2){if(head1 == NULL || head2 == NULL)return NULL;int num1=0;int num2=0;listNode* helper1 = head1;listNode* helper2 = head2;while (helper1!=NULL){++num1;helper1 = helper1->next;}while (helper2!=NULL){++num2;helper2 = helper2->next;}int diffenece = num1 - num2; if(diffenece>=0){for(int i = 0; i!=diffenece;++i)head1 = head1->next;}else{for(int i = 0; i!=-diffenece;++i)head2 = head2->next;}while (head1->next != head2->next){head1 = head1->next;head2 = head2->next;}return head1->next;}

34、在字符串中删除特定的字符
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。

例如，输入”They are students.”和”aeiou”，

则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。

void DeleteChars(char* str, char* chars){if(str == NULL || chars == NULL)return;char hashTable[256]={0}; for (char* ch = chars;*ch!='\0';++ch)++hashTable[*ch];for (char* ch = str;*ch!='\0';++ch){if(!hashTable[*ch])*str++ = *ch;}*str = '\0';}

35、寻找丑数
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

int FindUgly(int n){if(n<1)throw exception("invalid parameters!");int* uglyNumbers = new int[n];uglyNumbers[0] = 1;int nextUglyIndex = 1;int* Multiply2 = uglyNumbers;int* Multiply3 = uglyNumbers;int* Multiply5 = uglyNumbers;while (nextUglyIndex!=n){int minNum = min(*Multiply2*2,min(*Multiply3*3,*Multiply5*5));uglyNumbers[nextUglyIndex]=minNum;while(*Multiply2*2<=minNum)++Multiply2;while(*Multiply3*3<=minNum)++Multiply3;while(*Multiply5*5<=minNum)++Multiply5;++nextUglyIndex;}int ret = uglyNumbers[n-1];delete[] uglyNumbers;return ret;}

36、输出1到最大的N位数
题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，

则输出1、2、3一直到最大的3位数即999。
分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

//必须考虑大数void PrintNums(int n){if(n<1)return;int* nums = new int[n+1];for(int i=0;i!=n+1;++i)*(nums+i)=0;*nums=1;while (*(nums+n)==0){//输出大数bool startFlag = false;for(int i=n-1;i>=0;--i){if(startFlag)cout<<*(nums+i);else if(*(nums+i)!=0){cout<<*(nums+i);startFlag=true;}}cout<<endl;//大数加一if(*nums != 9)++*nums;else{int* helper = nums;while (*helper == 9){*helper = 0;++helper;}++*helper;}}}

37、旋转数组中的最小元素
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，

输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

int findMin(int* theArray,int length){if (theArray==NULL||length<=0)throw std::exception("invalid parameters!");findMin(theArray,theArray+length-1);}int findMin(int* start,int* end){int endNum = *end;int midNum = *(start+(end-start)/2);if(start!=end){if(midNum<=endNum)findMin(start,start+(end-start)/2);elsefindMin(start+(end-start)/2+1,end);}elsereturn *start;}

38、数值的整数次方

题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
不需要考虑溢出。

分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
double Power(double base, int exponent)
{

double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}

//你还需要考虑更多double Power(double base, int exponent){if(exponent==0)return 1;double result = 1;int abExponent = exponent>0?exponent:-exponent;for (int i = 0;i!=abExponent;++i)result*=base;if(exponent>0)return result;else if(base==0)throw exception("unvalid parameters!");elsereturn 1/result;}

39、对称字符串的最大长度

题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

int GetLongestSymmetricalStr(char* str){if(str == NULL)return 0;int length = 1;char* pChar = str;while(*pChar != '\0'){// Substrings with odd lengthchar* pFirst = pChar - 1;char* pLast = pChar + 1;while(pFirst >= str && *pLast != '\0' && *pFirst == *pLast){pFirst--;pLast++;}int newLength = pLast - pFirst - 1;if(newLength > length)length = newLength;// Substrings with even lengthpFirst = pChar;pLast = pChar + 1;while(pFirst >= str && *pLast != '\0' && *pFirst == *pLast){pFirst--;pLast++;}newLength = pLast - pFirst - 1;if(newLength > length)length = newLength;pChar++;}return length;}

40、数组中超过出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。

int FindNum(int* data,int length){if(data==NULL || length<1)return -1;int num = *data;int times = 1;for(int i=1;i!=length;++i){if(num==*(data+i))++times;else{--times;if(times==0){num = *(data+i);++times;}}}return num;}