当前位置: 首页 > news >正文

【每日一题】981. 基于时间的键值存储

981. 基于时间的键值存储 - 力扣(LeetCode)

设计一个基于时间的键值数据结构,该结构可以在不同时间戳存储对应同一个键的多个值,并针对特定时间戳检索键对应的值。

实现 TimeMap 类:

  • TimeMap() 初始化数据结构对象
  • void set(String key, String value, int timestamp) 存储键 key、值 value,以及给定的时间戳 timestamp
  • String get(String key, int timestamp)
    • 返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp 。
    • 如果有多个这样的值,则返回对应最大的  timestamp_prev 的那个值。
    • 如果没有值,则返回空字符串("")。
 

示例:

输入:
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出:
[null, null, "bar", "bar", null, "bar2", "bar2"]解释:
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ,时间戳 timestamp = 1   
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值,所以唯一的值位于时间戳 1 处(即 "bar") 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ,时间戳 timestamp = 4  
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

提示:

  • 1 <= key.length, value.length <= 100
  • key 和 value 由小写英文字母和数字组成
  • 1 <= timestamp <= 107
  • set 操作中的时间戳 timestamp 都是严格递增的
  • 最多调用 set 和 get 操作 2 * 105 次
class TimeMap {//假设key一样//HashMap<Integer , String> map = new HashMap<Integer , String>();HashMap<String,HashMap<Integer , String>> map = new HashMap<String,HashMap<Integer , String>>();// ArrayList<Integer> arr = new ArrayList<Integer>();HashMap<String,ArrayList<Integer>> arr = new HashMap<String,ArrayList<Integer>>();public TimeMap() {arr.clear();map.clear();}public void set(String key, String value, int timestamp) {//arr.add(timestamp);//map.put(timestamp,value);if(!map.containsKey(key)) {HashMap<Integer , String> tmp = new HashMap<Integer , String>();tmp.put(timestamp,value);map.put(key,tmp);} else {map.get(key).put(timestamp,value);}if(!arr.containsKey(key)) {ArrayList<Integer> tmp = new ArrayList<Integer>();tmp.add(timestamp);arr.put(key,tmp);} else {arr.get(key).add(timestamp);}}public String get(String key, int timestamp) {if(!map.containsKey(key))  return "";ArrayList<Integer> arr1 = arr.get(key);int right = arr1.size()-1;int left = 0;int mid = 0;while(left <= right) {mid = (left+right)/2;if(arr1.get(mid) < timestamp) {left = mid+1;} else if(arr1.get(mid) > timestamp) {right = mid-1;} else {return map.get(key).get(arr1.get(mid));}}if(left == 0) return "";return map.get(key).get(arr1.get(left-1));// int right = arr.size()-1;// int left = 0;// int mid = 0;// while(left <= right) {//     mid = (left+right)/2;//     if(arr.get(mid) < timestamp) {//         left = mid+1;//     } else if(arr.get(mid) > timestamp) {//         right = mid-1;//     } else {//         System.out.println(mid);//         System.out.println("------------");//         return map.get(arr.get(mid));//     }// }// if(left == 0) return "";// return map.get(arr.get(left-1));}
}/*** Your TimeMap object will be instantiated and called as such:* TimeMap obj = new TimeMap();* obj.set(key,value,timestamp);* String param_2 = obj.get(key,timestamp);*/

        每日一题,今天是中等题。这道题有些难度,但主要也是在理解题目上。

        首先读题,了解到,实际上是一个键值对。在java中,键值对一般使用map来存储。但是,除了key和value,还有一个timestamp。所以实际上是需要一个中介的。题目的set函数实际上就是存储键值对的过程。get函数才是获得答案的过程。由于key会不一样,如果一开始就上手可能会很复杂,我们可以从简单的写起,一步一步往上。

        先假设只有一个key的情况。那么key是不用存储的。get要找到给定timestamp前的最大数,那实际上就是要找<=timestamp的最大数。最后肯定是要根据找到的这个timestamp来返回值的,所以,一开始的键值对我们可以用(Integer,String)。之后用一个arraylist来存储timestamp。题目的数量级是2*105次方,如果直接暴力查找,大概率过不了。所以需要使用二分,改一下条件,让其变成可以找到小于等于timestamp的最大数。按博主的写法,最后left会是小于等于timestamp最大数的前一个。当然,博主的写法如果找到了就会直接返回了。之后只要根据找到的timestamp去map里取值就可以了。

        一个key的情况解决了,就是多个key的问题了。多个key无非就是用hashmap把一种key的情况包起来。所以一开始存储的两个数据结构都要用hashmap包起来,一个key对应一个map<Integer,String>和一个arraylist。之后就是修改set函数了:如果原本不存在这个key,就要新建一个新的map<Integer,String>和一个新的arraylist来存储这个key对应的value和timestamp。如果存在直接获取添加即可。再往后就是修改get函数了:如果不存在这个key对应的map或arraylist就说明还没有添加进来过,直接返回空字符串就行;如果存在,就按刚才一个的方法去做就可以了。

         今天这道题,用到了二分的变式,还是很有意义的,而且能够锻炼大家数据结构使用的熟练度。不过时间复杂度和空间复杂度都很大,大家可以去看看题解寻找更快更好的解决方法。

