[LeetCode] 359. Logger Rate Limiter 记录速率限制器

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 359. Logger Rate Limiter 记录速率限制器,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;html

设计一个记录系统每次接受信息并保存时间戳,而后让咱们打印出该消息,前提是最近10秒内没有打印出这个消息。Uber家java

解法:哈希表,创建message和timestamp之间映射,若是接收到的消息不在哈希表里,就添加到哈希表里,并返回true。若是已经存在,若是当前时间戳是否比哈希表中保存的时间戳大10秒,则更新哈希表,并返回true,不然返回false。python

Java:app

public class Logger{
    
    HashMap<String, Integer> record;
    
    /** Initialize your data structure here. */
    public Logger() {
        record= new HashMap<String, Integer>();
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
/*        if(record.containsKey(message)){
            if( timestamp-record.get(message) >=10){
                record.put(message, timestamp);
                return true;
            }
            else{
                return false;
            }
            
        }
        else{
            record.put(message, timestamp);
            return true;
        }*/  // 以上是很是连贯的逻辑,一步步作判断,下面是 精简后的判断条件,因此速度上快不少,可是若是没写出上面的代码,没看到重复出现的那两行,可能也不会想到下面的写法
        
        if(record.containsKey(message) && timestamp-record.get(message)<10 ){
            return false;
        }
        else{
            record.put(message, timestamp);
            return true;            
        }
        
    }
}
 
/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */  

Python:post

# Time:  O(1), amortized
# Space: O(k), k is the max number of printed messages in last 10 seconds
import collections

class Logger(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.__dq = collections.deque()
        self.__printed = set()

    def shouldPrintMessage(self, timestamp, message):
        """
        Returns true if the message should be printed in the given timestamp, otherwise returns false. The timestamp is in seconds granularity.
        :type timestamp: int
        :type message: str
        :rtype: bool
        """
        while self.__dq and self.__dq[0][0] <= timestamp - 10:
            self.__printed.remove(self.__dq.popleft()[1])
        if message in self.__printed:
            return False
        self.__dq.append((timestamp, message))
        self.__printed.add(message)
        return True


# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)  

C++:this

class Logger {
public:
    Logger() {}
    
    bool shouldPrintMessage(int timestamp, string message) {
        if (!m.count(message)) {
            m[message] = timestamp;
            return true;
        } 
        if (timestamp - m[message] >= 10) {
            m[message] = timestamp;
            return true;
        }
        return false;
    }

private:
    unordered_map<string, int> m;
};

C++:url

class Logger {
public:
    Logger() {}
    
    bool shouldPrintMessage(int timestamp, string message) {
        if (timestamp < m[message]) return false;
        m[message] = timestamp + 10;
        return true;
    }

private:
    unordered_map<string, int> m;
};

  

  

All LeetCode Questions List 题目汇总