第一章 面试的流程

应聘者的项目经验

项目背景完成的任务为完成任务做了哪些工作，怎么做的自己的贡献

问题： 1. 在项目中遇到的最大的问题是什么，怎么解决的？ 2. 从项目中学到了什么 3. 等等

第二章 面试需要的基础知识

2.2编程语言

问： 定义一个空的类型，求sizeof的结果。 答：通常为1（或0）取决于编译器。因为对象必须占用一定的空间。 问：如果内定义函数呢？ 答：除了虚函数会在每个实例中添加一个指向虚函数表的指针外，其他函数不占有空间。 附：类的方法，是通过this指针实现的。除了虚方法是通过每个类自带的虚函数表指针来实现的。

面试题1：赋值运算符函数

相关注意点： 1. 返回：构造无返回；赋值返回本身引用。 2. 传入形式：通常为常量引用。尤其是构造函数内，如果非引用，则由实参构造形参的时候，就会需要递归调用构造函数，引发死循环。 3. 是否需要释放内存：常见于含有指针的类。赋值运算符结合了析构和构造，要释放和重新分配内存。 4. 自我赋值：自我赋值时候常常因为释放内存产生问题。

class CMyString{ public: CMyString(char* pData=NULL); CMyString(const CMyString& str); ~CMyString(); private: char* pData; };

一般写法

CMyString& CMyString::operator= (const CMyString& str){ if(str==*this) return *this; delete[] pData; pData=new char[strlen(str.pData)+1]; strcpy(str.pData,pData); return *this; }

带有异常保护的写法 如果内存分配异常，则不应先delete内存,这样异常发生后现场无法恢复。 所以应该先分配，再delete。以下用了一个很高明的方法： 1. 创建临时对象。则该对象中已经分配好了内存，并拷贝了数据。 2. 交换该对象的指针与类成员的指针。这样类成员指针成功接管了数据区，完成了新数据的纳入；临时对象的指针接管了旧数据区，会在函数结束时析构，完成了旧数据的释放。

CMyString& CMyString::operator= (const CMyString& str){ if(str!=*this){ CMyString temp(str); swap(temp.pData,pData); } return *this; }

2.3 数据结构

2.3.1 数组

vector当尺寸size超过容量capacity时候，会内存重分配，重新申请当前两倍的容量。 数组是内存上一块连续的区域，指针是内存上一个位置。 数组名可以当做指针来使用，通常在作为右值的场合，比如使用数组对指针作赋值和初始化，函数参数传入，返回值传出等。 例外：使用引用作赋值和初始化，使用引用作函数传入传出，sizeof typeid等运算符等。 值得注意的是，函数内形参即使是数组的形式，本质也是指针。

面试题3：二位数组中的查找

题目：在一个二维数组中，每一行都是从左向右递增，每一列都是从上到下递增。设计函数，判断该矩阵是否含有某个值。 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 设定一个起始点，如果开始在左下角位置6，如果目标值大于6，目标必然不会在第一列中，所以向右移动到8.这样搜索区域从以6作为左下角的4x4矩阵变成了以8为左下角的4x3矩阵。 所以规则如下： 1. 起始点在左下角 2. 当前值等于目标，目标已找到，函数返回 3. 目标大于当前值，则右移，否则左移。 4. 若移动出界，则查找失败。

bool Find(int target, vector<vector<int> > array) { if(array.empty()||array[0].empty()) return false; int rows=array.size(), cols=array[0].size(); int r=rows-1,c=0; while(1){ if(target==array[r][c]){ return true; } if(target>array[r][c]){ c++; }else{ r--; } if(c>=cols || r<0){ return false; } } return false; }

2.3.2 字符串

常量字符串存储于字符串常量区。即，相同的常量字符串地址相同。

面试题4：替换空格

题目：请实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。 从头到尾的插入，会大大消耗时间，所以使用从尾到头的誊写。 誊写前，先确定最终长度。注意新串的结束符。然后用两个指针分别指向原串尾和新串尾。