相关文章:

【每日一题】981. 基于时间的键值存储

981. 基于时间的键值存储 - 力扣&#xff08;LeetCode&#xff09; 设计一个基于时间的键值数据结构&#xff0c;该结构可以在不同时间戳存储对应同一个键的多个值&#xff0c;并针对特定时间戳检索键对应的值。 实现 TimeMap 类&#xff1a; TimeMap() 初始化数据结构对象void…...

IMU姿态解算,从IMU数据中计算旋转、速度、位置,IMU测量的原理

0. 预备 a. IMU测量值解释 IMU在测量时&#xff0c;得到的角速度或者加速度均是相对于地心惯性系结果&#xff0c;并且将该结果表示到Body坐标系下&#xff0c;就形成了最终的IMU输出。 记作&#xff1a; ω i b b \omega_{ib}^b ωibb​&#xff0c;表示body系相对于惯性系的…...

【Qt-17】Qt调用matlab生成的dll库

matlab生成dll库 1、matlab示例代码 function BDCube(x,y)[x,y,z] cylinder(x,y);t1 hgtransform;s1 surf(3*x,3*y,4*z,Parent,t1);grid onview(3)shading interp end 2、matlab环境配置 首先检查自己的mcc编译器是否可用&#xff0c;输出以下命令&#xff1a; &#x…...

css经典面试题(二)

文章目录 1、清除浮动2、opacity: 0、visibility: hidden、display: none 的区别3、css画一个三角形4、常见的主流浏览器前缀5、重绘与重排的区别&#xff1f;6、如何优化图片7、CSS3 中 transition 和 animation 的属性分别有哪些8、居中为什么要使用 transform&#xff08;为…...

jira搜索search issue条目rest实用脚本

官方文档链接地址&#xff1a; The Jira Cloud platform REST API 实用json请求脚本如下&#xff1a; {"fields": ["summary","status"],"jql": "project abc AND summary ~ 【%s】【coverity】 AND componentCoverity"…...

《C++ primer plus》精炼(OOP部分)——对象和类(5)

“学习是照亮心灵的火炬&#xff0c;它永不熄灭&#xff0c;永不止息。” 文章目录 类的自动和强制类型转换原始类型转换为自定义类型将自定义类型转换为原始类型 类的自动和强制类型转换 原始类型转换为自定义类型 可以用一个参数的构造函数来实现&#xff0c;例如&#xff…...

钉钉旧版服务端SDK支持异步方法的升级改造

最近项目中需要对接钉钉&#xff0c;有些钉钉 API 的访问需要使用旧版服务端 SDK 才能搞定&#xff0c;但是这个 SDK 使用的还是 .NET Framework 2.0 框架&#xff0c;不能跨平台部署&#xff0c;也不支持 async\await 的异步操作方法&#xff0c;Nuget 上也有其它用户改造的 .…...

【C语言】【数据存储】用%d打印char类型数据,猜结果是啥

题目代码如下&#xff1a; #include <stdio.h> int main() {char a -1;signed char b-1;unsigned char c-1;printf("a%d,b%d,c%d",a,b,c);return 0; }解题关键&#xff1a; 1.二进制存储&#xff1a;原码&#xff0c;反码&#xff0c;补码 互换 2.截断 3.整型…...

算法——双指针

1658. 将 x 减到 0 的最小操作数 - 力扣&#xff08;LeetCode&#xff09; 这道题的重点是&#xff0c;如何用最小的操作数&#xff0c;来使其x变为0——也可以看作是用最少的数据个数&#xff0c;来求和得到x。 ——但是我们可以知道&#xff0c;由于数据是从两端向中间取的…...

