LRU缓存 Least Recently Used (LRU) cache. 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。…
二叉树的非递归前中后序遍历
非递归的思路。 个人感觉这句话很有用。 本质上是在模拟递归,因为在递归的过程中使用了系统栈,所以在迭代的解法中常用Stack来模拟系统栈。 中序遍历 左根右,在递归的时候,如果当前节点有左子树,我们就递归左子树,然后输出…
剑指Offer20-二叉搜索树的后序遍历序列
题目 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路 开始还是没有头绪,看了书。 感觉大部分还是计算机的一个非常重要的思想…
剑指Offer19-栈的压入、弹出序列
题目 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但…
剑指Offer18-包含min函数的栈
包含min函数的栈 要求O(1)的时间完成正常的栈操作,以及获取栈中最小元素的操作 思路 首先可能想到用一个辅助变量存最小值。但是当这个最小值被弹出,就不能以O(1)的时间找到次小值。因此次小值也许需要在push的时候存…
剑指Offer17-反转链表
题目 反转链表,思路一直接用栈转置一下链表,思路二,记录前驱。因为链表结点的移动需要知道next,而修改当前结点的next节点为前一个结点修改了next,所以再需要一个变量寸当前节点的next,也就是需要,前驱,当前,后…