05 August 2008
存储日志，包括timestamp，然后可以按照时间粒度（year，Hour等）查询所有日志
题目给 Put 输入为一个键值对，key 为 id，value 为一个字符串，表示时间戳；
题目从 Retrieve 获取一个 id，参数 granularity 表示起点从该级往下视为 0，终点从该级往下视为“满”，例如：“2016:01:01:01:01:01” 和 “2017:01:01:23:00:00”，如果 granularity 为 “YEAR” ，则把这两个字符串看成 “2016:00:00:00:00:00” 和 “2017:12:31:23:59:59”。
题目的难点在于如何根据给定的起点、终点和 granularity 获取 id。
考虑到字符串比较大小不方便，把时间戳转成一个数字，题目注释说给定的年份是 2000 年到 2017 年，我们可以把时间戳改成从 1999 年开始的秒数。
例如时间戳为：“2016:01:01:00:00:00”，先转成 int 数组：st = [2016, 1, 1, 0, 0, 0]，接着计算出它从 [1999,0,0,0,0,0] 开始的秒数，即：
(st[0] - 1999L) * (31 * 12) * 24 * 60 * 60 + // 年 st[1] * 31 * 24 * 60 * 60 + // 月 st[2] * 24 * 60 * 60 + // 日 st[3] * 60 * 60 + // 时 st[4] * 60 + // 分 st[5]; // 秒
把时间戳对应的秒数和 id 存储到一个 list 中。
使用 Retrieve 函数时，计算出 start 对应的秒数和 end+1 对应的秒数，然后从 list 中找到这两个秒数之间的时间戳的 id 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class LogSystem {
// [0] 为时间戳，[1] 为 id
ArrayList<long[]> list;
public LogSystem() {
list = new ArrayList<long[]>();
}
/**
* "2016:01:01:00:00:00" 转为 [2016, 1, 1, 0, 0, 0]，再转为秒数，存入 list
*
* @param id
* @param timestamp
*/
public void put(int id, String timestamp) {
String[] strs = timestamp.split(":");
int[] st = new int[strs.length];
for (int i = 0; i < strs.length; i++) {
st[i] = Integer.parseInt(strs[i]);
}
list.add(new long[]{convert(st), id});
}
/**
* 自定义方法
* 将时间戳转换为从 1999 年开始到该时间戳的秒数
*
* @param st
* @return
*/
public long convert(int[] st) {
st[1] = st[1] - (st[1] == 0 ? 0 : 1);
st[2] = st[2] - (st[2] == 0 ? 0 : 1);
return (st[0] - 1999L) * (31 * 12) * 24 * 60 * 60 + // 由于本题中年份的限制在 [2000, 2017] 之间，因此我们可以将时间戳转换为从 1999 年开始到该时间戳的秒数。
(long) st[1] * 31 * 24 * 60 * 60 + // 将每个月都看成 31 天，这样偏序关系仍然能够保持，只是有些整数没有对应的时间戳而已
(long) st[2] * 24 * 60 * 60 + // 日
(long) st[3] * 60 * 60 + // 时
st[4] * 60L + // 分
st[5]; // 秒
}
/**
* 返回在给定时间区间内的所有日志的 id
*
* @param s start 、 end 和 timestamp 的格式相同
* @param e
* @param gra granularity 表示考虑的时间级
* @return
*/
public List<Integer> retrieve(String s, String e, String gra) {
ArrayList result = new ArrayList();
long start = granularity(s, gra, false);
long end = granularity(e, gra, true);
for (long[] longs : list) {
// 注意 end 没有等于
if (longs[0] >= start && longs[0] < end)
result.add((int) longs[1]);
}
return result;
}
public long granularity(String s, String gra, boolean end) {
HashMap<String, Integer> h = new HashMap<>();
h.put("Year", 0);
h.put("Month", 1);
h.put("Day", 2);
h.put("Hour", 3);
h.put("Minute", 4);
h.put("Second", 5);
String[] res = new String[]{"1999", "00", "00", "00", "00", "00"};
String[] st = s.split(":");
// for (int i = 0; i <= h.get(gra); i++) {
// res[i] = st[i];
// }
if (h.get(gra) + 1 >= 0) {
System.arraycopy(st, 0, res, 0, h.get(gra) + 1);
}
int[] t = new int[res.length];
for (int i = 0; i < res.length; i++) {
t[i] = Integer.parseInt(res[i]);
}
if (end) {
t[h.get(gra)]++;
}
return convert(t);
}
}
/**
* Your LogSystem object will be instantiated and called as such:
* LogSystem obj = new LogSystem();
* obj.put(id,timestamp);
* List<Integer> param_2 = obj.retrieve(s,e,gra);
*/
另外的网上解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class LogSystem {
//leetcode.com/problems/design-log-storage-system/discuss/105008/Concise-Java-Solution/107763
private List<String[]> db;
Map<String, Integer> unitIndexMap;
public LogSystem() {
db = new ArrayList<>();
unitIndexMap = new HashMap<>();
//init
unitIndexMap.put("Year", 4);
unitIndexMap.put("Month", 7);
unitIndexMap.put("Day", 10);
unitIndexMap.put("Hour", 13);
unitIndexMap.put("Minute", 16);
unitIndexMap.put("Second", 19);
}
public void put(int id, String timestamp) {
db.add(new String[]{String.valueOf(id), timestamp});
}
public List<Integer> retrieve(String s, String e, String gra) {
int index = unitIndexMap.get(gra);
List<Integer> res = new ArrayList<>();
for (String[] st : db) {
if (st[1].substring(0, index).compareTo(s.substring(0, index)) >= 0 && st[1].substring(0, index).compareTo(e.substring(0, index)) <= 0) {
res.add(Integer.valueOf(st[0]));
}
}
return res;
}
}
/**
* Your LogSystem object will be instantiated and called as such:
* LogSystem obj = new LogSystem();
* obj.put(id,timestamp);
* List<Integer> param_2 = obj.retrieve(s,e,gra);
*/