leetcode/146. LRU Cache.html at master · michael3lyb/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
<html>
<head>
  <title>146. LRU Cache</title>
  <basefont face="Tahoma" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/304720 (en-US, DDL); Windows/10.0.14393 (Win64);"/>
  <style>
    body, td {
      font-family: Tahoma;
      font-size: 12pt;
    }
  </style>
</head>
<body>
<a name="7258"/>
<h1>146. LRU Cache</h1>
<div>
<table bgcolor="#D4DDE5" border="0">
<tr><td><b>Created:</b></td><td><i>8/1/2016 8:26 AM</i></td></tr>
<tr><td><b>Updated:</b></td><td><i>8/17/2016 4:21 AM</i></td></tr>
<tr><td><b>Tags:</b></td><td><i>Design, Hard, leetcode tag</i></td></tr>
</table>
</div>
<br/>

<div>
<span><div><a href="https://leetcode.com/problems/lru-cache/">https://leetcode.com/problems/lru-cache/</a></div><div><br/></div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.148438);"><div>class KeyValue {public:<br/>
    int key, value;<br/>
    KeyValue *next;<br/>
    KeyValue(int key, int value) {<br/>
        next = NULL;<br/>
        this-&gt;key = key;<br/>
        this-&gt;value = value;<br/>
    }<br/>
    KeyValue() {<br/>
        this-&gt;next = NULL;<br/>
        this-&gt;key = 0;<br/>
        this-&gt;value = 0;</div><div>    }</div><div>};</div><div><br/>
class LRUCache{private:<br/>
    void moveToTail(KeyValue *prev) {<br/>
        if (prev-&gt;next == tail) {<br/>
            return;<br/>
        }<br/>
       <br/>
        KeyValue *node = prev-&gt;next;<br/>
        prev-&gt;next = node-&gt;next;<br/>
        if (node-&gt;next != NULL) {<br/>
            hash[node-&gt;next-&gt;key] = prev;<br/>
        }<br/>
        tail-&gt;next = node;<br/>
        node-&gt;next = NULL;<br/>
        hash[node-&gt;key] = tail;<br/>
        tail = node;<br/>
    }<br/>
   <br/>
public:<br/>
    unordered_map&lt;int, KeyValue *&gt; hash;<br/>
    KeyValue *head, *tail;<br/>
    int capacity, size;<br/>
   <br/>
    LRUCache(int capacity) {<br/>
        this-&gt;head = new KeyValue(0, 0);<br/>
        this-&gt;tail = head;<br/>
        this-&gt;capacity = capacity;<br/>
        this-&gt;size = 0;<br/>
        hash.clear();<br/>
    }<br/>
   <br/>
    int get(int key) {<br/>
        if (hash.find(key) == hash.end()) {<br/>
            return -1;<br/>
        }<br/>
       <br/>
        moveToTail(hash[key]);<br/>
        return hash[key]-&gt;next-&gt;value;<br/>
    }<br/>
   <br/>
    void set(int key, int value) {<br/>
        if (hash.find(key) != hash.end()) {<br/>
            hash[key]-&gt;next-&gt;value = value;<br/>
            moveToTail(hash[key]);<br/>
        } else {<br/>
            KeyValue *node = new KeyValue(key, value);<br/>
            tail-&gt;next = node;<br/>
            hash[key] = tail;<br/>
            tail = node;<br/>
            size++;<br/>
            if (size &gt; capacity) {<br/>
                hash.erase(head-&gt;next-&gt;key);<br/>
                head-&gt;next = head-&gt;next-&gt;next;<br/>
                if (head-&gt;next != NULL) {<br/>
                    hash[head-&gt;next-&gt;key] = head;<br/>
                }<br/>
                size--;<br/>
            }<br/>
        }</div><div>    }</div><div>};</div></div><div><br/></div></span>
</div></body></html>