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

最大间距问题

LeetCode164 最大间距 

 基数排序

#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int maximumGap(vector<int>& nums) {int n=nums.size();if(n<2) return 0;int exp=1;int Max=nums[0];vector<int> buf(n);for(int i=1;i<n;i++) Max=max(Max,nums[i]);while(exp<=Max){vector<int> cnt(10,0);for(int i=0;i<n;i++){int digit=(nums[i]/exp)%10;cnt[digit]++;}for(int i=1;i<10;i++) cnt[i]=cnt[i]+cnt[i-1];for(int i=n-1;i>=0;i--){int digit=(nums[i]/exp)%10;buf[cnt[digit]-1]=nums[i];cnt[digit]--;}copy(buf.begin(),buf.end(),nums.begin());exp*=10;}int res=0;for(int i=1;i<n;i++) res=max(nums[i]-nums[i-1],res);return res;}
};

分桶法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int maximumGap(vector<int>& nums){int Min=*min_element(nums.begin(),nums.end());int Max=*max_element(nums.begin(),nums.end());if(Max-Min<=1) return Max-Min;int n=nums.size();int d=(Max-Min+n-2)/(n-1);vector<pair<int,int>> buckets((Max-Min)/d+1,{0x3f3f3f3f,-0x3f3f3f3f});for(int i=0;i<n;i++){auto& [mn,mx]=buckets[(nums[i]-Min)/d];mn=min(nums[i],mn);mx=max(mx,nums[i]);}int res=0;int pre_max=0x3f3f3f3f;for(auto [mn,mx]:buckets){if(mx!=-0x3f3f3f3f){res=max(res,mn-pre_max);pre_max=mx;}}return res;}    
};

相关文章:

最大间距问题

LeetCode164 最大间距 基数排序 #include <iostream> #include <vector> using namespace std;class Solution { public:int maximumGap(vector<int>& nums) {int nnums.size();if(n<2) return 0;int exp1;int Maxnums[0];vector<int> buf(n)…...

【Hadoop|MapReduce篇】Hadoop序列化概述

1. 什么是序列化 序列化就是把内存中的对象&#xff0c;转换成字节序列&#xff08;或其他数据传输协议&#xff09;以便于存储到磁盘&#xff08;持久化&#xff09;和网络传输。 反序列化就是将收到的字节序列&#xff08;或其他数据传输协议&#xff09;或者磁盘的持久化数…...

【Elasticsearch系列】Elasticsearch中的分页

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

NLTK:一个强大的自然语言处理处理Python库

我是东哥&#xff0c;一名热爱技术的自媒体创作者。今天&#xff0c;我将为大家介绍一个非常有趣且强大的Python库——NLTK。无论你是刚刚接触Python的小白&#xff0c;还是对自然语言处理&#xff08;NLP&#xff09;有些许了解的朋友&#xff0c;NLTK都是一个值得学习的工具。…...

NUUO网络视频录像机 css_parser.php 任意文件读取漏洞复现

0x01 产品简介 NUUO网络视频录像机(Network Video Recorder,简称NVR)是NUUO Inc.生产的一种专业视频监控设备,它广泛应用于零售、交通、教育、政府和银行等多个领域。能够同时管理多个IP摄像头,实现视频录制、存储、回放及远程监控等功能。它采用先进的视频处理技术,提供…...

【支付】Stripe支付通道Java对接(产品 价格 支付 查询 退款 回调)

Stripe是一家美国科技公司&#xff0c;成立于2010年&#xff0c;由爱尔兰兄弟Patrick Collison和John Collison共同创立。该公司致力于提供高效、简洁的互联网支付收款服务&#xff0c;为开发者或商家提供支付API接口或代码&#xff0c;使商家的网站、移动APP支持信用卡付款。S…...

Unity3D 小案例 像素贪吃蛇 01 蛇的移动

Unity3D 小案例 像素贪吃蛇 第一期 蛇的移动 像素贪吃蛇 今天来简单制作一个小案例&#xff0c;经典的像素贪吃蛇。 准备 首先调整一下相机的设置&#xff0c;这里使用灰色的纯色背景&#xff0c;正交视图。 接着&#xff0c;创建一个正方形&#xff0c;保存为预制体&#…...

【STM32 MCU】stm32MCUs 32-bit Arm Cortex-M

stm32MCUs 32-bit Arm Cortex-M...

html+css网页设计 旅游 雪花旅行社5个页面

htmlcss网页设计 旅游 雪花旅行社5个页面 网页作品代码简单&#xff0c;可使用任意HTML辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码 1&#…...

vue3中的实例

