前言

算起来应该是上周四开始投简历的，到现在一共收到两个面试通知，其中有一个还是非计算机专业的，面试的是股票交易员，此处有笑哭脸。另外一家就是今天要讲述的：我面试的这个职位。我先卖个关子，讲讲我之前面试的经验，以及我现在的决定。 more >>

问题描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8,6}，则重建出图所示的二叉树并输出它的头结点。

问题描述
用两个栈来实现一个队列
分析
这个题目其实是在考你对栈和队列的性质是否掌握的是否清晰明白。刚开始我大致想了几分钟没有想出来，后来去看了剑指offer上的指导，发现跟我想的是蛮接近。现在我再来捋一下思路，首先是实现队列，队列的性质是先进先出，而此时实现的条件是通过两个栈来实现。我们可以先考虑把元素存起来，也就是入队操作，因为你这个函数不可能什么也不做，最基础的一部肯定是要先存储起来。所以第一步操作就是将入队的元素存储在s1中，s1需要入栈来存储这些元素。如果此时需要出队呢？我们一定是要把s1中栈底的元素出队，而此时他却在栈底，通过将s1的出栈的元素在入进s2，那么s1的栈底元素也就变成了s2的栈顶元素，如果此时出队就是s2的出栈操作。这里有个限制操作就是， more >>

前言

为什么要写这一篇呢？原因是我不够熟练，大多时候，比如说要写一个栈，我想一想是能够写出来了，可是当我再去细致思考时，比如我用什么来实现呢？数组，链表。有比如我用数组去实现队列，是用循环队列呢？还是普通队列。我现在又想起这些问题的时候，我发现还是自己掌握的不够扎实。还有一点就是记忆，我刚去看了之前写的哈夫曼，虽然也用到了树结构，但是现在又去看，还是觉得在基础上模模糊糊的，虽然也敲了很多天代码才写成，但是什么也没有留下。所以这次决定从线性结构到图，把一般常用的数据结构以及算法再梳理一遍，所以这篇文章应该会比较长。 more >>

问题描述
请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。
分析
暴力
找到空格就进行替换，按到常理的思路是按照从前往后的顺序题替换，这样每替换一次就要移动元素一次，故时间是O(n^2)
从后往前 more >>

问题描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析
思路1
查找的暴力思路，O(n^2) more >>