剑指offer上的题目学习笔记整理和记录。
1.替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
编程
经验
- 注意StringBuffer和String的区别，string可以直接利用replace方法实现替换的功能，而StringBuffer中并没有相关的方法，所以在编程时需要先将stringBuffer转换为string。
- 可结合源码理解String的replace方法的实现。
参考
2.二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
编程
思路：矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时。右移要查找数字比左下角数字小时，上移。
经验
- 注意二维数组的行列长度的区分和获取，以及二维数组中元素下标和行列的关系。
- 如果给的是一个有序的数组或者序列，那么肯定有比整个遍历一遍效率更高的处理方法，也就是说我们在处理大量可排序元素时，可考虑排序后再处理。
报错
Java compile error: “reached end of file while parsing }”——也就是少了一个“}”
参考
3.从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
编程
思路1：利用递归。
思路2：利用java中的栈这一数据结构（由于其具有先进后出的特点）。
经验
- 注意对于Java编程中常用的数据结构及对应特点和应用场景及基本操作的积累。
- 注意在定义各种数据结构时的数据类型的定义（详见报错）。
- 注意积累其他的可能解法。
这种方法还可以简化为直接在链表头插入节点的思路，或者利用数组进行翻转。
报错
在定义栈时如果不定义整型栈，就会报错如下图——
参考
java 中几种常用数据结构
8种java常见数据结构及优缺点
Java关于链表的增加、删除、获取长度、打印数值的实现
java链表的各种操作
Java的ArrayList操作
Java集合的Stack、Queue、Map的遍历
java 栈的基本操作
栈操作编程题
4.重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
编程
思路：利用递归。
经验
- 编程之前先思考出思路，如果有多重循环并且每重循环都有相同的规律和处理逻辑就可以考虑递归。
- 注意在递归操作时对于某些边界条件的判断，如是否为空等。
- 注意积累Java对于数组的基本操作。
报错
注意如果result赋值语句的位置不对，就会报错如下图——
参考
5.用2个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
编程
思路：队列是先入先出，而栈是先入后出。
经验
- 注意要考虑多种可能的输入情况，最开始的编程实现如下图，虽然可以通过牛客网上的测试用例，但对于某些情况下的处理会失败（比如stack2中元素个数>1的情况）。
参考
6.旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
编程
思路：当找到临界点的时候（即某一个元素大于后一个元素时即可），最坏情况下时间复杂度为O(n)。
经验
- 如果想要提高时间效率，则可采用二分法(需要查找序列是有序序列)进行查找，时间复杂度为O(logn)。
疑问
- 上图二分查找法实现中，如果
forward = mid而不是forward = mid+1，则程序不能在规定时间内运行完成。原因在于——
如果forward = mid，那么可能存在一个forward、mid、tail的值使得每次计算出的forward和mid值都相等，程序就会陷入死循环。
- 那么为什么是
tail = mid而不是tail = mid-1呢？
- 为什么将中间值和前面的值进行比较只能通过40%的测试用例呢？