实例类型 Vue2&#xff1a;每个Vue应用都是new Vue创建的一个新实例&#xff0c;创建的时候将data作为property添加到响应式系统中 vue3&#xff1a;createApp创建一个Application Instance、应用实例用来注册全局内容&#xff0c;大多数方法支持链式调用&#xff0c;返回实例…...

9.测试计划(包含笔试/面试题)

一、软件测试计划介绍 1.测试计划就是一份测试文档&#xff0c;一份描述测试工作计划的文档&#xff0c;对测试计划进行统筹安排。 2.测试计划的编写者就是测试组长&#xff0c;测试主管。 3.测试计划的查阅者&#xff1a;测试人员&#xff0c;测试主管&#xff0c;产品&#x…...

这 7 款AI应用将让你全新的iPhone 16成为电影制作的强大工具

苹果公司在周一的Glowtime发布会上揭晓了新款的iPhone 16 Pro系列。除了新加入的苹果智能功能和令人印象深刻的硬件升级外&#xff0c;它还获得了一套视频制作工具&#xff0c;让用户能够在一个几乎可以放进口袋的设备上制作整部电影。 这些升级中有一个48MP融合相机。它具有2…...

自注意力机制(self-attention)

自注意力机制&#xff08;self-attention&#xff09; 之前听过吴恩达老师的课&#xff0c;吴恩达老师CNN那一块讲的特别好&#xff0c;但是后面RNN这一部分我听的不是很明白&#xff0c;今天有看了李宏毅老师attention这部分的课&#xff0c;总结一下笔记。 self-attention …...

Nuxt3入门:过渡效果(第5节)

你好同学&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏、评论和关注。 Nuxt 利用 Vue 的 <Transition> 组件在页面和布局之间应用过渡效果。 一、页面过渡效果 你可以启用页面过渡效果&#xff0c;以便对所有页面应用自动过渡效果。 nuxt.config.js export defaul…...

【开发工具】IntelliJ IDEA插件推荐:Json Helper——让JSON处理更高效

导语&#xff1a;在Java开发过程中&#xff0c;JSON作为一种轻量级的数据交换格式&#xff0c;被广泛应用于前后端数据交互。今天&#xff0c;我要为大家介绍一款IntelliJ IDEA插件——Json Helper&#xff0c;帮助开发者更高效地处理JSON数据。 一、什么是Json Helper&#x…...

Lua垃圾回收机制

Lua垃圾回收机制 在 Lua 中&#xff0c;一共只有8种数据类型&#xff0c;分别为 nil 、boolean 、userdata 、number 、string 、 table 、 function 、 userdata 和 thread 。其中&#xff0c;只有 string table function thread 四种是以引用方式共享&#xff0c;是需要被 G…...

Java学习路线:详细指引

Java学习路线可以分为几个阶段&#xff0c;每个阶段都有其重点和推荐学习的内容。下面我将按照初学者、进阶和高级三个阶段来举例说明&#xff1a; 初学者阶段 目标&#xff1a; 熟悉Java基础语法理解面向对象编程掌握基本数据类型和数据结构学会使用IDE&#xff08;如Intel…...

商家转账到零钱如何开通-微信支付

商家转账到零钱是微信支付的一项实用功能&#xff0c;允许商户将资金从商户号余额直接转账到用户的微信零钱。我们以上万次成功申请的经验整理了本文的详细的步骤和建议以帮助商户可以快速开通该功能。 1. 准备工作 - 确认申请资格&#xff1a;只有公司性质的商户可以申请此功能…...

自研商家如何快速接入电商平台订单数据?

随着电子商务行业的快速发展&#xff0c;越来越多的商家开始寻求高效的订单管理和数据整合方案。对于那些自研系统的商家来说&#xff0c;如何实现与各大电商平台之间的无缝对接&#xff0c;成为了一项重要挑战。点三电商API正是为此类需求量身打造&#xff0c;为商家提供了一站…...

Win10下借助CMake编译OpenMVS

笔者在编译OpenMVS的过程十分曲折。刚开始借助CMake编译,能够把与库生成相关的工程编译出来,但是与可执行文件相关的工程会报错;后来参考官方教程借助VCPKG编译,发现VCPKG并没有想中强大、好用,最终也是遇到了各种问题没有编译成功。但是,笔者在解决问题的过程发现了问题…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

OPENCV图形计算面积、弧长API讲解(1)

一.OPENCV图形面积、弧长计算的API介绍 之前我们已经把图形轮廓的检测、画框等功能讲解了一遍。那今天我们主要结合轮廓检测的API去计算图形的面积&#xff0c;这些面积可以是矩形、圆形等等。图形面积计算和弧长计算常用于车辆识别、桥梁识别等重要功能&#xff0c;常用的API…...