void replaceSpace(char *str,int length) { int num0=0; for(int i=0;i<length;++i){ if(str[i]==' ') num0++; } int newLen=length+2*num0; str[newLen]='\0'; //一定要注意 for(int i=length-1,j=newLen-1;i>=0;){ if(str[i]!=' '){ str[j--]=str[i--]; }else{ str[j--]='0'; str[j--]='2'; str[j--]='%'; i--; } } }

2.3.3 链表

链表元素的插入和删除要影响前驱节点，所以迭代的对象，一定是前驱节点。 无头链表要特别注意空指针和头节点的处理。

面试题5：从尾到头打印链表

题目：输入一个链表，从尾到头打印链表每个节点的值。不许使用额外O(N)的空间。

void reverPrint(ListNode* p){ if(p==nullptr){ return; } rever(p->next); cout<<p->val; }

2.3.4 树

面试题6：重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 利用中序序列中，根节点会划分序列为左右子树的特性；找到根节点，划分左右子树，并对左右分别递归调用函数即可。

例如

前：1 2 4 5 3 6 7 中：4 2 5 1 6 3 7 根节点：1 劈开中序： 4 2 5 + 6 3 7 依次匹配前序：2 4 5 + 3 6 7 继续递归调用。

TreeNode* reBuild(int* f,int* m,int n){ if(n<=0)//终止条件，千万别忘了 return nullptr; TreeNode* p=new TreeNode(f[0]); int i=0; for(i=0;i<n;++i){ if(m[i]==f[0]) break; } p->left=reBuild(f+1,m,i); p->right=reBuild(f+i+1,m+i+1,n-i-1); return p; }

2.3.5 栈和队列

面试题7 用两个栈实现队列

思路：两个栈IN和OUT 入队时直接压入IN栈； 出队时若OUT栈为空，则从IN依次弹出并压入OUT内。从OUT弹出元素。

class Solution { public: void push(int node) { stack1.push(node); } int pop() { if(stack2.empty()){ while(!stack1.empty()){ int node=stack1.top(); stack1.pop(); stack2.push(node); } } int node=stack2.top(); stack2.pop(); return node; } private: stack<int> stack1; stack<int> stack2; };

扩展：用队列实现栈操作。 压栈：直接入队尾。 出栈：需要把队尾元素输送至队首。即队首依次弹出N-1个元素入队尾。然后弹出队首，即为出栈操作。 出栈后，其他元素依然按照原序排列，故无后效性。 注：也可以用另一个队列来辅助操作。

2.4 算法和数据操作

2.4.1 查找和排序

Demo: 二分查找第一个大于等于x的数

int firstBigEq(int* a,int n,int x){ int left=0,right=n-1; //每次迭代中，a[right]>=x 且a[left]<x.先对最开始进行检测 if(a[0]>=x) return 0; if(a[n-1]<x) return -1; //终止条件是left与right相邻。 //每次迭代中，a[right]>=x 且a[left]<x while(left+1<right){ int mid=left+(right-left)/2; if(a[mid]>=x) right=mid;//新的right是旧的mid，而a[mid]>=x 所以a[新right]>=x else left=mid; } return right; }

如果right=mid-1以及left=mid+1，那么最后两者会相遇。但如果没有加减一，最后两者会相邻。

面试题8：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

int find(int* a,int n){ if(a[0]<a[n-1]){//原来头部较小，旋转后，较小的一定在后面。 return a[0]; } int left=0,right=n-1; while(left+1<right){ int mid=left+(right-left)/2; if(a[mid]>a[left]){ left=mid; }else if(a[mid]<a[left]){ right=mid; }else{//如果mid和left相等，无法确定在哪里。例如：3 3 1 2 3 for(int i=left;i<right;++i){ if(a[i]>a[i+1]){ return a[i+1]; } } } } //使用非缩减mid的好处，就是结果一定在left和right两者之间。 return a[left]<a[right]?a[left]:a[right]; }

递归和循环

面试题9：斐波那契数列的第N项

int Fibonacci(int n) { if(n<=0) return 0; if(n<=2) return 1; int a=1,b=1,c=2; for(int i=3;i<=n;++i){ c=a+b; a=b; b=c; } return c; }

面试题:跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

int jumpFloor(int number) { vector<int> s(number+1); s[1]=1; s[2]=2; for(int i=3;i<=number;++i) s[i]=s[i-1]+s[i-2]; return s[number]; }

面试题：变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

int jumpFloorII(int number) { vector<long> s(number+1); s[1]=1; for(int i=2;i<=number;++i) s[i]=s[i-1]*2; return s[number]; }

矩形覆盖

我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？ 其实简单画一画，就看得出，递推公式很接近斐波那契。

int rectCover(int number) { vector<int> s(number+1); s[1]=1; s[2]=2; for(int i=3;i<=number;++i){ s[i]=s[i-1]+s[i-2]; } return s[number]; }

2.4.3 位运算

对于有符号数，切记右移的时候，会填充符号位。所以位运算操作的往往是无符号数。 顺便提及一下STL里面bitset的使用：

bitset<n> b(u) b是unsigned long型u的一个副本,共n位，n为常数 bitset<n> b(s) b是string对象s中含有的位串的副本，共n位，n为常数 b.any() b中有1吗？ b.none() b中全0吗？ b.count() b中置为1的二进制位的个数 b.size() b中二进制位的个数 b[pos] 访问b中在pos处的二进制位 b.set() 把b中所有二进制位都置为1 b.set(pos) 把b中在pos处的二进制位置为1 b.reset() 把b中所有二进制位都置为0 b.reset(pos) 把b中在pos处的二进制位置为0 b.flip() 把b中所有二进制位逐位取反 b.flip(pos)把b中在pos处的二进制位取反 b.to_ulong()用b中同样的二进制位返回一个unsigned long值 os << b 把b中的位集输出到os流

注意：如果把一个有符号数转换为无符号数，二进制是不会变的，它之后被无符号数的形式来解析。 日常处理的时候，除了右移之外，有无符号数位操作基本一致。

二进制中1的个数

int NumberOf1(int n) { int num=0; while(n){ ++num; n=n&(n-1); } return num; }

n=n&(n-1)会使得最右侧的1变为0. 例如：

n =xxxx1 n-1 =xxxx0 ans =xxxx0 n =xxxx1000 n-1 =xxxx0111 ans =xxxx0000

第三章 高质量的代码

3.3 代码的完整性

关于错误的处理： 1. 返回值 2. 全局变量 3. 异常

面试题11：数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 基于鲁棒性的考虑： 1. 指数为0或负值的情况； 2. 底数为0的情况； 基于运算效率的考虑： B2n=Bn∗Bn 这样求B的N次方，就可以在O(logN)内求出。 我们把指数表示成二进制，从右向左遍历。如果某一位为1，则使得sum*=base。每次遍历base*=base. 例如3^5, 5= 0101 则结果为 1∗31+0∗32+1∗34+0∗38

double Power(double base, int exponent) { bool negE=false; if(exponent<0){ negE=true; exponent=-exponent; } bool zeroB=false; if(base>-0.00001 && base<0.00001){ zeroB=true; } if(zeroB && negE){ return -1;//一般抛出异常 } double sum=1; unsigned int ee=exponent; while(ee){ int last=ee&0x01; ee>>=1; if(last){ sum*=base; } base*=base; } if(negE){ sum=1.0/sum; } return sum; }

其中的要点： 1. 指数为负的结果最后须求倒数。0的负指数无意义。0的0次方可以为0或1. 2. 两个浮点数判相等，通常看它们的差，是否在0的一个领域。因为浮点是近似表示的。

bool equal(double a,double b){ return (a-b>-0.00001 && a-b<0.00001); } //整数加减如果考虑越界：通常越界的结果是很大的值，所以当然不在0的领域内了。

面试题12：打印1到最大的n位数

大数陷阱：如果单单指定n位数，很容易超过范围。这种类型一般用字符串或数组求解。 思路：n位数的全枚举。不足n位的，前面用0补齐。后续打印时注意即可。 全枚举问题用递归来完成。 递归求全枚举的基本框架是：分别枚举第m位置的所有可能，分别进入m+1个位置的递归。

void reOrder1(char* a,int m,vector<string >& res){ if(a[m]=='\0'){ res.push_back(a); return ; } for(int i=0;i<=9;++i){ a[m]='0'+i; reOrder1(a,m+1,res); } }

全排列 递归求全排列的基本框架是：分别交换第m位置和m及其后的所有位置，分别进入m+1个位置的递归，然后交换回来。交换回来的步骤，就是回溯。回溯时恢复函数调用前的状态。

void reOrder2(char* a,int m,vector<string >& res){ if(a[m]=='\0'){ res.push_back(a); return; } for(int i=m;a[i]!='\0';++i){ swap(a[m],a[i]); reOrder2(a,m+1,res); swap(a[m],a[i]); } }

扩展：求两个数相加

首先判断两者的符号：若同号，则是相加；否则就是相减。相加时用flag表示进位，然后从右向左遍历字符串。注意当遍历结束时，如果flag为1，需要在数字的最前面加一。相减时被减数为较大者。使用字符串的比较函数进行比对，选出较大者作为被减数。相减时用flag表示借位。遍历时验证各位的合法性。

具体代码未验证，此时暂略。

面试题13：在O(1)时间删除链表节点

删除链表节点势必会更改其前驱。这里使用拷贝其后继节点，然后删除其后继节点来模拟。然而，这样不能删除尾节点；不能更改const节点；割裂了地址和内容的一致性。

面试题14：调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整数组，使得所有的奇数位于偶数前面，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 如果没有相对位置的限制，可以使用快排的划分思想。但是快排是不稳定排序（即使没有随机交换过程，新旧都是）。 归并排序是稳定的，堆和快排和希尔都是不稳定的。 要想保证原有次序，则只能顺次移动或相邻交换。 遍历数组，如果当前是奇数，利用插入排序的思想，插入到前一个奇数的后面。 定义第0个奇数的位置是-1.

void reOrderArray(vector<int> &array) { int last=-1; for(int i=0;i<array.size();++i){ if(array[i]%2==1){ int get=array[i]; for(int j=i;j>last;--j){ array[j]=array[j-1]; } array[last+1]=get; last+=1; } } }

关于快速划分：快速划分可以划分为两块，甚至是三块。三块的情形，就是在数组头尾分别设置区间，对遍历到的元素进行判断，来决定交换并纳入哪一个区间中。注意新交换过来的陌生元素还需要再处理一遍。

3.4 代码的鲁棒性

面试题15：链表中倒数第K个节点

链表只有单向性，所以通常用快慢指针来快速查找某些位置。 1 2 3 4 5 6 7 空 有两种策略： 1. 当fast指向尾元素时，slow指向倒数第K个元素，则两指针相差K-1,所以开始阶段，fast前进K-1步。此后两指针同时移动，至fast为空。 2. 当fast为空时，slow指向倒数第K个元素，则两针相差K,开始阶段fast前进K步。此后两指针同时移动，至fast的next为空。

前者处理起来更容易，因为前者的开始阶段，fast始终是有效的，只需对其有效性进行检查，即可发现数组长度不足K的情况；后者的fast可能在前进最后一步时为空，检查起来略显麻烦。

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead==nullptr) return nullptr; ListNode* fast=pListHead,*slow=pListHead; for(int i=0;i<k-1;++i){ fast=fast->next; if(fast==nullptr){ return nullptr; } } while(fast->next){ fast=fast->next; slow=slow->next; } return slow; }

扩展：求链表的中间节点

1 2 3 4 5 1 2 3 4 5 6 fast和slow初始都指向头，fast每次走两步，slow每次走一步，直至fast不存在下个节点或不存在下下个节点。此时，如果fast有下个节点，则证明是偶数长度；反之为奇数长度。此时，若是奇数，则slow在正中；若是偶数，则正中偏左。

扩展：判断链表是否有环

1 2 3 4 5 8 6 7

fast和slow初始都指向头，fast每次走两步，slow每次走一步，直至fast为空或两指针相遇。前者证明无环，后者证明有环。 相遇后，fast不动，slow重新指向头； 接下来两者每次都走一步，直至相遇。相遇处即为入环点。

面试题16：反转链表

head->1->2->3->4->NULL 假设当前处理节点1，那么应该是求出其后的链表翻转后的尾节点，再把节点1添加到它的后面。这样就可以递归调用了： 递归函数输入：链表头指针； 输出：反转后的新头节点 注意：需要在主调函数里检查头指针有效性，以及手动添加尾节点的next为空。

ListNode* rever(ListNode* p){ if(p->next==nullptr){ return p; } //先反转后面的，再链接前面的，千万别反了 ListNode* newh=rever(p->next); p->next->next=p; return newh; } ListNode* ReverseList(ListNode* pHead) { if(!pHead) return nullptr; ListNode* newH=rever(pHead); pHead->next=nullptr; return newH; }

如果拿循环来做，通常用3个指针：

ListNode* Rever(ListNode* head){ ListNode* newH,*p=head,*plast=nullptr; while(p){ ListNode* pnxt=p->next; if(pnxt==nullptr) newH=p; //最后三句首尾相连 p->next=plast; plast=p; p=pnxt; } return newH; }

面试题17：合并两个排序的链表

ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ if(pHead1==nullptr) return pHead2; if(pHead2==nullptr) return pHead1; if(pHead1->val<pHead2->val){ pHead1->next=Merge(pHead1->next,pHead2); return pHead1; }else{ pHead2->next=Merge(pHead1,pHead2->next); return pHead2; } }

带头链表用循环好做，无头链表用递归好做。

面试题18：树的子结构

在这里判断B是否是A的子结构，而非完整的子树，不能用KMP算法来做。 ps：我们约定空树不是任意一个树的子结构

8 8 / \ / \ 8 7 9 2 / \ 9 2

重点在于匹配策略： 如果根节点不相等，则分别用A的左右子树，去和B匹配。两者任意一个匹配上，即匹配成功。 如果根节点相等，则分别用A的左右子树，去和B的左右子树匹配。两者均匹配，则匹配成功。 如果左右子树中有任何一个不匹配呢？匹配失败了吗？ 不对，此时依然可以用A的左右子树，去和B匹配。

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot1==nullptr || pRoot2==nullptr ) return false; if(pRoot1->val!=pRoot2->val){ return ( HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2) ); }else{ bool left=true,right=true; if(pRoot2->left) left=HasSubtree(pRoot1->left,pRoot2->left); if(pRoot2->right) right=HasSubtree(pRoot1->right,pRoot2->right); if(!(left &&right) ){ return ( HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2) ); }else{ return true; } } }

在这里，规定空树不是任何树的子树。其实如果规定：如果B是A的子树，那么B的左右子树，分别和A的左右子树，依然构成子树包含关系。那么空树，应该是任意树的子树才对。 上文因为顾忌子树为空的问题，不能让B树为空，所以当B有左右孩子时，才能进入左右孩子的递归过程。如果定义空树为任意树的子树，那么代码可以更简单：

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot1==nullptr) return false; if(pRoot2==nullptr) return true; if(pRoot1->val!=pRoot2->val){ return ( HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2) ); }else{ bool left=true,right=true; left=HasSubtree(pRoot1->left,pRoot2->left); right=HasSubtree(pRoot1->right,pRoot2->right); if(!(left &&right) ){ return ( HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2) ); }else{ return true; } } }