力扣labuladong——一刷day28
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣380. O(1) 时间插入、删除和获取随机元素
- 二、力扣710. 黑名单中的随机数
前言
常数时间删除-查找数组中的任意元素,且随机访问概率一致
如果想「等概率」且「在 O(1) 的时间」取出元素,一定要满足:底层用数组实现,且数组必须是紧凑的。 这样我们就可以直接生成随机数作为索引,从数组中取出该随机索引对应的元素,作为随机元素。 但如果用数组存储元素的话,插入,删除的时间复杂度怎么可能是 O(1) 呢? 可以做到!对数组尾部进行插入和删除操作不会涉及数据搬移,时间复杂度是 O(1)。 所以,如果我们想在 O(1) 的时间删除数组中的某一个元素 val,可以先把这个元素交换到数组的尾部,然后再 pop 掉。 交换两个元素必须通过索引进行交换对吧,那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。
一、力扣380. O(1) 时间插入、删除和获取随机元素
class RandomizedSet {private List<Integer> nums;private Map<Integer, Integer> valToIndex;public RandomizedSet() {nums = new ArrayList<>();valToIndex = new HashMap<>();}public boolean insert(int val) {if(valToIndex.containsKey(val)){return false;}nums.add(val);valToIndex.put(val,nums.size()-1);return true;}public boolean remove(int val) {if(!valToIndex.containsKey(val)){return false;}int deleteIndex = valToIndex.get(val);int curIndex = nums.size()-1;Collections.swap(nums, deleteIndex, curIndex);valToIndex.put(nums.get(deleteIndex),deleteIndex);nums.remove(nums.size()-1);valToIndex.remove(val);return true;}public int getRandom() {return nums.get((int)(Math.random()*nums.size()));}
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/
二、力扣710. 黑名单中的随机数
class Solution {int RZ;Map<Integer,Integer> map;public Solution(int n, int[] blacklist) {RZ = n - blacklist.length;map = new HashMap<>();for(int b : blacklist){map.put(b,666);}int last = n-1;for(int b : blacklist){if(b >= RZ){continue;}while(map.containsKey(last)){last --;}map.put(b,last);last --;}}public int pick() {int index = (int)(Math.random()*RZ);if(map.containsKey(index)){return map.get(index);}return index;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(n, blacklist);* int param_1 = obj.pick();*/
相关文章:
力扣labuladong——一刷day28
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣380. O(1) 时间插入、删除和获取随机元素二、力扣710. 黑名单中的随机数 前言 常数时间删除-查找数组中的任意元素,且随机访问概率一致 如果…...
2023年CCF非专业级别软件能力认证第二轮 (CSP-S)提高级C++语言试题
2023年CCF非专业级别软件能力认证第二轮 (CSP-S)提高级C语言试题 编程题第 1 题 问答题 密码锁(lock) 题目描述 小Y有一把五个拨圈的密码锁。如图所示,每个拨圈上是从0到9的数字。每个拨圈都是从0到9的循环…...
华为ensp:静态默认路由
静态路由 到r2 上的系统视图模式 下一跳为1.1.1.2 ip route-static 192.168.2.0 255.255.255.0 1.1.1.2 如果找2网段下一跳为1.1.1.2接口 默认路由 到r3上做的是默认路由 ip route-static 0.0.0.0 0 1.1.1.1 所有的流量去找1.1.1.1 查看效果 只要做完完整的路由就可…...
xss 通过秘籍
终极测试代码 <sCr<ScRiPt>IPT>OonN"\/(hrHRefEF)</sCr</ScRiPt>IPT> 第一关(没有任何过滤) 使用终极测试代码,查看源码 发现没有任何过滤,直接使用javascrupt中的alert弹框 <script>aler…...
Kibana使用Watcher监控服务日志并发送飞书报警(Markdown)
Watcher是什么 Kibana Watcher 是 Elasticsearch 的监控和告警工具,它允许你设置和管理告警规则以监控 Elasticsearch 数据和集群的状态。Kibana Watcher 可以监测各种指标和数据,然后在满足特定条件时触发警报。它提供了一种强大的方式来实时监控 Elas…...
Flutter笔记:光影动画按钮、滚动图标卡片组等
Flutter笔记 scale_design更新:光影动画按钮、滚动图标卡片组 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263…...
【论文】利用移动性的比例公平蜂窝调度测量和算法
(一支笔一包烟,一节论文看一天 )(一张纸一瓶酒,一道公式推一宿) 摘要1. 引言2. 相关工作3. 模型和问题公式4. 预测FPF调度 ( P F ) 2 S (PF)^2S (…...
内存条选购注意事项(电脑,笔记本)
电脑内存条的作用、选购技巧以及注意事项详解 - 郝光明的个人空间 - OSCHINA - 中文开源技术交流社区 现在的电脑直接和内存条联系 电脑上的所有输入和输出都只能依靠内存条 现在买双条而不是单条 买两个相同的内存条最好 笔记本先分清是低电压还是标准电压,DD…...
ChatGPT 宕机?OpenAI 将中断归咎于 DDoS 攻击
您的 ChatGPT 已关闭吗?您是否遇到 ChatGPT 问题,例如连接问题或遇到“长响应时出现网络错误”?– ChatGPT 遭受了一系列 DDoS 攻击,显然是由匿名苏丹组织策划的。 OpenAI 的 ChatGPT 是一款流行的人工智能聊天机器人,…...
go单元格测试
编写单元测试(Unit Test)是一种测试方法,用于验证代码中的单个功能单元(通常是函数或方法)是否按照预期工作。以下是编写单元测试的一般步骤: 1. 创建测试文件:在项目的测试目录中创建一个新的…...
JavaScript理解表达式和语句的含义
JavaScript中的表达式和语句都是用于完成特定计算或操作的语言构件,但它们有着不同的含义和用途: 表达式(expression)是用来计算并返回一个值的代码片段,可以包含变量、数值、函数调用、运算符等。表达式的运算结果可以被赋值给变量、作为函数…...
Visual Studio导入Wiinform项目文件,引用显示黄色感叹号
参考博客 第一步: 开程序包管理控制台 vs->工具->NuGet包管理器->程序包管理控制台 Update-Package –reinstall 第二步: 删除.csproj 文件片段 // 整个模块全部删除 包括标签中所含有的任何内容 <Target Name"EnsureNuGetPackage…...
深入研究SVN代码检查的关键工具:svnchecker vs. SonarQube,选择最适合你的代码检查工具
目录 一、SVN代码检查(整合svnchecker)1、创建SVN代码库2、下载安装包3、修改SVN配置4、新建代码检查配置文件(名称自定义)5、hooks目录添加配置文件6、设置只对Java文件进行检查7、测试 二、SonarQube代码检测1、什么是SonarQube2、MySQL数据库的安装3、SonarQube服务端软件安…...
博客积分上一万一千了
博客积分上一万一千了 充满自信,继续前进。...
docker 构建并运行 python项目
此处不重述docker安装及基本命令,可参考另一篇文章centos7 安装 docker_centos7 docker network rm-CSDN博客文章浏览阅读111次。1、 1.1 docker 官网 Empowering App Development for Developers | DockerLearn how Docker helps developers bring their ideas to …...
django建站过程(4)创建文档显示页面
django建站过程(4)创建文档显示页面 创建文档显示页面项目主文件夹schoolapps中的文件urls.py在APP“baseapps”中创建url.py文件编写视图模板继承bootstrap创建head.html创建doclist.html创建docdetail.html 使用 markdown 编辑器安装模块Model 模型的d…...
uniapp本地存储的几种方式
在UniApp中,你可以使用本地存储来保存和获取数据,以便在应用的不同页面之间共享数据或在应用关闭后仍然保存数据。UniApp提供了两种主要的本地存储方式:uni.setStorage 和 uni.getStorage,以及 uni.removeStorage 用于删除数据。这…...
74hc595模块参考
74hc595模块参考 8位串行并行输出(SIPO)移位寄存器 使用74HC595移位寄存器扩展微控制器上的输出引脚数量。如果你需要扩充输入引脚的数量那么你需要74HC165移位寄存器。 SER(串行输入)引脚用于一次一位地将数据发送到移位寄存器…...
【Unity细节】Failed importing package???Unity导包失败?
👨💻个人主页:元宇宙-秩沅 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 秩沅 原创 😶🌫️收录于专栏:unity细节和bug 😶🌫️优质专栏 ⭐【…...
【问题记录】docker pull 镜像的时候 devel 版本和无 devel 版本的差别
这两个Docker镜像的主要区别在于是否包含了 CUDA 的开发工具集(CUDA Toolkit)。 docker pull cnstark/pytorch:1.10.0-py3.8.16-cuda11.1.1-ubuntu20.04这个镜像只包含运行时所需的库文件,并没有额外安装CUDA Toolkit。 docker pull cnstar…...
RAG 还是 Lucene:私有化部署客服系统的 AI 知识库架构选型渤
在之前的文章中,我们花了大量的篇幅,从记录后端pod真实ip开始说起,然后引入envoy,再解决了各种各样的需求:配置自动重载、流量劫持、sidecar自动注入,到envoy的各种能力:熔断、流控、分流、透明…...
如何用3分钟将B站视频转成文字稿?这个免费开源工具让你告别手动记录
如何用3分钟将B站视频转成文字稿?这个免费开源工具让你告别手动记录 【免费下载链接】bili2text Bilibili视频转文字,一步到位,输入链接即可使用 项目地址: https://gitcode.com/gh_mirrors/bi/bili2text 你是否曾经面对长达几小时的B…...
Chandra OCR实战案例:扫描文档转Markdown,保留表格公式原格式
Chandra OCR实战案例:扫描文档转Markdown,保留表格公式原格式 你是不是也遇到过这样的烦恼?手头有一堆扫描的PDF文档、老旧的合同、复杂的学术论文,里面全是表格、公式和特殊排版。想把它们变成可编辑的电子版,要么手…...
YOLOv9镜像实战应用:安防监控、工业质检等场景落地解析
YOLOv9镜像实战应用:安防监控、工业质检等场景落地解析 1. 为什么选择YOLOv9镜像 在目标检测领域,YOLO系列模型一直以速度和精度的平衡著称。最新发布的YOLOv9通过引入可编程梯度信息(Programmable Gradient Information)技术&a…...
Nuxt v4.x 应用创建中的常见问题与解决方案
Nuxt v4.x 应用创建中的常见问题与解决方案 在构建现代Web应用时,Nuxt.js以其出色的开发体验和强大的功能集赢得了众多开发者的青睐。随着v4.x版本的发布,这个基于Vue.js的框架带来了更多令人兴奋的特性,但同时也伴随着一些新的挑战。本文将深…...
从零构建ReAct Agent:完整代码实现解析
从零构建ReAct Agent 说实话,当我第一次看到 ReAct 这个名词的时候,还以为是某个新出的前端框架。直到折腾了半天才发现,这玩意儿是解决 LLM “一本正经胡说八道” 的神器。 作为一个在 LLM 应用开发里踩过无数坑的人,我可以负责任…...
AI原生研发不是“加AI”,而是重构研发DNA(SITS2026白皮书核心框架首次解密)
第一章:什么是AI原生软件研发?SITS2026给你答案 2026奇点智能技术大会(https://ml-summit.org) AI原生软件研发不是对传统开发流程的简单增强,而是以大模型为第一公民、以提示工程与推理编排为基本范式、以LLM-as-OS架构为底层支撑的全新研发…...
一键修改文件创建 修改 访问时间,这款小工具太方便 小巧无广告
今天再给大家带来一款吾爱原创的轻量小工具 ——文件时间编辑器,由 Thebzk 开发,整个软件只有 376 KB,小巧便携,功能纯粹。 软件下载地址 操作也非常简单:选中需要修改的文件或文件夹,自定义设置好想要的…...
AVP系统背后的技术拆解:车端、场端、云端到底谁在“开车”?
AVP系统技术全景:车端、场端与云端的协同博弈 当一辆特斯拉Model 3在商场停车场自动寻找车位时,它可能正经历着三种技术路线的激烈博弈。AVP(自主代客泊车)系统作为自动驾驶技术中最先商业化的场景,其背后的技术架构选…...
别再只盯着Setup/Hold了!聊聊STA里Cell Delay和Net Delay那些‘反常’的负值现象
负延迟现象:STA中Cell Delay与Net Delay的深层解析 在数字集成电路设计中,静态时序分析(STA)是确保芯片功能正确性的关键环节。大多数工程师对Setup/Hold时间检查已经驾轻就熟,但当我们深入时序模型的细节时࿰…...