【PowerQuery】Excel的PowerQuery按需刷新

将数据通过PowerQuery 导入进来后,这里将进行数据分组运算,最终的数据计算结果将保存在Excel 表格中,图为销售统计结果。 在Excel中,如果我们希望进行销售统计的手动更新可以使用几种不同的方法来进行刷新: 刷新单一数据连接如果仅仅需要刷新单一数据连接的话我们可以通过…...

Django REST Farmowork初探

1.简介 Django REST framework &#xff08;简称&#xff1a;DRF&#xff09;是一个强大而灵活的 Web API 工具。 遵循RESTFullAPI风格&#xff0c;功能完善&#xff0c;可快速开发API平台。 官网文档&#xff1a;https://www.django-rest-framework.org 2. framwork的安装 …...

【flink进阶】-- Flink kubernetes operator 版本升级

目录 1、检查当前 flink kubernetes operator 版本 2、停止生产上正在运行的 flink job 3、升级 CRD...

Linux Ubuntu20.04深度学习环境快速配置命令记录

一、驱动安装 1、更新系统包 sudo apt-get updatesudo apt-get upgrade 2、安装显卡驱动 使用apt方式安装驱动&#xff0c;多数情况不容易成功&#xff0c; 使用一下方法更佳&#xff1a; 1.查看合适显卡的驱动版本 ubuntu-drivers devices NVIDIA GeForce 驱动程序 - …...

信息安全三级真题一

目录 一、单选题 二、填空题 三、综合题 一、单选题 二、填空题 三、综合题 知法懂法&#xff0c;请各位网络安全从业者遵守《网络安全法》、《个人信息保护法》 业%$务*$&联&#系 XHU3ZjUxXHU3ZWRjXHU4ZmQwXHU3ZWY0XHU2ZTE3XHU5MDBmXHU1NmUyXHU5NjFmXHUyMDBiXHU2M…...

RK3568-tftp更新设备树和内核nfs挂载文件系统

1. 注意:需要设备树和内核按以下修改才能支持tftp和nfs。 1.1 修改设备树: diff --git a/arch/arm64/boot/dts/rockchip/OK3568-C-linux.dts b/arch/arm64/boot/dts/rockchip/OK3568-C-linux.dts index 178b4d831..34cb57ffd 100644 --- a/arch/arm64/boot/dts/rockchip/OK…...

FIR滤波器简述及FPGA仿真验证

数字滤波器的设计&#xff0c;本项目做的数字滤波器准确来说是FIR滤波器。 FIR滤波器&#xff08;有限冲激响应滤波器&#xff09;&#xff0c;与另一种基本类型的数字滤波器——IIR滤波器&#xff08;无限冲击响应滤波器&#xff09;相对应&#xff0c;其实就是将所输入的信号…...

高速信号处理板资料保存:383-基于kintex UltraScale XCKU060的双路QSFP+光纤PCIe 卡设计原理图

基于kintex UltraScale XCKU060的双路QSFP光纤PCIe 卡 一、板卡概述 本板卡系我司自主研发&#xff0c;基于Xilinx UltraScale Kintex系列FPGA XCKU060-FFVA1156-2-I架构&#xff0c;支持PCIE Gen3 x8模式的高速信号处理板卡&#xff0c;搭配两路40G QSFP接口&#xf…...

QT:使用分组框、单选按钮、普通按钮、标签、行编辑器、垂直分布、水平分布做一个小项目

widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QRadioButton> //单选按钮 #include <QGroupBox> //分组框 #include <QHBoxLayout> //水平布局 #include <QVBoxLayout> //垂直布局 #include <QPushButton>…...

封装微信小程序隐私信息授权

隐私 代码 html &#xff08;modal 组件再后面封装有提供&#xff09; <modal isShow"{{show}}"><view class"privacy-auth-dialog"><view class"title">温馨提示</view><view class"content"><vi…...

【C#】FileInfo类 对文件进行操作

提示&#xff1a;使用FileInfo类时&#xff0c;要引用System.IO命名空间。 using System.IO; FileInfo类 生成文件删除文件移动文件复制文件获取文件名判断文件是否存在属性列表其它常用方法 生成文件 Create()&#xff1a;在指定路径上创建文件。 FileInfo myFile new FileIn…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...