文章目录
- 06从尾到头打印链表
- 03数组中重复的数字
- 04二维数组中的查找
- 05 替换空格
- 06重建二叉树
- 背英语单词,看了二十页
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) ;