【leetcode】981. Time Based Key-Value Store
2024-10-07 15:35:13
题目如下:
Create a timebased key-value store class
TimeMap
, that supports two operations.1.
set(string key, string value, int timestamp)
- Stores the
key
andvalue
, along with the giventimestamp
.2.
get(string key, int timestamp)
- Returns a value such that
set(key, value, timestamp_prev)
was called previously, withtimestamp_prev <= timestamp
.- If there are multiple such values, it returns the one with the largest
timestamp_prev
.- If there are no values, it returns the empty string (
""
).Example 1:
Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],
["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.get("foo", 1); // output "bar"
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2,
//then the only value is at timestamp 1 ie "bar"
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // output "bar2"
kv.get("foo", 5); //output "bar2"Example 2:
Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],
["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]Note:
- All key/value strings are lowercase.
- All key/value strings have length in the range
[1, 100]
- The
timestamps
for allTimeMap.set
operations are strictly increasing.1 <= timestamp <= 10^7
TimeMap.set
andTimeMap.get
functions will be called a total of120000
times (combined) per test case.
解题思路:我用了两个字典,一个是dic_timestamp,以timestamp为key,value作为val;第二个是dic[val] = [timestamp],对于val相同的timestamp以升序排列的方式保存在val对应的list中。由于set操作的timestamp是递增的,所以在set的时候只需要把timestamp插入到div[val]的最后即可;对于get操作,采用二分查找的方法找出最大的小于timestamp的历史timestamp。但是二分查找的方法会timeout,后来我发现get操作的timestamp也是递增的,但是题目没有说明,所以改进代码在get操作之后删除掉小于timestamp的所有历史数据。
代码如下:
class TimeMap(object): def __init__(self):
"""
Initialize your data structure here.
"""
self.dic_timestamp = {}
self.dic = {} def set(self, key, value, timestamp):
"""
:type key: str
:type value: str
:type timestamp: int
:rtype: None
"""
self.dic[key] = self.dic.setdefault(key,[]) + [timestamp]
self.dic_timestamp[timestamp] = value def get(self, key, timestamp):
"""
:type key: str
:type timestamp: int
:rtype: str
"""
import bisect
if key not in self.dic or len(self.dic[key]) == 0 or timestamp < self.dic[key][0]:
return ''
elif timestamp >= self.dic[key][-1]:
v = self.dic[key][-1]
self.dic[key] = [self.dic[key][-1]]
return self.dic_timestamp[v]
v = bisect.bisect_left(self.dic[key], timestamp)
inx = bisect.bisect_left(self.dic[key], timestamp)
if inx == len(self.dic[key]) or timestamp != self.dic[key][inx]:
inx -= 1
v = self.dic[key][inx]
self.dic[key] = self.dic[key][inx:]
return self.dic_timestamp[v]
最新文章
- 编程结构:Promise和Future
- [SAP ABAP开发技术总结]选择屏幕——各种屏幕元素演示
- 整理iOS9适配
- Leetcode OJ : Repeated DNA Sequences hash python solution
- SQLite入门与分析(八)---存储模型(1)
- 新Android学习计划
- Matlab中边缘提取方法简析
- 沙朗javascript总结一下(一)---基础知识
- linux 编译java并打包
- noip模拟 市长选举
- C++调用C方法
- 使用Navicat快速生成MySQL数据字典
- hadoop ha zkfc 异常自动切换机制和hdfs 没有空间问题解决
- iOS开发之UIGestureRecognizer
- DBMS客户端是否安装:Make sure DBMS client is installed and this required library is available for dynamic loading
- 【LeetCode】13. 罗马数字转整数
- 大叔力量VIP介绍
- 2017CCPC秦皇岛 E题String of CCPC&;&;ZOJ3985【模拟】
- java中两种发起POST请求,并接收返回的响应内容的方式&#160;&#160;(转)
- 浅析中国剩余定理(从CRT到EXCRT))
热门文章
- 学习日记3、投机取巧使两个表的数据同时在一个treeGrid中显示
- LintCode之左填充
- Qt5.1 静态编译
- oracle、sql developer 删除某用户下所有的表
- 匿名函数 sorted() filter() map() 递归函数
- unittest测试框架生成可视化测试报告-BeautifulReport
- tomcat启动控制台报Exception in thread &#39;&#39;main";.......“Could not find the main class:.....Bootstrap”问题
- Python专题三字符串的基础知识
- Java8 Nashorn JavaScript引擎
- [Linux] 014 帮助命令