统计信息

  • 日志总数:266篇
  • 评论总数:149条
  • 分类总数:29个
  • 标签总数:234个
  • 友情链接:5个
  • 网站运行:3165天

2017年七月
« 6月   8月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  
  • Flag Counter
  • 留言本

  • 现在位置:    首页 > 算法导论 > 正文
    LeetCode_146: LRUCache 使用STL-list
    算法导论 暂无评论 阅读(120 views)

    在LeetCode的题目中,考察list操作的比较少,所以这道题也算是经典了,只有17%的通过率也足以说明问题。STL的list模板是一个环形双链表,其支持链表的基本操作,并且封装了reverse、sort、merge、splice等算法,为链表的操作提供许多遍历,这篇博客会根据在STL源码分析中的内容进行简单介绍。

    题目

    Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get andput.

    get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
    put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

    Follow up:
    Could you do both operations in O(1) time complexity?

    Example:

    分析

    这道题目,没做对很大程度上是因为没有理解题意。题目要求要求每次删除最久没有操作过的删去。于是这就是一个队列,每次操作了哪个元素,就将那个元素提到队列最前,每次删除时删除队尾就可以了。至于O(1)操作时间,则完全可以借助Hash表来实现。

    链表

    STL的LIST是一个环状的双向链表。关于LIST的实现,最好参考STL源码分析来理解。这里介绍list中封装的几个方法:splice、sort。还有一个merge算法,merge的输入要求连个链表都是排序好的。

    void sort():容器内所有元素排序,默认是升序

    template<class Pred>void sort(Pred pr):容器内所有元素根据预断定函数pr排序

    void swap(list& str):两list容器交换功能

    void unique():容器内相邻元素若有重复的,则仅保留一个

    void splice(iterator it,list& li):队列合并函数,队列li所有函数插入迭代指针it前,x变成空队列

    void splice(iterator it,list& li,iterator first):队列li中移走[first,end)间元素插入迭代指针it前

    void splice(iterator it,list& li,iterator first,iterator last):x中移走[first,last)间元素插入迭代器指针it前

    void reverse():反转容器中元素顺序

    代码

     

    本文版权归Deep Studio所有,转载引用请完整注明以下信息:
    本文作者:PengChao
    本文地址:LeetCode_146: LRUCache 使用STL-list | Deep Studio

    发表评论

    留言无头像?