算法leetcode

【设计难题】力扣635-设计日志存储系统

字数统计: 1.3k字   |   阅读时长: 6分
, ,

摘要: 基于 Trie 的日期索引设计

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 题目

635. 设计日志存储系统

你将获得多条日志，每条日志都有唯一的 id 和 timestamp ，timestamp 是形如 Year:Month:Day:Hour:Minute:Second 的字符串，2017:01:01:23:59:59 ，所有值域都是零填充的十进制数。

实现 LogSystem 类：

  • LogSystem() 初始化 LogSystem 对象
  • void put(int id, string timestamp) 给定日志的 id 和 timestamp ，将这个日志存入你的存储系统中。
  • int[] retrieve(string start, string end, string granularity) 返回在给定时间区间 [start, end] （包含两端）内的所有日志的 id 。start 、end 和 timestamp 的格式相同，granularity 表示考虑的时间粒度（例如，精确到 Day、Minute 等）。例如 start = “2017:01:01:23:59:59”、end = “2017:01:02:23:59:59” 且 granularity = “Day” 意味着需要查找从 Jan. 1st 2017 到 Jan. 2nd 2017 范围内的日志，可以忽略日志的 Hour、Minute 和 Second 。

提示

1
2
3
4
5
6
7
8
1 <= id <= 500
2000 <= Year <= 2017
1 <= Month <= 12
1 <= Day <= 31
0 <= Hour <= 23
0 <= Minute, Second <= 59
granularity 是这些值 ["Year", "Month", "Day", "Hour", "Minute", "Second"] 之一
最多调用 500 次 put 和 retrieve

示例：

输入：
[“LogSystem”, “put”, “put”, “put”, “retrieve”, “retrieve”]
[[], [1, “2017:01:01:23:59:59”], [2, “2017:01:01:22:59:59”], [3, “2016:01:01:00:00:00”], [“2016:01:01:01:01:01”, “2017:01:01:23:00:00”, “Year”], [“2016:01:01:01:01:01”, “2017:01:01:23:00:00”, “Hour”]]
输出：
[null, null, null, null, [3, 2, 1], [2, 1]]

解释：
LogSystem logSystem = new LogSystem();
logSystem.put(1, “2017:01:01:23:59:59”);
logSystem.put(2, “2017:01:01:22:59:59”);
logSystem.put(3, “2016:01:01:00:00:00”);

// 返回 [3,2,1]，返回从 2016 年到 2017 年所有的日志。
logSystem.retrieve(“2016:01:01:01:01:01”, “2017:01:01:23:00:00”, “Year”);

// 返回 [2,1]，返回从 Jan. 1, 2016 01:XX:XX 到 Jan. 1, 2017 23:XX:XX 之间的所有日志
// 不返回日志 3 因为记录时间 Jan. 1, 2016 00:00:00 超过范围的起始时间
logSystem.retrieve(“2016:01:01:01:01:01”, “2017:01:01:23:00:00”, “Hour”);

$2 题解

算法: Trie

比较直观的做法是将时间转化为时间戳，然后在平衡树上维护时间。查询时将 start 和 end 转换为时间戳再在平衡树维护树形索引。这里尝试一种 Trie 型的索引。

由于查询粒度为年月日时分秒六种粒度，因此可以考虑用类似与 Trie 的方式设计节点，第 1 层为根，第 2 到 7 层为年月日时分秒六种粒度的数据，并且每个节点均把所有子节点的数据在本节点汇总了一份副本，方便查询时直接取用。

例如如果当前层级的节点为月粒度的节点，那么它的子节点是该月份下各个日的节点，节点持有的数据就是所有子节点持有的数据的并集。即该月份的数据就是该月份下所有日的数据的并集。

1
2
3
4
5
6
7
struct Node
{
    string type;
    vector<int> logs;
    map<string, Node*> children;
    Node(string type):type(type){}
};

在查询的时候根据粒度决定搜索时的深度限制，如果查询区间很大覆盖完整的粒度更高的节点代表的时间段，则可以直接返回该节点持有的数据，不用继续往下搜索。

代码 (C++)

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
struct Node
{
    string type;
    vector<int> logs;
    map<string, Node*> children;
    Node(string type):type(type){}
};

class LogSystem {
public:
    LogSystem() {
        root = new Node("Root");
    }

    void put(int id, string timestamp) {
        int n = timestamp.size();
        int level = 0;
        Node *iter = root;
        int i = 0;
        while(i < n)
        {
            int j = timestamp.find_first_of(':', i);
            if(j == (int)string::npos)
                j = n;
            string key = timestamp.substr(i, j - i);
            ++level;
            if(!(iter -> children)[key])
                (iter -> children)[key] = new Node(LEVEL2TYPE[level]);
            iter = (iter -> children)[key];
            (iter -> logs).push_back(id);
            i = j + 1;
        }
    }

    vector<int> retrieve(string s, string e, string gra) {
        int level = TYPE2LEVEL.find(gra) -> second;
        vector<string> start_info = _parse(s);
        vector<string> end_info = _parse(e);
        vector<int> result;
        dfs(root, start_info, end_info, 0, level, true, true, result);
        return result;
    }

private:
    Node *root;

    void dfs(Node* node, const vector<string>& start_info, const vector<string>& end_info,
            int level, const int max_level, bool edge_left, bool edge_right, vector<int>& result)
    {
        // edge_prev true  前面顶到了右边界
        //           false 前面顶到了左边界
        if(level == max_level || (!edge_left && !edge_right))
        {
            result.insert(result.end(), (node -> logs).begin(), (node -> logs).end());
            return;
        }
        string start_key = start_info[level + 1];
        string end_key = end_info[level + 1];
        map<string, Node*>::iterator it;
        if(edge_left)
            it = (node -> children).lower_bound(start_key);
        else
            it = (node -> children).begin();
        map<string, Node*>::iterator end;
        if(edge_right)
            end = (node -> children).upper_bound(end_key);
        else
            end = (node -> children).end();
        while(it != end)
        {
            bool left_flag = edge_left && it -> first == start_key;
            bool right_flag = edge_right && it -> first == end_key;
            dfs(it -> second, start_info, end_info, level + 1, max_level,
                    left_flag, right_flag, result);
            ++it;
        }
    }

    vector<string> _parse(const string& s)
    {
        int n = s.size();
        int level = 0;
        int i = 0;
        vector<string> result(7);
        while(i < n)
        {
            int j = s.find_first_of(':', i);
            if(j == (int)string::npos)
                j = n;
            string key = s.substr(i, j - i);
            result[++level] = key;
            i = j + 1;
        }
        return result;
    }

    const vector<string> LEVEL2TYPE = {
        "Root",
        "Year",
        "Month",
        "Day",
        "Hour",
        "Minute",
        "Second"
    };

    const unordered_map<string, int> TYPE2LEVEL = {
        {"Root", 0},
        {"Year", 1},
        {"Month", 2},
        {"Day", 3},
        {"Hour", 4},
        {"Minute", 5},
        {"Second", 6}
    };
};
Share