8.6 day07 休息+剑指offer

06从尾到头打印链表

从尾到头遍历链表
方法一就是用栈来辅助，栈的结构是先进后出的，将链表中的元素加入到栈中去，然后一个个弹出来。
方法二 递归，递归到链表的尾部，然后返回，将所有的元素添加到集合中去，再将集合转为数组返回。

03数组中重复的数字

找到数组中重复的数字，刚开始采用的是hash表，用map集合来写，但是过于复杂，其实一个数组就行了，遍历对应的数组，如果在数组中没有，那么就对应的值++，如果对应的值不等于0，那么就找到了，直接返回这个数即可

04二维数组中的查找

这样的一个矩阵，想要查询一个数是否在其中，刚开始的思路是：将二维数组转为一维数组，然后排序，在用二分进行查找。但是时间复杂度较高，不便于操作。
观察发现，从左下角或者右上角看，类似于一个二叉树，对于一个节点，左边的值小于它，右边的值大于它，所以这是一个二叉树。那么就从左下角开始，如果当前的值小于目标值，那么对应的行需要减减，如果大于目标值，对应的列需要加加;

05 替换空格

可以直接用api进行拼接，其他方法是用StringBuilder进行拼接，将字符串转为字符数组，遇到空格，拼接”%20“；其他拼接字符，最后再return sb.toString（）;

06重建二叉树

前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
递推参数： 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ；

终止条件： 当 left > right ，代表已经越过叶节点，此时返回 null ；

递推工作：

建立根节点 node ： 节点值为 preorder[root] ；
划分左右子树： 查找根节点在中序遍历 inorder 中的索引 i ；
为了提升效率，使用哈希表 dic 存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1) ；

背英语单词，看了二十页