LeetCode Design Log Storage System
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.
Design a log storage system to implement the following functions:
void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system.
int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
Example 1:
put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.
Note:
- There will be at most 300 operations of Put or Retrieve.
- Year ranges from [2000,2017]. Hour ranges from [00,23].
- Output for Retrieve has no order required.
设计一个日志系统，该系统有两个操作，put(id,timestamp)把timestamp时刻的日志id放到日志系统中，retrieve(start,end,gra)从系统中取出timestamp范围在[start,end]之间的日志id，时间的粒度是gra。 我设计的系统是这样的，为了方便retrieve，系统中的日志都按timestamp排序了。有趣的是，在zero-padded（每部分不足补前导0）的情况下，timestamp的字符串排序就是timestamp表示的时间的排序。 定义一个Node结构体，保持一个日志，信息包括日志id和timestamp。用一个链表存储所有Node，并且当新Node插入时，采用插入排序的方法使得链表始终有序。 retrieve的时候，根据粒度，重新设置start和end，比如样例中粒度为Year时，把start改为Year固定，其他时间最小
"2016:00:00:00:00:00"
把end改为Year固定，其他时间最大
"2017:12:31:23:59:59"
这样我只需要遍历链表，把所有timestamp字符串在这个范围内的日志id取出来就好了。其他粒度也是类似的。
完整代码如下：
[cpp]
class LogSystem {
private:
struct Node {
int id;
string timestamp;
Node(int i, string t) :id(i), timestamp(t) {};
};
list<Node> log;
string start, end;
public:
LogSystem() {
start = "2000:00:00:00:00:00";
end = "2017:12:31:23:59:59";
}
void put(int id, string timestamp) {
Node node(id, timestamp);
if (log.empty())log.push_back(node);
else {
auto it = log.begin();
while (it != log.end() && (*it).timestamp <= timestamp)++it;
log.insert(it, node);
}
}
vector<int> retrieve(string s, string e, string gra) {
if (gra == "Year") {
s = s.substr(0, 4) + start.substr(4);
e = e.substr(0, 4) + end.substr(4);
}
else if (gra == "Month") {
s = s.substr(0, 7) + start.substr(7);
e = e.substr(0, 7) + end.substr(7);
}
else if (gra == "Day") {
s = s.substr(0, 10) + start.substr(10);
e = e.substr(0, 10) + end.substr(10);
}
else if (gra == "Hour") {
s = s.substr(0, 13) + start.substr(13);
e = e.substr(0, 13) + end.substr(13);
}
else if (gra == "Minute") {
s = s.substr(0, 16) + start.substr(16);
e = e.substr(0, 16) + end.substr(16);
}
vector<int> ans;
auto it = log.begin();
while (it != log.end() && (*it).timestamp < s)++it;
while (it != log.end() && (*it).timestamp <= e) {
ans.push_back((*it).id);
++it;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时19MS。]]>