lintcode 961 · 设计日志存储系统预【系统设计题 中等】

题目链接，描述

https://www.lintcode.com/problem/961

您将获得多个日志，每个日志都包含唯一的 ID 和时间戳。 时间戳是一个具有以下格式的字符串：Year:Month:Day:Hour:Minute:Second，例如2017:01:01:23:59:59。 所有域都是零填充的十进制数字。设计一个日志存储系统，实现以下功能：void put(int id, string timestamp)给定日志的唯一 ID 和时间戳，将日志存储在存储系统中。int[] retrieve(String start, String end, String granularity)返回时间戳在 start 到 end 范围内的日志 ID。 start 和 end 都具有与时间戳相同的格式。然而，粒度意味着考虑的时间水平。 例如 start="2017:01:01:23:59:59"，end="2017:01:02:23:59:59"，granularity="Day"，这意味着我们需要查找日志范围为 2017 年 1 月 1 日至 2017 年 1 月 2 日。最多有 300 次放回操作。年份范围为 [2000，2017]，小时范围为 [00，23]。输出不需要你进行排序。样例
样例 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")
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour")
输出：[1,2,3]
[1,2]
样例 2输入：put(1,"2017:01:04:19:26:51")
put(2,"2017:01:05:02:15:35")
put(3,"2017:01:07:23:02:54")
retrieve("2017:01:09:08:09:49","2017:01:09:13:55:15","Hour")
输出：[]put(1,"2017:01:04:05:50:33")
put(2,"2017:01:08:22:48:21")
put(3,"2017:01:05:04:44:19")
put(4,"2017:01:05:18:24:57")
put(5,"2017:01:04:03:31:29")
put(6,"2017:01:03:19:26:15")
put(7,"2017:01:02:13:23:19")
put(8,"2017:01:01:02:39:25")
put(9,"2017:01:08:00:02:31")
put(10,"2017:01:04:14:40:57")
retrieve("2017:01:05:15:29:07","2017:01:05:03:03:51","Day")
retrieve("2017:01:07:06:18:53","2017:01:07:14:06:02","Day")
retrieve("2017:01:02:16:46:52","2017:01:07:23:53:28","Month")
retrieve("2017:01:04:21:59:44","2017:01:07:03:03:14","Minute")
输出数据
[3,4]
[]
[1,2,3,4,5,6,7,8,9,10]
[]
期望答案
[3,4]
[]
[1,2,3,4,5,6,7,8,9,10]
[3,4]

思路

本题考查的知识点为设计。

在本题中，我们需要设计日志存储系统，对于该系统的日志信息，我们可以直接使用一个动态数组来进行存储。数组中需要存储的是每个日志的 ID 以及时间戳。

而对于检索指定时间内的日志，则可以通过遍历当前数组来进行。由于该判断时间的范围还加了一个粒度，因此我们需要根据粒度对时间进行裁。其中时间的处理包括起始时间，结束时间以及日志时间。

然后我们再根据对根据粒度处理过后字符串进行时间比较，对此我们可以直接比较两个字符串的字典序即可，这是因为题目中给出的时间戳恰好按照年月日时分秒的格式，因此字典序也能够比较出时间的大小。

最后我们只需要将合法的日志 ID 加到返回的数组即可。

答案

public class LogSystem {List<Log> logs;Map<String,Integer> map;public LogSystem(){logs = new ArrayList<>();map = new HashMap<>();map.put("Year",4);  map.put("Month",7);map.put("Day",10);  map.put("Hour",13);map.put("Minute",16);  map.put("Second",19);}public void put(int id, String timestamp) {logs.add(new Log(id,timestamp));}public int[] retrieve(String start, String end, String granularity) {List<Integer> list= new ArrayList<>();int endIndex = map.get(granularity);start = start.substring(0,endIndex);end= end.substring(0,endIndex);for (Log log : logs) {String logtime = log.timestr.substring(0,endIndex);if(logtime.compareTo(start) >=0 && logtime.compareTo(end)<=0){list.add(log.id);}}int[] ans = new int[list.size()];for (int i = 0; i < list.size(); i++) {ans[i] = list.get(i);}return ans;}static class Log{int id;String timestr;public Log(int i,String s){id = i;timestr=s;}}
}