hashtable&hash_set

 1 class Node:
 2     def __init__(self,key,val):
 3         self.pair=(key,val)
 4         self.next=None      # next仍指向一个Node
 5 
 6 class MyHashMap(object):
 7 
 8     def __init__(self):
 9         self.table_len=1000
10         self.hash=[None]*self.table_len
11 
12     def put(self, key, value):
13         """
14         value will always be non-negative.
15         :type key: int
16         :type value: int
17         :rtype: None
18         """
19         idx=key%self.table_len
20         if(self.hash[idx]==None):
21             self.hash[idx]=Node(key,value)
22         else:
23             cur=self.hash[idx]
24             while True:
25                 if(cur.pair[0]==key):
26                     cur.pair=(key,value)
27                     return
28                 if cur.next==None:
29                     break
30                 cur=cur.next
31             cur.next=Node(key,value)   
32         
33 
34     def get(self, key):
35         """
36         Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
37         :type key: int
38         :rtype: int
39         """
40         idx=key%self.table_len
41         cur=self.hash[idx]
42         while(cur):
43             if(cur.pair[0]==key):
44                 return cur.pair[1]
45             else:
46                 cur=cur.next
47         return -1
48 
49 
50     def remove(self, key):
51         """
52         Removes the mapping of the specified value key if this map contains a mapping for the key
53         :type key: int
54         :rtype: None
55         """
56         idx=key%self.table_len
57         cur=self.hash[idx]
58         pre=self.hash[idx]
59 
60         if(cur==None):
61             return
62         
63         if(cur.pair[0]==key):
64             self.hash[idx]=cur.next
65         else:
66             cur=cur.next
67             while(cur):
68                 if(cur.pair[0]==key):
69                     pre.next=cur.next
70                     break
71                 else:
72                     pre=pre.next
73                     cur=cur.next
74         
75 
76         
77 
78 
79 # Your MyHashMap object will be instantiated and called as such:
80 # obj = MyHashMap()
81 # obj.put(key,value)
82 # param_2 = obj.get(key)
83 # obj.remove(key)

 1 class Node:
 2     def __init__(self,key):
 3         self.key=key
 4         self.next=None
 5 
 6 class MyHashSet(object):
 7 
 8     def __init__(self):
 9         """
10         Initialize your data structure here.
11         """
12         self.table_len=1000
13         self.hash_set=[None]*self.table_len
14 
15     def add(self, key):
16         """
17         :type key: int
18         :rtype: None
19         """
20         idx=key%self.table_len
21         cur=self.hash_set[idx]
22         if(cur==None):
23             self.hash_set[idx]=Node(key)
24         else:
25             while True:
26                 if(cur.key==key):
27                     return
28                 else:
29                     if(cur.next==None):
30                         break
31                         
32                 cur=cur.next
33 
34             cur.next=Node(key)
35         
36 
37     def remove(self, key):
38         """
39         :type key: int
40         :rtype: None
41         """
42         idx=key%self.table_len
43         cur=self.hash_set[idx]
44         pre=self.hash_set[idx]
45         if(cur==None):
46             return
47 
48         if(cur.key==key):
49             self.hash_set[idx]=cur.next
50         else:
51             cur=cur.next
52             while(cur):
53                 if(cur.key==key):
54                     pre.next=cur.next
55                     break
56                 else:
57                     pre=pre.next
58                     cur=cur.next 
59         
60 
61     def contains(self, key):
62         """
63         Returns true if this set contains the specified element
64         :type key: int
65         :rtype: bool
66         """
67         idx=key%self.table_len
68         cur=self.hash_set[idx]
69         if(cur==None):
70             return False
71         else:
72             while(cur):
73                 if(cur.key==key):
74                     return True
75                 else:
76                     cur=cur.next
77         return False
78 
79 
80 # Your MyHashSet object will be instantiated and called as such:
81 # obj = MyHashSet()
82 # obj.add(key)
83 # obj.remove(key)
84 # param_3 = obj.contains(key)

 1 from collections import OrderedDict
 2 class LRUCache(object):
 3 
 4     def __init__(self, capacity):
 5         """
 6         :type capacity: int
 7         """
 8         #有序字典的尾部表示最近访问的
 9         self.hash=OrderedDict()
10         self.remains=capacity
11 
12 
13     def get(self, key):
14         """
15         :type key: int
16         :rtype: int
17         """
18         if key not in self.hash:
19             return -1
20         else:
21             val=self.hash.pop(key)
22             self.hash[key]=val
23             self.remains
24         return val
25 
26     def put(self, key, value):
27         """
28         :type key: int
29         :type value: int
30         :rtype: None
31         """
32         if(key in self.hash):
33             val=self.hash.pop(key)
34             self.hash[key]=value
35         else:
36             if(self.remains):
37                 self.remains-=1
38                 self.hash[key]=value
39             else:
40                 self.hash.popitem(last=False)
41         self.hash[key]=value
42 
43 
44 
45 
46 # Your LRUCache object will be instantiated and called as such:
47 # obj = LRUCache(capacity)
48 # param_1 = obj.get(key)
49 # obj.put(key,value)