文章目录博主目前也在学习,有错误欢迎指正
保持热爱 奔赴星海
- 一、题目
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
- 1、思路分析
- 2、代码详解
- 三、本题知识
设计一个基于时间的键值数据结构,该结构可以在不同时间戳存储对应同一个键的多个值,并针对特定时间戳检索键对应的值。
实现 TimeMap 类:
- TimeMap() 初始化数据结构对象
- void set(String key, String value, int timestamp) 存储键 key、值 value,以及给定的时间戳 timestamp。
- String get(String key, int timestamp)
(1)返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp 。
(2)如果有多个这样的值,则返回对应最大的 timestamp_prev 的那个值。
(3)如果没有值,则返回空字符串(“”)。
- Java版本框架代码如下:
class TimeMap {
public TimeMap() {
}
public void set(String key, String value, int timestamp) {
}
public String get(String key, int timestamp) {
}
}
3、原题链接
二、解题报告 1、思路分析981. 基于时间的键值存储
(1)这里因为要存储三个数据,所以我们Map里面嵌套一个Map,因为在get()方法中,我们要返回最大的timestamp_prev ,所以我们使用TreeMap来存储(timestamp,value)。
(2)对于set()方法,若map中存在key,则把(timestamp,value)放入key对应的TreeMap中即可,若map中不存在key,那么创建一个TreeMap,然后放入map中。
(3)对于get方法,如果map中不包含key直接返回""即可,如果map中包含key,返回最小的timestamp对应的value返回即可。
class TimeMap {
Map> map;
public TimeMap() {
map = new HashMap();
}
public void set(String key, String value, int timestamp) {
if(map.containsKey(key)) {
map.get(key).put(timestamp,value);
return;
}
TreeMap tm = new TreeMap();
tm.put(timestamp,value);
map.put(key,tm);
}
public String get(String key, int timestamp) {
if(!map.containsKey(key)) {
return "";
}
Map.Entry entry = map.get(key).floorEntry(timestamp);
if(entry == null) {
return "";
}
return entry.getValue();
}
}
三、本题知识
模拟



