使用数据结构

返回首页

返回算法分类分析

第一题 LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解法

利用OrderedDict就很好解这道题，注意下面解答中OrderedDict的使用方法。 popitem有两种模式1)last=False模式，FIFO 2)last=True模式，LIFO

class LRUCache(object):



def __init__(self, capacity):

    """

    :type capacity: int

    """

    self.cache = collections.OrderedDict()

    self.capacity = capacity





def get(self, key):

    """

    :rtype: int

    """

    if key not in self.cache:

        return -1

    value = self.cache.pop(key)

    self.cache[key] = value

    return value



def set(self, key, value):

    """

    :type key: int

    :type value: int

    :rtype: nothing

    """

    if key in self.cache:

        self.cache.pop(key)

    elif len(self.cache) == self.capacity:

        self.cache.popitem(last=False)

    self.cache[key] = value

第二题 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

解法

这里巧妙地用set的特性来弥补了题中不看顺序的特点，而且利用了set查询方便的特性。

class Solution(object):

def longestConsecutive(self, nums):

    """

    :type nums: List[int]

    :rtype: int

    """

    nums = set(nums)

    maxLen = 0

    for n in nums:

        if n - 1 not in nums:

            m = n

            while(m + 1 in nums):

                m = m + 1

            maxLen = max(maxLen, m - n + 1)

    return maxLen