剑指offer刷题笔记1

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。

思路：

旋转数组分为两段，两端都是递增的，而且第二段的所有数比第一段的任何数字都小，最小的数字是第一个比第一个数字小的数。二分法查找，如果找到的数字比第一个数字大，就往后找，比第一个数字小，就往前找，直到把查找范围缩到一个数字。