美文网首页
2018-10-25 First Unique Number I

2018-10-25 First Unique Number I

作者: WenshengL | 来源:发表于2018-10-26 01:57 被阅读0次
  1. First Unique Number In Stream

LC:387

Given a continuous stream of numbers, write a function that returns the first unique number whenever terminating number is reached(include terminating number). If there no unique number before terminating number or you can't find this terminating number, return -1.

Example
Given a stream [1, 2, 2, 1, 3, 4, 4, 5, 6] and a number 5
return 3

Given a stream [1, 2, 2, 1, 3, 4, 4, 5, 6] and a number 7
return -1

class LinkedNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def __init__(self,):
        self.hash = {}
        self.head = LinkedNode()
        self.tail = self.head
        
    """
    @param nums: a continuous stream of numbers
    @param number: a number
    @return: returns the first unique number
    """
    def firstUniqueNumber(self, nums, number):
        if not nums:
            return -1
        
        for n in nums:
            if n in self.hash:
                if self.hash[n]:
                    self.remove(self.hash[n])
            else:
                self.push_back(LinkedNode(n))
            if n == number:
                return self.head.next.val
        return -1
    
    def push_back(self, node):
        self.hash[node.val] = self.tail
        self.tail.next = node
        self.tail = node
    
    # different from LRU, need to totally reomove
    # use self.hash[node] to denote that node is deleted
    def remove(self, prev):
        node = prev.next
        prev.next = node.next
        
        if node == self.tail:
            self.tail = prev
        else:
            self.hash[node.next.val] = prev
        
        self.hash[node.val] = None

Note:

  1. Almost the same to 2018-10-23/24 LRU Cache [H]

    1. need LinkedNode()
    2. same push_back()
    3. same __init__(), need hash(value, prev node)
  2. But different in:

    1. remove() instead of move_to_back()
    2. set hash[val] to be None if deleted, because hash still works as "visited"
  3. A really good way of practicing linked list

    1. Learn how to add, remove etc.
    2. Consider edge cases.
      1. tail of linked list inremove()
      2. what if a node is deleted

相关文章

网友评论

      本文标题:2018-10-25 First Unique Number I

      本文链接:https://www.haomeiwen.com/subject/wbgftqtx.html