acwing算法基础之基础算法--整数离散化算法
目录
- 1 知识点
- 2 模板
1 知识点
整个范围很大,但存在的数据点很少。比如从 − 1 0 9 -10^9 −109到 1 0 9 10^9 109,但总共只有 1 0 6 10^6 106个数。
可以采用离散化的思想来做,即将离散的大数值映射成连续的小数值(一般是 1 , 2 , 3 , ⋯ , n 1,2,3,\cdots,n 1,2,3,⋯,n)。
看到这里,你是不是觉得小数值与向量下标比较相似,是的,它本质就是下标,从1开始编号还是从0开始编号,取决于业务逻辑。acwing讲解例题中是从1开始编号的。
2 模板
//输入是向量vector<int>alls
//输出是函数find(),输入大数值得到小数值
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());int find(vector<int> &alls, int x) { //找到大于等于x的第1个下标,题目中保证一定存在xint l = 0, r = alls.size() - 1;while (l < r) {int mid = (l + r) / 2;if (alls[mid] >= x) {r = mid;} else {l = mid + 1;}}return l + 1;//从1开始编号。如果返回l,表示从0开始编号。
} //其中unique()函数使用的是库函数,也可以自己实现,如下所示
vector<int>::iterator unique(vector<int> &a) {int j = 0;for (int i = 0; i < a.size(); ++i) {if (i == 0 || a[i] != a[i-1]) {a[j++] = a[i]; }}return a.begin() + j;
}
当然,上述模板也可以用哈希表来实现,如下,
//输入是向量vector<int>alls
//输出是哈希表mp,输入大数值得到小数值
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());unordered_map<int,int> mp;
for (int i = 0; i < alls.size(); ++i) {mp[alls[i]] = i + 1; //从1开始编号。如果写i,表示从0开始编号。
}
相关文章:
acwing算法基础之基础算法--整数离散化算法
目录 1 知识点2 模板 1 知识点 整个范围很大,但存在的数据点很少。比如从 − 1 0 9 -10^9 −109到 1 0 9 10^9 109,但总共只有 1 0 6 10^6 106个数。 可以采用离散化的思想来做,即将离散的大数值映射成连续的小数值(一般是 1 , …...
基于SSM框架的安全教育平台
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:Vue 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目:是 目录…...
Kafka生产者使用案例
1.生产者发送消息的过程 首先介绍一下 Kafka 生产者发送消息的过程: 1)Kafka 会将发送消息包装为 ProducerRecord 对象, ProducerRecord 对象包含了目标主题和要发送的内容,同时还可以指定键和分区。在发送 ProducerRecord 对象前,…...
EasyX图形库实现贪吃蛇游戏
⭐大家好,我是Dark Falme Masker,学习了动画制作及键盘交互之后,我们就可以开动利用图形库写一个简单的贪吃蛇小游戏,增加学习乐趣。 ⭐专栏:EasyX部分小游戏实现详细讲解 最终效果如下 首先包含头文件 #include<stdio.h> #…...
利用 Amazon CodeWhisperer 激发孩子的编程兴趣
我是一个程序员,也是一个父亲。工作之余我会经常和儿子聊他们小学信息技术课学习的 Scratch 和 Kitten 这两款图形化的少儿编程工具。 我儿子有一次指着书房里显示器上显示的 Visual Studio Code 问我,“为什么我们上课用的开发界面,和爸爸你…...
2023年中国分子筛稀土催化材料竞争格局及行业市场规模分析[图]
稀土催化材料能够起到提高催化剂热稳定性、催化剂活性、催化剂储氧能力,以及减少贵金属活性组分用量等作用,广泛应用于石油化工、汽车尾气净化、工业废气和人居环境净化、燃料电池等领域。 2015-2023年中国稀土催化材料规模及预测 资料来源:…...
vue3插件——vue-web-screen-shot——实现页面截图功能
最近在看前同事发我的vue3框架时,发现他们有个功能是要实现页面截图功能。 vue3插件——vue-web-screen-shot——实现页面截图功能 效果图如下:1.操作步骤1.1在项目中添加vvue-web-screen-shot组件1.2在项目入口文件导入组件——main.ts1.3在需要使用的页…...
简单总结Centos7安装Tomcat10.0版本
文章目录 前言JDK8安装部署Tomcat 前言 注意jdk与tomcat的兼容问题,其他的只要正确操作一般问题不大 Tomcat 是由 Apache 开发的一个 Servlet 容器,实现了对 Servlet 和 JSP 的支持,并提供了作为Web服务器的一些特有功能,如Tomca…...
ffmpeg中AVCodecContext和AVCodec的关系分析
怎么理解AVCodecContext和AVCodec的关系 AVCodecContext和AVCodec是FFmpeg库中两个相关的结构体,它们在音视频编解码中扮演着不同的角色。 AVCodecContext:是编解码器上下文结构体,用于存储音视频编解码器的参数和状态信息。它包含了进行音视…...
2023年中国门把手产量、销量及市场规模分析[图]
门把手行业是指专门从事门把手的设计、制造、销售和安装等相关业务的行业。门把手是门窗装饰硬件的一种,用于开启和关闭门窗,同时也具有装饰和美化门窗的作用。 门把手行业分类 资料来源:共研产业咨询(共研网) 随着消…...
HTML 核心技术点基础详细解析以及综合小案例
核心技术点 网页组成 排版标签 多媒体标签及属性 综合案例一 - 个人简介 综合案例二 - Vue 简介 02-标签语法 HTML 超文本标记语言——HyperText Markup Language。 超文本:链接 标记:标签,带尖括号的文本 标签结构 标签要成…...
BAT学习——批处理脚本(也称为BAT文件)常用语法元素与命令
批处理脚本(也称为BAT文件)使用Windows的批处理语言编写,它具有一些常用的语法元素和命令。以下是一些BAT编程的常用语法元素和命令: 命令行命令: 批处理脚本通常包含一系列Windows命令,例如echo࿰…...
AMD AFMF不但能用在游戏,也适用于视频
近期AMD发布了AMD Software Adrenalin Edition预览版驱动程序,增加了对平滑移动帧(AMD Fluid Motion Frames,AFMF)功能的支持,也就是AMD的“帧生成”技术,与DLSS 3类似,作为FidelityFX Super Re…...
CSS 常用样式浮动属性
一、概述 CSS 中,浮动属性的作用是让元素向左或向右浮动,使其他元素围绕它排布,常用的浮动属性有以下几种: float: left; 使元素向左浮动,其他元素从右侧包围它。 float: right; 使元素向右浮动,其他元素…...
Linux引导故障排除:从问题到解决方案的详细指南
1 BIOS初始化 通电->对硬件检测->初始化硬件时钟 2 磁盘引导及其修复 2.1 磁盘引导故障 磁盘主引导记录(MBR)是在0磁道1扇区位置,446字节。 MBR作用:记录grub2引导文件的位置 2.2 修复 步骤:1、光盘进…...
【vim 学习系列文章 6 -- vim 如何从上次退出的位置打开文件】
文章目录 1.1 vim 如何从上次退出的位置打开文件1.2 autogroup 命令学习1.2.1 augroup 基本语法 1.3 vim call 命令详细介绍 1.1 vim 如何从上次退出的位置打开文件 假设我打开了文件 test.c,然后我向下滚动到第 50 行,然后我做了一些修改并关闭了文件。…...
怎样学习C#上位机编程?
怎样学习C#上位机编程? 00001. 掌握C#编程和.NET框架基础。 00002. 学WinForm应用开发,了解控件使用和事件编程。 00003. 熟悉基本数据结构和算法,如链表、栈、队列。 00004. 理解串口通信协议和方法,用于与硬件交互。 00005…...
【算法-动态规划】两个字符串的删除操作-力扣 583
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...
【06】基础知识:typescript中的泛型
一、泛型的定义 在软件开发中,我们不仅要创建一致的定义良好的API,同时也要考虑可重用性。 组件不仅能支持当前数据类型,同时也能支持未来的数据类型,这在创建大型系统时提供了十分灵活的功能。 在像 C# 和 Java 这样的语言中&…...
flutter 绘制原理探究
文章目录 Widget1、简介2、源码分析Element1、简介2、源码分析RenderObjectWidget 渲染过程总结思考Flutter 的核心设计思想便是“一切皆 Widget”,Widget 是 Flutter 功能的抽象描述,是视图的配置信息,同样也是数据的映射,是 Flutter 开发框架中最基本的概念。 在 Flutter…...
[Java]SPI扩展功能
一、什么是SPI Java SPI(Service Provider Interface)是Java官方提供的一种服务发现机制。 它允许在运行时动态地加载实现特定接口的类,而不需要在代码中显式地指定该类,从而实现解耦和灵活性。 二、实现原理 基于 Java 类加载…...
机器人命令表设计
演算命令 CLEAR 将数据 1 上被指定的编号以后的变数的内容,以及数据 2 上仅被指定的个数都清除至 0。 INC 在被指定的变数内容上加上 1。 DEC 在被指定的变数内容上减掉 1。 SET 在数据 1 上设定数据 2。 ADD 将数据 1 和数据 2 相加,得出的结果保存在数…...
STM32--WDG看门狗
文章目录 WDG简介IWDGIWDG的超时计算WWDGWWDG超时和窗口值设定独立看门狗工程WWDG工程 WDG简介 WDG看门狗(Watchdog Timer)是一种常见的硬件设备,在STM32F10系列中,有两种看门狗,分别是独立看门狗和窗口看门狗&#x…...
(※)力扣刷题-字符串-实现 strStr()(KMP算法)
28 实现 strStr() 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。 示例 1: 输入: haystack “hello”, needle “ll” 输出: 2 示例…...
Redis 集群 Redis 事务 Redis 流水线 Redis 发布订阅 Redis Lua脚本操作
Redis 集群 & Redis 事务 & Redis 流水线 & Redis 发布订阅 Redis 集群linux安装redis主从配置查看当前实例主从信息 Redis Sentinelsentinel Redis Cluster Redis 事务Redis 流水线Redis 发布订阅Redis Lua脚本操作 Redis 集群 linux安装redis 下载安装包&#…...
【算法与数据结构】--常见数据结构--栈和队列
一、栈 栈(Stack) 是一种基本的数据结构,具有后进先出(LIFO)的特性,类似于现实生活中的一叠盘子。栈用于存储一组元素,但只允许在栈顶进行插入(入栈)和删除(…...
Linux shell编程学习笔记11:关系运算
Linux Shell 脚本编程和其他编程语言一样,支持算数、关系、布尔、字符串、文件测试等多种运算。前面几节我们研究了 Linux shell编程 中的 字符串运算 和 算术运算,今天我们来研究 Linux shell编程中的的关系运算。 一、关系运算符功能说明 运算符说明…...
JS标准库
学习一门编程语言不仅是掌握其语法。同等重要的是学习其标准库,从而熟练掌握语言本身提供的所有工具。 1 定型数组 js常规数组与C和Java等较低级语言的数组类型还是有很大区别。ES6新增了定型数组,与这些语言的低级数组非常接近。 定型数组严格来说并…...
Android 12.0 hal层添加自定义hal模块功能实现
1. 前言 在12.0的系统rom定制化开发中,在 对hal模块进行开发时,需要通过添加自定义的hal模块来实现某些功能时,就需要添加hal模块的相关功能,接下来就来实现一个案例来供参考 接下来就来具体实现这个功能 2.hal层添加自定义hal模块功能实现的核心类 hardware\interfaces…...
如何理解vue声明式渲染
Vue.js中的声明式渲染是一种用来描述用户界面的方式,它强调“声明”应该如何渲染页面,而不需要关心底层的DOM操作。这与传统的命令式渲染方式,即手动控制DOM元素的创建、更新和销毁,形成了鲜明的对比。 理解Vue的声明式渲染的关键…...
【已解决】Vue全局引入scss 个别页面不生效 / 不自动引入全局样式
项目里配置了全局样式的引入,今天新建了 demo 页面去修改 element 的样式,发现全局的样式没有引入进来。 问题原因 在此页面 没有任何样式导致的 项目在编译的时候,会把 .vue 文件的样式抽离到单独的 css 文件中。 当该页面没有css代码的时…...
MySQL之双主双从读写分离
一个主机 Master1 用于处理所有写请求,它的从机 Slave1 和另一台主机 Master2 还有它的从 机 Slave2 负责所有读请求。当 Master1 主机宕机后, Master2 主机负责写请求, Master1 、 Master2 互为备机。架构图如下 : 准备 我们…...
使用eBPF加速阿里云服务网格ASM
背景 随着云原生应用架构的快速发展,微服务架构已经成为了构建现代应用的主要方式之一。而在微服务架构中,服务间的通信变得至关重要。为了实现弹性和可伸缩性,许多组织开始采用服务网格技术来管理服务之间的通信。 Istio作为目前最受欢迎的…...
大型数据集处理之道:深入了解Hadoop及MapReduce原理
在大数据时代,处理海量数据是一项巨大挑战。而Hadoop作为一个开源的分布式计算框架,以其强大的处理能力和可靠性而备受推崇。本文将介绍Hadoop及MapReduce原理,帮助您全面了解大型数据集处理的核心技术。 Hadoop简介 Hadoop是一个基于Google…...
LCR 095. 最长公共子序列(C语言+动态规划)
1. 题目 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(…...
程序员不写注释:探讨与反思
一、为什么程序员不写注释 当程序员选择不写注释时,通常有一系列常见原因,这些原因可以影响他们的决策和行为。同时,这个决策可能会带来多方面的影响和后果。以下是详细阐述为什么程序员不写注释的常见原因以及这种决策可能导致的影响和后果…...
《论文阅读:Dataset Condensation with Distribution Matching》
点进去这篇文章的开源地址,才发现这篇文章和DC DSA居然是一个作者,数据浓缩写了三篇论文,第一篇梯度匹配,第二篇数据增强后梯度匹配,第三篇匹配数据分布。DC是匹配浓缩数据和原始数据训练一次后的梯度差,DS…...
免费chatGPT工具
发现很多人还是找不到好用的chatGPT工具,这里分享一个邮箱注册即可免费试用。 PromptsZone - 一体化人工智能平台使用 PromptsZone 与 ChatGPT、Claude、AI21 Labs、Google Bard 聊天,并使用 DALL-E、Stable Diffusion 和 Google Imagegen 创建图像&…...
数据分析基础:数据可视化+数据分析报告
数据分析是指通过对大量数据进行收集、整理、处理和分析,以发现其中的模式、趋势和关联,并从中提取有价值的信息和知识。 数据可视化和数据分析报告是数据分析过程中非常重要的两个环节,它们帮助将数据转化为易于理解和传达的形式࿰…...
settings.xml的文件配置大全
settings.xml 文件中最常配置的还是这几个标签 localRepository和mirrors settings.xml文件官方文档地址 <settings xmlns"http://maven.apache.org/SETTINGS/1.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"ht…...
极简c++(7)类的继承
为什么要用继承 子类不必复制父类的任何属性,已经继承下来了;易于维护与编写; 类的继承与派生 访问控制规则 一般只使用Public! 构造函数的继承与析构函数的继承 构造函数不被继承! 在创建子类对象的时候&…...
DOSBox和MASM汇编开发环境搭建
DOSBox和MASM汇编开发环境搭建 1 安装DOSBox2 安装MASM3 编译测试代码4 运行测试代码5 调试测试代码 本文属于《 X86指令基础系列教程》之一,欢迎查看其它文章。 1 安装DOSBox 下载DOSBox和MASM:https://download.csdn.net/download/u011832525/884180…...
047:mapboxGL本地上传shp文件,在map上解析显示图形
第047个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中本地上传shp文件,利用shapefile读取shp数据,并在地图上显示图形。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共117行)加载shapefile.js方式…...
Windows下DataGrip连接Hive
DataGrip连接Hive 1. 启动Hadoop2. 启动hiveserver2服务3. 启动元数据服务4. 启动DG 1. 启动Hadoop 在控制台中输入start-all.cmd后,弹出下图4个终端(注意终端的名字)2. 启动hiveserver2服务 单独开一个窗口启动hiveserver2服务,…...
Xshell7和Xftp7超详细下载教程(包括安装及连接服务器附安装包)
1.下载 1.官网地址: XSHELL - NetSarang Website 选择学校免费版下载 2.将XSHELL和XFTP全都下载下来 2.安装 安装过程就是选择默认选项,然后无脑下一步 3.连接服务器 1.打开Xshell7,然后新建会话 2.填写相关信息 出现Connection establi…...
ASP.net数据从Controller传递到视图
最常见的方式是使用模型或 ViewBag。 使用模型传递数据: 在控制器中,创建一个模型对象,并将数据赋值给模型的属性。然后将模型传递给 View 方法。 public class HomeController : Controller {public IActionResult Index(){// 创建模型对…...
c++ 友元函数 友元类
1. 友元函数 1.1 简介 友元函数是在类的声明中声明的非成员函数,它被授予访问类的私有成员的权限。这意味着友元函数可以访问类的私有成员变量和私有成员函数,即使它们不是类的成员。 一个类中,可以将其他类或者函数声明为该类的友元&#…...
Spring推断构造器源码分析
Spring中bean虽然可以通过多种方式(Supplier接口、FactoryMethod、构造器)创建bean的实例对象,但是使用最多的还是通过构造器创建对象实例,也是我们最熟悉的创建对象的方式。如果有多个构造器时,那Spring是如何推断使用…...
十五、【历史记录画笔工具组】
文章目录 历史记录画笔工具历史记录艺术画笔工具 历史记录画笔工具 历史记录画笔工具很简单,就是将画笔工具嗯,涂抹过的修改过的地方,然后用历史记录画笔工具重新修改回来,比如我们将三叠美元中的一叠用画笔工具先涂抹掉…...
Spark上使用pandas API快速入门
文章最前: 我是Octopus,这个名字来源于我的中文名--章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的…...