Revisit:

Leave a comment

October 29, 2016 by oneOokay

  1. LRU Cache

大概两个月前做过的题目:https://wordpress.com/post/oneokay.wordpress.com/929

Revisit的时候的想法是从Queue或者Stack里面选一种结构来实现:选了queue,因为FIFO。用一个hashmap来实现查找(不要用dictionary,因为dictionary没有if key exisits),两个queue来倒来倒去,结果TLE了。

所以!选择数据结构的时候应该有:Queue, Stack,LinkedList/DoubleLinkedList, HashMap.(以及他们之间的种种结合)。

这题应该用一个DoubleLinkedList来表达cache,另一个HashMap来查找<key, Node>

  • 可以把lru node放到头或者放到尾都可以,我的思维定式是把它想象成一个queue,新cache放在尾部。但是我觉得放head更好一点。所以新cache放HEAD
  • 一个head和一个tail不动,方便放入最新visited的node,也方便delete lru node。
  • 两个key method:(以把lru node处于尾部为例)
    • move_to_head:是把访问存在于cache中的node放到头部。当set一个新的cache的时候,就直接在主函数里面写就可以了,没有必要再弄一个小函数。
    • remove_lru_node: 移除处于尾部的lru node。
  • 注意保持 node和hashmap的一致性。
  • get和set都是对cache的一次访问,都要调整cache的顺序。

 

2. TWO SUM:

  • 最先想到的是利用那个backtracking的模板,但是忘记了写不出来;
  • 之后的想法二:两个for-loop进行二重循环pass。
  • 最优解在这里,一个for-loop,一个hashmap<target – nums[i], i>:https://oneokay.wordpress.com/2016/07/10/56-two-sum/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: