面试题1:赋值运算符函数
类型CMyString，请为该类型添加赋值运算符函数。
CMyString & CMyString::operator = (const CMyString & str)
{
if(this == &str)
return *this;
delete [] m_pData;
m_pDate = NULL;
m_pData = new char[strlen(str.m_pData) + 1];
strcpy(m_pdata, str.m_pData);
return *this;
}
-
只有返回一个引用（*this），才可以被连续赋值。
-
参数设置为引用，防止从形参到实参调用复制构造函数。
-
释放自己本身的内存，防止程序发生内存泄漏。
-
要判断传入参数和*this是否是同一个实例。
面试题3:二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上倒下递增的顺序排列。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含该整数。
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找结束；
如果该数字大于要查找的数字，剔除这个数字所在的列；
输入该数字小于要查找的数字，剔除这个数字所在的行。
- STL中的vector每次扩充容量时，新的容量都是前一次的两倍。
面试题4:替换空格
请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy”
假设我们要在原来的字符串上做替换，并且输入的字符串后面有足够多的空余内存。
首先遍历一次字符串，统计处字符串中空格的总数，计算出替换后字符串的总长度。
从字符串的后面开始复制和替换。准备两个指针p1和p2，分别指向原字符串的末尾和替换后字符串的末尾。
一步步向前移动p1，逐个把它指向的字符复制到p2未知。如果p1指向的是空格，就变成“%20”。
- 合并两个数组时，如果从前往后复制每个数字需要重复移动数字多次，那么我们可以考虑从后往前复制，这样能减少移动的次数，提高效率。
面试题5:从尾到头打印链表
输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
链表遍历的顺序是从头到尾的顺序，输出的顺序却是从尾到头，这就是典型的后进先出，我们可以用栈来实现这种顺序。
stack<ListNode *> nodes
面试题6:重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，重建二叉树并输出头节点。
前序遍历的第一个数字是根节点的值，扫描中序遍历，就能确定根节点的值的位置。
根据中序遍历的特点，根节点的值前面的就是左子树的值，根节点的值后面的就是右子树的值。
可以用递归实现。
面试题7:用两个栈实现队列
用两个栈实现一个队列。请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。
我们有两个栈stack1和stack2。
插入的时候都是直接用stack1.push(element)。
删除的时候：当stack2中不为空时，stack2中栈顶的元素就是最先进入队列的元素，可以弹出。如果stack2为空，我们就把stack1中的元素逐个弹出并压入stack2，因为先进入stack1的元素在栈底，经过弹出并压入之后处于stack2的栈顶，可以直接弹出。
番外题：快速排序
实现快拍的关键在于现在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字放在数组的左边，比选择的数字大的数字放在数组的右边。
int Partition(int data[], int length, int start, int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
throw new std::exception("Invalid Parameters");
srand((unsigned)time(NULL));
int index = start + rand() % length;
Swap(&data[index], &data[end]);
int small = start - 1; //保存一个指针，该指针前面的值数字都比选中的数字小。
for(int i = start; i < end; i++)
{
if(data[i] < data[end])
{
small++;
if(small != i)
swap(&data[i], &data[small]);
}
}
small++;
swap(&data[small], &data[end]);
return small;
}
这个函数贼鸡儿好使，Markdown
然后就可以用递归的思路分别对左右两边排序。
void QuickSort(int data[], int length, int start, int end)
{
if(start == end)
return ;
int index = Partition(data, length, start, end);
if(index > start)
QuickSort(data, length, start, index -1);
if(index < end)
QuickSort(data, length, start + 1, end);
}
番外题：堆排序
堆排序最重要的一个函数是调整堆。
void HeapAdjust(int *data,int i,int size) //调整堆
{
int left = 2 * i; //i的左孩子节点序号
int right = 2 * i + 1; //i的右孩子节点序号
int maxIndex = i; //最大的节点序号
if(i < size / 2) //如果i是叶节点就不用进行调整
{
if(left <= size && data[left] > data[maxIndex])
{
maxIndex = left;
}
if(right <= size && data[right] > data[maxIndex])
{
maxIndex = right;
}
if(maxIndex != i)
{
swap(data[i], data[maxIndex]);
HeapAdjust(data, maxIndex, size); //递归，避免调整之后以maxIndex为父节点的子树不是堆
}
}
}
首先是建立最大堆，然后依次把最大的元素放到数组的最后。
void HeapSort(int *data,int size) //堆排序
{
//建立最大堆
for(int i = size / 2; i >= 0; i --)
{
HeapAdjust(data, i, size);
}
//每次把堆顶元素和最后一个元素交换
for(int i = size; i >= 1; i --)
{
swap(a[0],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
HeapAdjust(data,0,i-1); //重新调整堆顶节点成为大顶堆
}
}
面试题8:旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1
旋转之后的数组实际上可以分为两个排序的数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。
我们可以采用二分查找法，找到数组中间的元素，如果该中间元素位于前面的递增数组，它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于中间元素的后面。
反之，如果该中间元素位于后面的递增数组，它应该小于等于第二个指针指向的元素。此时数组中最小的元素应该位于中间元素前面。
而当数组的第一个元素小于最后一个元素，说明数组已排序，可以直接返回第一个数字了。
特例：如果当第一个元素，中间元素，最后一个元素都相等时，我们无法判断中间数字位于前面还是后面，此时需要顺序查找该段。
面试题9:斐波那契数列
写一个函数，输入n，求斐波那契数列的第n项。
f(0) = 0
f(1) = 0
f(n) = f(n-1) + f(n-2)
一步步迭代即可，复杂度为O(n)
面试题9.2:青蛙跳台阶问题
一只青蛙一次可以跳上1个台阶，也可以跳上2个台阶，求该青蛙跳上一个n级的台阶一共有多少种跳法。
面试题10:二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把0表示成1001，有2个1.因此如果输入9，则输出2.
常规思路：一步步判断每一位是否是1.可以用1«i然后和该数做与运算，如果结果为1，说明第i位是1.
惊喜思路：把一个整数减1，再和原整数做与运算，会把该整数最右边的一个1变成0.
int NumberOf1(int n)
{
int count = 0;
while(n)
{
count++;
n = (n - 1) & n;
}
return count;
}
面试题11：数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
-
考虑底数为0的情况。
-
考虑指数为负数的情况。
惊喜思路：
当n为偶数：pow(a, n) = pow(a, n/2) * pow(a, n/2)
当n为奇数：pow(a, n) = pow(a, (n-1)/2) * pow(a, (n-1)/2)
面试题12:打印1到最大的n位数
输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，打印出1，2，3一直到最大的3位数999.
全排列问题，用递归实现
void PrintRecursively(char * number, int length, int index)
{
if(index == length - 1)
{
PrintNumber(number);
return ;
}
for(int i = 0; i < 10; i++)
{
number[index + 1] = '0' + i;
PrintRecursively(number, length, index + 1);
}
}
面试题13:在O(1)的时间内删除链表节点
给定单向链表的头指针和一个节点指针，定义一个函数在O(1)的时间删除该节点。
要删除一个节点i，我们需要把i前面节点的next指针指向i后面的节点j。
我们可以将j的内容复制到i，然后让i的next指针指向j后面的节点。效果就是把i节点给删除了。
面试题14:调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整数组中的数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
快速排序中Partition的应用。
面试题15:链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。
为了实现遍历链表一次就可以找到倒数第k个节点，我们定义两个指针p1和p2。
p1先从链表的头指针向前走k-1步，p2不动。
然后从第k步开始，两个指针一起向前移动。当p1走到链表的尾节点时，p2刚好在倒数第k个节点。
面试题16:反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
h –> i –> j 假设当前遍历到节点i，h之前的链表已经反转完成。 h <– i j 我们需要将i的next指针指向h，而在此之前我们需要一个指针指向j，防止节点i处断开。
ListNode * ReverseList(ListNode * pHead)
{
ListNode * pReversedHead = NULL;
ListNode * pNode = pHead; //i
ListNode * pPrev = NULL; //h
ListNode * pNext = NULL; //j
while(pNode != NULL)
{
pNext = pNode->m_pNext;
if(pNext == NULL)
pReversedHead = pNode;
pNode->next = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
面试题17:合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。
合并排序问题。
每次比较两个链表的头节点，值较小的头节点作为新链表的下一个节点。
面试题18:树的字结构
输入两颗二叉树A和B，判断B是不是A的字结构。
- 第一步在树A中查找与B根节点的值一样的节点，这实际是树的遍历。递归。
- 第二步判断树A中以R为根节点的子树是不是和树B有相同的结构。递归。
面试题19:二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像
我们先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左右孩子之后，就得到了树的镜像。
面试题20:顺时针打印矩阵
输入一个矩阵，按照从外到里以顺时针的顺序依次打印出每一个数字。
由于是从外圈到内圈依次打印，我们可以把矩阵想象成若干个圈。
每个圈的起点，即左上角的点的行标startX和列标startY总是相同的。循环继续的条件是startX * 2 < row && startY * 2 < col。
打印每一圈需要横竖弯勾四步，条件如下：
- 第一步必须。
- 第二步需要终止行号endX大于起始行号startX。（至少两行）
- 第三步需要终止列号endY大于起始列号startY。（至少两行两列）
- 第四步需要终止行号endX比起始行号startX大2。（至少三行两列）
面试题21:包含min函数的栈
定义栈数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min，push和pop的时间复杂度都是O(1)
除了数据栈之外，我们每次把最小元素都保存起来放到另外一个辅助栈中。
如果每次把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。
面试题22:栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字都不相等。
维护一个栈。
如果下一个弹出的数字刚好是栈顶元素，那么就直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶位置。
面试题23:从上往下打印二叉树
从上往下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
先进先出，使用队列来遍历
面试题24:二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是返回true，否则返回false。假设输入的数组的任意两个数字都不相同。
在后序遍历得到的序列中，最后一个数字是树的根节点的值。
数组中前面的数字可以分为两部分：第一部分是左子树的节点，都比根节点的值小；第二部分是右子树的节点的值，都比根节点的值大。
面试题25:二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
前序遍历的方式访问二叉树。用一个栈来记录路径
开始时把该节点压到栈中，并累加该节点的值。符合要求就打印出路径。如果当前节点不是叶节点，继续访问其子节点。最后记得返回父节点之前把该节点弹出栈。
面试题26:复杂链表的复制
请实现函数ComplexListNode * Clone(ComplexListNode * pHead)，复制一个复杂链表。在复杂链表中，每个节点除了有一个m_pNext指针指向下一个节点外，还有一个m_pSibling指向链表中的任意节点或者NULL。
常规思路：
第一步复制原始链表上的每一个节点，并用m_pNext链接起来；第二步是设置每个节点的m_pSibling指针。
优化思路：
- 复制链表的每个节点N，得到N’，但是把N’放在N的后面。
- 假设N的m_pSibling指向S，那么其对应复制出来的N’是N的m_pNext指向的节点，同样S’是S的m_pNext指向的节点。
- 把新链表拆分成两个链表：把奇数位置的节点链接起来就是原始链表；把偶数位置的节点链接起来就是复制链表。
面试题27:二叉搜索树与双向链表
输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
在二叉搜索树中，左子节点的值总是小于父节点的值；右子节点的值总是大于父节点的值。
中序遍历的结果就是从小到大的顺序排列。因此可以在中序遍历的过程中建立双向链表。
/**
* pNode 当前节点
* pLastNodeInList 记录已拍好序的最后一个节点，起始就是中序遍历中的上一个遍历到的节点
*/
void ConvertNode(BinaryTreeNode * pNode, BinaryTreeNode ** pLastNodeInList)
{
if(pNode == NULL)
return ;
BinaryTreeNode * pCurrent = pNode;
if(pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
pCurrent->m_pLeft = *pLastNodeInList;
if(*pLastNodeInList != NULL)
(*pLastNodeInList)->m_pNext = pCurrent;
*pLastNodeInList = pCurrent;
if(pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
面试题28:字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出字符a, b, c所能排列出的所有字符串abc,acb,bac,bca,cab,cba。
常规思路：
典型的dfs遍历，带上剪枝。 然而，如果采用这种方法，剪枝也是消耗时间的。 如果每次把剩余的字符作为一个参数传给递归函数，可以省去剪枝的时间开销，那么空间又会有很大开销。
优化思路：
还是按照dfs的路子走，但是采用Permutation(char * pStr, char* pBegin)来进行递归，pBegin是dfs层数。每次拿第pBegin个字符和后面的字符依次交换位置来划分下一层。
这种方法既不需要额外的剪枝时间，又不需要额外的空间开销。机智如你，双击666.
面试题29:数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组一半的数字。即长度为n的数组中的第n/2大的数字。
基于快速排序中的Partition函数可以在O(n)的时间内找到数组中第k大的数字。
面试题30:最小的k个数
输入n个整数，找出其中最小的k个数。
方法一：利用Partition函数在O(n)的时间内找到第k小的数字。
方法二：用一个最大堆保存k个数，每次从数组中拿一个数和堆顶元素比较，如果该数比堆顶元素小，则把堆顶元素删除，把该数插入最大堆。
面试题31:连续子数组的最大和
输入一个整形数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
动态规划
if f(i-1) <= 0, f(i) = data[i]
if f(i-1) > 0, f(i) = f(i-1) + data[i]
面试题32:从1到n整数中1出现的次数
输入一个整数n，从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。
转换成一个排列组合问题
例如1～21345划分成1～1345和1346～21345两段。
1346～21345可以分为最高位为1的和其他位为1的来考虑。
递归计算1～1345这段。
面试题33:把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3, 32, 321}，则打印出这3个数字能排成的最小数字321323.
两个数字m和n能拼接成mn和nm。如果mn < nm，那么我们应该打印出mn，也即m应该排在n的前面。
这也就转换成了一个自定义规则的排序问题。
面试题34:丑数
我们把只包含因子2，3和5的数称作丑数。求按从小到大的顺序的第1500个丑数。例如6，8都是丑数，但是14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。
我们创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或5得到的。
用3个指针分别记录上次乘以2，3或5的3个丑数。
每次生成新的丑数的时候，拿出上一步的三个数分别乘以2，3和5，取最小值作为新的丑数。并把指针后移一位。
面试题35:第一个只出现一次的字符
在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b’。
利用哈希表。key为字符，value为该字符出现的次数。
面试题36:数组中的逆序对
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数
利用归并排序
先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。
面试题37:两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如果两个链表有公共节点，那么公共节点出现在两个链表的尾部。如果我们从链表的尾部向前比较，最后一个相同的节点就是我们要找的节点。
方法一：后进先出，利用两个栈。
方法二：先遍历两个链表，得到长度。就知道了长链表比短链表长多少步。就先让长链表走这么多步，然后一起走。找到的第一个相同的节点，即为所求。
面试题38:数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
二分查找法分别查找第一个k和最后一个k。
第一个k：如果中间数字是k，如果前面一个数字也是k，则第一个k在数组前半段，否则中间数字就是第一个k。 最后一个k：如果中间数字是k，如果后面一个数字也是k，则最后一个k在数组后半段，否则中间数字就是最后一个k。
面试题39:二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根，叶节点）形成树的一条路径，最长路径的长度为树的深度。
后序遍历，树的深度是左子树和右子树深度较大值+1.
面试题39.2:是否是平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树
后序遍历，在遍历左右节点之后，根据左右子节点的深度判断它是不是平衡的，并得到当前节点的深度。
面试题40:数组中只出现一次的数字
一个整形数组里除了两个数字之外，其他数字都出现了两次。请写出程序找出这两个只出现一次的数字。时间复杂度O(n)，空间复杂度O(1)。
异或运算：任何一个数字异或它自己为0.
从头到尾依次异或数组中的每一个数字，得到一个结果num0 ^ num1.
在结果数字中找到第一个为1的位的位置，记为第n位。根据该位是不是1把原数组中的数字分为两个子数组。
分别异或两个子数组中的每一个数字，就得到两个数。
面试题41:和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
定义两个指针p1和p2，分别指向数组第一个元素和最后一个元素。
如果两个元素的和大于s，把p2左移；
如果两个元素的和小于s，把p1右移； 如果两个元素的和等于s，输出。
面试题41.2:和为s的连续正数序列
输入一个正数s，打印出所有和为s的连续正数序列（至少包含两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3个连续序列1～5，4～6，7～8.
用两个数small和big表示序列的最小值和最大值。
初始化small和big为1和2；
如果从small到big和大于s，增加small； 如果从small到big和小于s，增加big；
一直增加small到(1+s)/2为止。
面试题42:翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为了简单起见，标点符号和普通字符一样处理。例如输入字符串“I am a student.“，则输出”student. a am I“。
第一步：翻转句子中的所有字符。
第二步：翻转每个单词中字符的顺序。
面试题42.2:左旋转字符串
字符串的左旋转操作是把字符串前面的若干个k字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串“abcdefg”和数字2，则该函数返回左旋转2位得到的结果“cdefgab”。
第一步：翻转前k个字符。
第二步：翻转后n-k个字符。
第三步：翻转所有字符。
面试题43:n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
方法一：递归DFS。
方法二：用两个数组来存储骰子点数的每一个总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一次循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n-1，n-2，n-3，n-4，n-5和n-6的次数的总和。
面试题44:扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
首先把数组排序，再统计数组中0的个数（大小王）。
统计排序后数组中相邻数字之间的空缺总数。
如果空缺总数小于或者等于0的个数，那么数组连续；否则不连续。 注意：数组中非0元素只能出现一次。
面试题45:圆圈中最后剩下的数字
0，1～n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
用环形链表模拟圆圈std:list。其本身不是环形结构，因此当迭代器扫描到链表末尾时，手动把迭代器移动到头部。
面试题46:求1+2+…+n
要求不能使用乘除法，for，while，if，else，switch，case等关键字及条件判断语句（A?B:C）。
利用构造函数来模拟循环迭代。
面试题47:不用加减乘除做加法
写一个函数，求两个整数之和。要求在函数体内不得使用加减乘除。
第一步：不考虑进位，做异或。
第二步：考虑进位，做与运算。
第三步：两者相加，迭代。
面试题48:不能被继承的类
用C++设计一个不能被继承的类
把构造函数设为私有函数。
面试题49:把字符串转换成整数
检查空指针。
检查正负号。非法输入等。
面试题50:树中两个节点的最低公共祖先
如果是二叉搜索树
二叉搜索树是排序过的。位于左子树的节点都比父节点小，位于右子树的节点都比父节点大。
从根节点开始和两个输入的节点比较。如果当前节点比两个节点值都大，则最低公共祖先在左子树；如果当前节点比两个节点值都小，则最低公共祖先在右子树；如果当前节点比一个大，比一个小，即为所求。
如果有指向父节点的指针
如果树中的每个节点都有一个指向父节点的指针，这个问题就转换成了求两个链表的第一个公共节点。
普通二叉树
用两个链表分别保存从根节点到输入的两个节点的路径，然后把问题转换成两个链表的最后公共节点。
面试题51:数组中重复的数字
在一个长度为n的数组里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出任意一个重复的数字。
哈希表做法。空间复杂度O(n)。
重排数组法。
从头到尾扫描数组中的每个数字。当扫描到下标为i的数字时，比较这个数字m是不是等于i，是就继续；如果不等，拿m和第m个数字比较，如果相等，就找到了重复数字。如果不相等，把m和第m个数字交换，把m放到它属于的位置。
面试题52:构建乘积数组
给定一个数组A[n]，请构建一个数组B[n]，其中B中的元素B[i] = A[0] * A[1] * … * A[i-1] * A[i+1] * … * A[n-1]。不能使用除法。
定义两个数组。
C[i] = A[0] * A[1] * … * A[i-1]
D[i] = A[i+1] * … * A[n-1]
B = C * D。
面试题53:正则表达式匹配
请实现一个函数用来匹配包含‘.’和‘’的正则表达式。模式中的字符‘.’表示任意一个字符，而’‘表示它前面的字符可以出现任意多次（含0次）。在本题中，匹配是指字符串的所有字符匹配某个模式。
- 如果第二个字符不是*：如果该字符与模式相匹配，在字符串和模式上后移一位，否则返回false。
- 如果第二个字符是*: 2.1. 模式后移两个字符，相当于a*被忽略。
2.2. 字符串后移一个字符，模式后移二个字符，相当于a*匹配一个a。
2.3. 字符串后移一个字符，模式不变，相当于a*匹配多个a。
面试题54:表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
就是一步步匹配
面试题55:字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出两个字符“go”时，第一个只出现一次的字符是“g“。当从字符流中读出前六个字符”google“时，第一个只出现一次的字符是”l“。
哈希表
第一次出现，值记为下标
第二次出现，值记为-1.
面试题56:链表中环的入口节点
一个链表中包含环，如何找出环的入口节点？
第一步：用一快一慢两个指针，如果两指针相遇，则相遇节点p1在环内。
第二步：从p1遍历，再次回到p1，记录走的步数即为环中节点个数n.
第三步：用两个指针p2和p3，从链表头开始，p2先走n步，然后俩指针一起走，两指针相遇于入口。
面试题57:删除链表中重复的节点
在一个排序的链表中，如何删除重复的节点？
从头遍历整个链表。如果当前节点的值与后面节点的值相同，那么它们都应该被删除。**
面试题58:二叉树的下一个节点
给定一颗二叉树和其中的一个节点，如何找出中序遍历顺序的下一个节点？树中除了有两个分别指向左右子节点的指针以外，还有一个指向父节点的指针。
- 如果该节点有右子树，那么它下一个节点就是右子树的最左子节点。
- 如果该节点是它父节点的左孩子，那么下一个节点就是它的父节点。
- 如果该节点是它父节点的右孩子，那么沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。
面试题59:对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
比较前序遍历和翻转前序遍历的序列是否一致（考虑NULL指针）。
面试题60:把二叉树打印成多行
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印一行。
用一个队列保存将要打印的节点。
为了把二叉树的每一行单独打印到一行，需要保存当前层还没有打印的节点数，和下一层节点的总数。
面试题61:按之字形顺序打印二叉树
请实现一个函数按之字形打印二叉树，即第一行按从左到右打印，第二行按从右到左打印，第三行再从左到右打印。
用两个栈来保存将要打印的节点。
如果当前打印的是奇数层，则先保存左子节点，后保存右子节点到第一个栈；
如果当前打印的是偶数层，则先保存右子节点，后保存左子节点到第二个栈。
面试题62:序列化二叉树
请实现两个函数，分别用来序列话和反序列化二叉树
前序遍历的方法序列话，遇到NULL时用特殊字符“$“代替。
面试题63:二叉搜索树的第k个节点
给定一棵二叉搜索树，请找出其中的第k大的节点。
中序遍历，找出第k个。
面试题64:数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序后位于中间的数。如果从数据流读出偶数个数值，那么中位数就是所有数值排序后中间两个数的平均值。
方法一：利用Partition函数查找中位数。
方法二：利用一个最大堆保存左半边的数据，利用一个最小堆保存右半边的数据，总是保证左边的数据小于右边的数据。
面试题65:滑动窗口的最大值
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}
利用一个队列，保存有可能成为滑动窗口最大值的数值。
在存入一个数字的下标之前，首先判断队列里已有的数字是否小于待存入的数字。如果已有的数字小于待存入的数字，这些数字已经不可能是滑动窗口的最大值，因此它们将会依次从队列的尾部删除。
面试题66:矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵任意一格开始，每一步可以在矩阵中上下左右移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
回溯法
面试题67:机器人的运动范围
地上有一个m行n列的放歌。一个机器人从坐标0，0的格子开始移动，它每一次可以上下左右移动一格，但不能进入行坐标和列坐标的位数之和大于k的格子。请问机器人能够达到多少个格子？
回溯法