1.hashtable
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)
2.hashset
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)
3. lru
访问key：
step1：查看key是否在self.lst中，如果在，将其移到self.lst尾部；否则返回-1
插入(key,val)：
step1：查看key是否在self.lst中，如果在，那么将旧key删除，在self.lst尾部插入(key，val)键值对；否则，转step2
step2：如果不在，那么查看是否有空闲页面，如果有，那么在self.lst尾部插入(key，val)键值对；否则，移除队头页面，并在self.lst尾部插入(key，val)键值对
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)
3.use a array implement three
class TripleInOne(object): def __init__(self, stackSize): """ :type stackSize: int """ self.size=stackSize self.lst=[None]*3*stackSize self.top=[-1,-1,-1] def push(self, stackNum, value): """ :type stackNum: int :type value: int :rtype: None """ if(0<=stackNum<3): if self.top[stackNum]+1>=self.size: return else: self.top[stackNum]+=1 self.lst[stackNum*self.size+self.top[stackNum]]=value def pop(self, stackNum): """ :type stackNum: int :rtype: int """ if(0<=stackNum<3): if(self.top[stackNum]!=-1): res=self.lst[stackNum*self.size+self.top[stackNum]] self.top[stackNum]-=1 return res return -1 def peek(self, stackNum): """ :type stackNum: int :rtype: int """ if(0<=stackNum<3): if(self.top[stackNum]!=-1): res=self.lst[stackNum*self.size+self.top[stackNum]] return res return -1 def isEmpty(self, stackNum): """ :type stackNum: int :rtype: bool """ if(0<=stackNum<3): return self.top[stackNum]==-1 # Your TripleInOne object will be instantiated and called as such: # obj = TripleInOne(stackSize) # obj.push(stackNum,value) # param_2 = obj.pop(stackNum) # param_3 = obj.peek(stackNum) # param_4 = obj.isEmpty(stackNum)