面试题1：
题目描述：
如下为类型CMyString的声明，请为该类型添加赋值运算符函数。
class CMyString
{
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
private:
char* m_pData;
};
思路： 现代写法，传一个临时参数tmp,然后将tmp的m_pData值与this指针指向的值进行交换，就实现了运算符的重载。
注：tmp出了作用域会自动调用析构函数释放，所以当tmp区域与this指向的为同一区域时，tmp释放，则this指针
指向的区域也释放了，就会出现问题，所以需要加上条件(this!=&str)。
代码：
CMyString& CMyString::operator=(const CMyString& str)
{
if (this != &str)
{
CMyString temp(str); char* data = temp.m_pData;
temp.m_pData = this->m_pData;
this->m_pData = data;
}
return *this;
}
面试题3：
题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入描述：
array： 待查找的二维数组
target：查找的数字
输出描述：
查找到返回true，查找不到返回false
思路：从二维数组的左下角开始找，若当前位置比target小，则向右移；反之，向上移动。
代码：
class Solution
{
public:
bool Find(vector<vector<int> > array,int target)
{ int row =array.size(); //行
int col=array[].size(); //列
int x=row-; //横坐标
int y=; //纵坐标
while(x>= && y<col)
{
if(array[x][y]>target) //当前位置值>target，上移
x--;
else if(array[x][y]<target) //当前位置值<target，右移
y++;
else
return true;
}
return false;
}
};
面试题4：
题目描述：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：先计算空格个数，str原长及新长度，然后从后向前拷贝，避免内存覆盖
代码：
//假定length为系统规定字符串输出的最大长度，固定为一个常数
class Solution
{
public:
void replaceSpace(char *str,int length)
{
if(str==NULL||length<)//当str为空或最大长度非法，则返回
{
return;
}
int len=;//str的长度
int blank=;//空格的个数
int i=;
while(str[i]!='\0')
{
if(str[i++]==' ')
blank++;
len++;
}
int newlen=len+*blank;//str替换后新的长度
if(newlen>length)//新长度<系统分配的最大长度时，返回
return; //str的替换过程，从后向前拷贝
while(len>= && newlen>len)
{
if(str[len]!=' ')
str[newlen--]=str[len];
else
{
str[newlen--]='';
str[newlen--]='';
str[newlen--]='%';
}
len--;
}
}
};
面试题5：
题目描述：
输入一个链表，从尾到头打印链表每个节点的值。
输入描述：
输入为链表的表头
输出描述：
输出为需要打印的“新链表”的表头
思路：递归，直至找到最后一个节点，进行打印。
代码：
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(struct ListNode* head)
{
vector<int> tail;
if(head!=NULL)
{
if(head->next!=NULL)
tail=printListFromTailToHead(head->next);
tail.push_back(head->val);
}
return tail;
}
};
面试题6：
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：前序遍历的第一个节点为根节点root，再根据中序遍历的结果，查找到中序遍历结果中与root值相等的位置index,
则该值左边的为左子树的节点，右边的为右子树的节点。然后以左、右子树为子问题，递归调用函数重建子树。
代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in)
{
int Size = in.size();//遍历这棵树的节点数
if(Size == ) //树为空
return NULL;
vector<int> preLeft, preRight, inLeft, inRight;
int val = pre[]; //根节点的值（前序遍历的第一个值）
TreeNode* node = new TreeNode(val);//构建根节点
int index = ;
for(index = ; index < Size; ++index)
{
if(in[index] == val) //在前序遍历结果中查找根节点值的位置
break;
}
for(int i = ; i < Size; ++i)
{
if(i < index)//在中序遍历结果中，在根节点前的值均为二叉树的左子树的值
{
//构建左子树
inLeft.push_back(in[i]);
preLeft.push_back(pre[i+]);
}
else if(i > index)
{
//构建右子树
inRight.push_back(in[i]);//Construct the right pre and in preRight.push_back(pre[i]);
}
}
//分为子问题，递归调用
node->left = reConstructBinaryTree(preLeft, inLeft);
node->right = reConstructBinaryTree(preRight, inRight);
return node;
}
};
面试题7：
题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路： 两个栈实现一个队列，记两个栈分别为stack1、stack2。入队列操作，即为入栈stack1操作；
而出队列可先将stack1中的数据全部push到stack2中，两次先进后出，使得stack2中数据顺
序就是队列先进先出的顺序，然后再将stack2的top数据pop即可。
但须注意的是：将stack1中数据push到stack2之前，徐判断stack2是否为空：
1）若为空，则将stack1中数据全部push进来后在pop它的top数据。
2）若stack2中原本就有数据，则需先将stack2中原有的数据先pop
代码：
class Solution
{
public:
void push(int node) //直接将数据入stack1，先进后出一次
{
stack1.push(node);
}
int pop()
{
if(stack2.empty())//若stack2为空，将stack1的数据全push进stack2中，先进后出二次(stcak2中的数据顺序为队列中的数据顺序)
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
int top=stack2.top();//保存stack2的顶部数据
stack2.pop();//将stack2中的顶部元素pop出去
return top;
}
private:
stack<int> stack1;
stack<int> stack2;
};