1. 二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
取二维数组最中央的数字，该数字所在列和行把整个数字分为四块，左上方块的所有数字都比它小，右下方块的所有数字的都比它大，那么根据它与所求数字的大小关系，可以排除一个方格。每次的范围都缩小到原来的3/4，然后剩下的三个方块递归即可。
2.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
先遍历一遍，找出空格总数，得到替换后的长度。然后从后往前迁移修改，这样每个字符只需要移动一次，如果从前往后，那么每碰到一个空格，空格后面的字符都要移动一次。
3.从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
思路：建一个新链表，是原链表的反转的链表，从后往前链接，然后再打印。
4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树--->根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
前序遍历的第一个数字是根节点，中序遍历的根节点的左边的数是左子树，右边的数是右子树。根据前序遍历的第一个数字1是根节点，然后在中序遍历中得到根节点1和根节点的左子树{4,7,2}和右子树{5,3,8,6}，然后前序遍历中{2,4,7}{3,5,6,8}也是左右子树的前序遍历，{4,7,2}{5,3,8,6}也是左右子树的中序遍历，然后即可得到第二层的根节点，由此迭代，可以还原二叉树。
5.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：
栈：LIFO，队列：FIFO
一个做push栈，一个做pop栈，在做push操作的时候把数据全部push到push栈中，如果要pop，就把数据从push栈中一个一个pop出来然后push进pop栈，然后pop，如果要push就再把pop栈中的数全部pop出来push进push栈，知道pop栈空，然后再push新的数。
6.旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：
旋转数组分为两段，两端都是递增的，而且第二段的所有数比第一段的任何数字都小，最小的数字是第一个比第一个数字小的数。二分法查找，如果找到的数字比第一个数字大，就往后找，比第一个数字小，就往前找，直到把查找范围缩到一个数字。
网友评论