当前位置: 首页 > 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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...