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

LeetCode 2671.频率跟踪器:俩计数哈希表

【LetMeFly】2671.频率跟踪器:俩计数哈希表

力扣题目链接:https://leetcode.cn/problems/frequency-tracker/

请你设计并实现一个能够对其中的值进行跟踪的数据结构,并支持对频率相关查询进行应答。

实现 FrequencyTracker 类:

  • FrequencyTracker():使用一个空数组初始化 FrequencyTracker 对象。
  • void add(int number):添加一个 number 到数据结构中。
  • void deleteOne(int number):从数据结构中删除一个 number 。数据结构 可能不包含 number ,在这种情况下不删除任何内容。
  • bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字,则返回 true,否则返回 false

 

示例 1:

输入
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
输出
[null, null, null, true]解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.add(3); // 数据结构现在包含 [3, 3]
frequencyTracker.hasFrequency(2); // 返回 true ,因为 3 出现 2 次

示例 2:

输入
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
输出
[null, null, null, false]解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // 数据结构现在包含 [1]
frequencyTracker.deleteOne(1); // 数据结构现在为空 []
frequencyTracker.hasFrequency(1); // 返回 false ,因为数据结构为空

示例 3:

输入
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
输出
[null, false, null, true]解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // 返回 false ,因为数据结构为空
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.hasFrequency(1); // 返回 true ,因为 3 出现 1 次

 

提示:

  • 1 <= number <= 105
  • 1 <= frequency <= 105
  • 最多调用 adddeleteOnehasFrequency 共计 2 * 105

方法一:俩计数哈希表

  • 使用一个哈希表val2times记录值val一共出现了多少次。
  • 使用一个哈希表times2times记录val2times中的每个times一共出现了多少次。

添加或删除元素时,更新val2times[val]的值,并更新times2times[val2times[val] (+diff)]的值。

询问是否存在出现了frequency次的数字时,直接返回times2times[frequency]是否非零。

  • 时间复杂度 O ( 1 ) / 操作 O(1)/操作 O(1)/操作
  • 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++
class FrequencyTracker {
private:unordered_map<int, int> val2times, times2times;
public:FrequencyTracker() {}void add(int number, int diff=1) {int originalTimes = val2times[number];val2times[number] += diff;times2times[originalTimes]--;times2times[originalTimes + diff]++;}void deleteOne(int number) {if (val2times[number]) {add(number, -1);}}bool hasFrequency(int frequency) {return times2times[frequency];}
};
Python
# from collections import defaultdictclass FrequencyTracker:def __init__(self):self.val2times = defaultdict(int)self.times2times = defaultdict(int)def add(self, number: int, diff=1) -> None:originalTimes = self.val2times[number]self.val2times[number] += diffself.times2times[originalTimes] -= 1self.times2times[originalTimes + diff] += 1def deleteOne(self, number: int) -> None:if self.val2times[number]:self.add(number, -1)def hasFrequency(self, frequency: int) -> bool:return self.times2times[frequency] != 0

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136922983

相关文章:

LeetCode 2671.频率跟踪器:俩计数哈希表

【LetMeFly】2671.频率跟踪器&#xff1a;俩计数哈希表 力扣题目链接&#xff1a;https://leetcode.cn/problems/frequency-tracker/ 请你设计并实现一个能够对其中的值进行跟踪的数据结构&#xff0c;并支持对频率相关查询进行应答。 实现 FrequencyTracker 类&#xff1a;…...

NAT笔记

NAT 用于实现内网和外网之间的互访。 静态NAT 静态NAT实现内网地址和外网地址的一对一转换。 有2种配置方法&#xff1a; 全局模式下设置静态NAT [R1]nat static global 172.10.10.10 inside 192.168.10.10 [R1]int g0/0/1 #外网接口 [R1-GigabitEthernet0/0/1]nat static…...

MySQL 数据库的备份和还原

1.命令行 备份语法 mysqldump -u用户名 -p密码 数据库名称 > 保存的路径还原语法 1.登陆数据库 2.创建数据库 3.使用数据库 4.执行文件 source 文件路径2.图形化(太简单了不写了) 点击返回 MySQL 快速学习目录...

初识CSS样式 与 文本背景样式

目录 前言: 1.什么是CSS: 2.关于css的主要特性: 2.1层叠性&#xff1a; 2.2继承性&#xff1a; 2.3优先级&#xff1a; 2.4.CSS的组成结构: 3.css样式的三种写法: 3.1内联样式&#xff1a; 3.1.2存在的优点和缺点: 3.2内部样式表&#xff1a; 3.2.2存在的优点和缺点:…...

JSR380验证框架

