706. Design HashMap

[tech-cow]

第一刷

错误代码

3个Bug: List死循环没有Node.next, 然后没有考虑链表edge case，提前删除链表。

class ListNode(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
    

class MyHashMap(object):

    def __init__(self):
        self.size = 1000
        self.bucket = [None] * self.size
        
        
    def put(self, key, val):
        index = key % self.size
        
        if self.bucket[index] == None:
            self.bucket[index] = ListNode(key , val)
        else:
            cur = self.bucket[index]

            
            while cur:
                if cur.key == key:
                    cur.val = val
                    return
                if not cur.next: break
                # BUG1 : 没有 cur = cur.next ,  无限循环1
            cur.next = ListNode(key, val)
        

    def get(self, key):
        index = key % self.size
        
        cur = self.bucket[index]
        while cur:
            if cur.key == key:
                return cur.val
            cur = cur.next
        return -1
        
        
    def remove(self, key):
        index = key % self.size
        prev = cur = self.bucket[index]
        
        if not cur: return
        if cur.key == key:
            self.bucket[index] = None
             # BUG2 : 不能直接删除设为None，因为之后链表可能还有Node
            return
        
        cur = cur.next
        while cur:
            if cur.key == key:
                prev.next = cur.next
                # WARN1: 可以直接break here
            else:
                cur = cur.next
                prev = prev.next

更改代码

class ListNode(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
    

class MyHashMap(object):

    def __init__(self):
        self.size = 1000
        self.bucket = [None] * self.size
        
        
    def put(self, key, val):
        index = key % self.size
        
        if self.bucket[index] == None:
            self.bucket[index] = ListNode(key , val)
        else:
            cur = self.bucket[index]

            
            while cur:
                if cur.key == key:
                    cur.val = val
                    return
                if not cur.next: break
                cur = cur.next
            cur.next = ListNode(key, val)
        

    def get(self, key):
        index = key % self.size
        
        cur = self.bucket[index]
        while cur:
            if cur.key == key:
                return cur.val
            cur = cur.next
        return -1
        
        
    def remove(self, key):
        index = key % self.size
        prev = cur = self.bucket[index]
        
        if not cur: return
        if cur.key == key:
            self.bucket[index] = cur.next
            return
        
        cur = cur.next
        while cur:
            if cur.key == key:
                prev.next = cur.next
                break
            else:
                cur = cur.next
                prev = prev.next