依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-validation</artifactId> </dependency>demo Size(min10,max200 ,message"描述需要控制在10到200字符"&#xff09; Min(valu…...

百度paddleocr GPU版部署

显卡&#xff1a;NVIDIA GeForce RTX 4070&#xff0c;Nvidia驱动程序版本&#xff1a;537.13 Nvidia驱动程序能支持的最高cuda版本&#xff1a;12.2.138 Python&#xff1a;python3.10.11。试过python3.12&#xff0c;安装paddleocr失败&#xff0c;找不到相关模块。 飞桨版本…...

node.js 常用命令

Node.js的常用命令包括多种类型&#xff0c;从运行JavaScript文件到管理Node.js的模块和包。以下是一些主要的Node.js常用命令&#xff1a; 运行JavaScript文件&#xff1a; node filename.js 这个命令会调用Node.js程序来运行指定的JavaScript文件。 查看文件和目录&#xf…...

Easypoi实现导出Excel(简单高效)

今天做报表导出&#xff0c;网上找了很多导出的方法&#xff0c;最后总结发现以下方法是最简便&#xff0c;更易维护的导出方法&#xff0c;下面来分享给大家。 1、首先引入相关依赖 <!--EasyPoi 报表--><dependency><groupId>cn.afterturn</groupId>…...

python之pathlib库使用介绍

pathlib 是 Python 标准库中用于处理文件路径的模块。它提供了一种面向对象的方式来操作文件和目录路径&#xff0c;简化了路径操作的编码和跨平台的兼容性。下面是 pathlib 库的基本介绍和使用方法&#xff1a; 1.导入 pathlib 模块 from pathlib import Path 2.创建路径对…...

Java:设计模式

文章目录 参考简介工厂模式简单工厂模式工厂方法模式抽象工厂模式总结 单例模式预加载懒加载线程安全问题 策略模式 参考 知乎 简介 总体来说设计模式分为三类共23种。 创建型模式&#xff0c;共五种&#xff1a;工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模…...

【链表】Leetcode 19. 删除链表的倒数第 N 个结点【中等】

删除链表的倒数第 N 个结点 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 解题思路 1、使用快慢指针找到要删除节点的前一个节点。2、删…...

亚马逊认证考试系列 - 知识点 - 安全组简介

AWS安全组是一种虚拟防火墙&#xff0c;用于控制实例进出网络流量。安全组是一个实例级别的防火墙&#xff0c;可以定义哪些流量可以进入或离开特定的EC2实例。 功能&#xff1a;安全组可以用于限制特定类型的流量&#xff0c;如HTTP或SSH&#xff0c;允许特定IP地址范围的流量…...

同向双指针合集(力扣)

283. 移动零 代码 class Solution { public:void moveZeroes(vector<int>& nums) {int n nums.size();int l 0, r 0;while(r < n){if(nums[r]){swap(nums[l],nums[r]);l;}r;}} };209. 长度最小的子数组 代码 class Solution { public:int minSubArrayLen(i…...

G - Find a way

题目分析 1.双重bfs,遍历两个起点求最短路再计算总和即可 2.唯一的坑点在于对于一个KFC&#xff0c;两人中可能有一个到不了&#xff0c;所以还要对到不了的点距离做处理 #include <bits/stdc.h> using namespace std; using ll long long; const int N 220;struct pos…...

AJAX 02 案例、Bootstrap框架

AJAX 学习 AJAX 2 综合案例黑马 API01 图书管理Bootstrap 官网Bootstrap 弹框图书管理-渲染列表图书管理-添加图书图书管理-删除图书图书管理 - 编辑图书 02 图片上传03 更换图片04 个人信息设置信息渲染头像修改补充知识点&#xff1a;label扩大表单的范围 AJAX 2 综合案例 黑…...

SinoDB客户端工具dbaccess

类似Oracle的客户端工具sqlplus&#xff0c;Mysql的客户端工具mysql&#xff0c;SinoDB数据库也有自带的命令行客户端工具dbaccess。 dbaccess 识别用户输入&#xff0c;将用户输入的 SQL 语句打包发送给 SinoDB 数据库服务器执行&#xff0c;然后接收服务器的执行结果&#xf…...

postman学习

一、如何学习postman工具 1、下载和安装 Postman&#xff1a; 首先&#xff0c;从 Postman 官方网站&#xff08;https://www.postman.com&#xff09;下载并安装 Postman 应用程序。 2、了解基本概念&#xff1a; 在开始学习之前&#xff0c;了解一些基本概念&#xff0c;…...

【Linux】初识进程

目录 操作系统是什么 设计操作系统的目的 操作系统的定位 如何理解管理 管理的本质 管理的例子 计算机的管理概念图 操作系统管理逻辑的六字真言 系统调用和库函数的概念 进程 进程的概念 什么是PCB&#xff1f; PCB的主要内容 如何查看进程&#xff1f; 通过系统…...

有关Theano和PyTensor库

根据Github里面的介绍&#xff0c;PyTensor是源于Theano&#xff0c; Theano目前应该已经不再开发了&#xff0c;更新都是很多年前。 因此PyTensor在背景介绍中说 PyTensor is a fork of Aesara, which is a fork of Theano. Theano和PyTensor都是计算相关的库&#xff0c;可以…...

用 Open-Sora 高效创作视频,让创意触手可及

近年来&#xff0c;视频内容以爆炸式增长席卷了我们的生活。从短视频平台到直播带货&#xff0c;视频正成为人们获取信息和娱乐的主要方式。然而&#xff0c;传统视频制作流程往往耗时费力&#xff0c;对于普通用户来说门槛较高。 为了降低视频创作门槛&#xff0c;让更多人享…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...

【Redis】Redis从入门到实战:全面指南

Redis从入门到实战:全面指南 一、Redis简介 Redis(Remote Dictionary Server)是一个开源的、基于内存的键值存储系统,它可以用作数据库、缓存和消息代理。由Salvatore Sanfilippo于2009年开发,因其高性能、丰富的数据结构和广泛的语言支持而广受欢迎。 Redis核心特点:…...