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

【算法——双指针】

922. 按奇偶排序数组 II

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>nums = { 3,1,2,4 };int i = 0, j = 1;int n = nums.size() - 1;while (j < nums.size() && i < nums.size())   //如果奇偶任一方排好了,另一方自然排好了{//判断最后一个元素奇偶if (nums[n] % 2 != 0) {swap(nums[j], nums[n]);    j += 2;  //来到下一个奇数位置}else {swap(nums[i], nums[n]);i += 2;  //来到下一个偶数位置}}

287. 寻找重复数

快慢指针

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>nums = {}; int slow = nums[0];int fast = nums[nums[0]];while (slow != fast)     //一开始快指针一次2步,慢指针一次1步{fast = nums[nums[fast]];slow = nums[slow];}fast = 0;    //二者第一次相遇后,快指针重置为初始位置while (slow != fast)     //快慢都一次一步{fast = nums[fast];slow = nums[slow];}//最后返回fast和slow都可以

42. 接雨水

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

思想:每个格子上方的水量进行累加,首先求这个格子左边的最大格子和右边的最大值。

如果左边比右边小,那么左边就是一个兜底,我当前格子装水量就是左减当前格子数。

右比左小同理,右边就是兜底。

总结:

	min(left_max, max_right)-nums[i]
特例:当前格子数比左右都大,就直接为0,这时候没有人兜底了
最终式子:max(min(left_max, max_right)-nums[i],0)

两侧最大值怎么求? 

mainvector<int>nums = { 0,1,0,2,1,0,1,3,2,1,2,1 };int n = nums.size();vector<int>lmax(n);lmax[0] = nums[0];for (int i = 1; i < n; i++)        //左侧最大值不断继承lmax[i] = max(nums[i], lmax[i - 1]);vector<int>rmax(n);rmax[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0 ; i--)   //右侧最大值不断继承rmax[i] = max(nums[i], rmax[i + 1]);int sum = 0;for (int i = 1; i < n - 1; i++)     //计算sum += max(min(lmax[i - 1], rmax[i + 1]) - nums[i], 0);cout << sum;

881. 救生艇

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>people = { 3,5,3,4 };int limit = 3;int n = people.size();sort(people.begin(), people.end());      //进行一个排序int l = 0, r = n - 1;                    //左右指针int ans = 0;                     //计数while (l <= r){//这个边界处理至关重要,防止l和r指向同一个地方重复计数int sum = l==r ? people[l]:people[l] + people[r];  //最大和最小的都已经装不下来,所以直接最大的单独一个船if ( sum > limit)     {ans++;      //装当前遍历的最大的r--;        }else if( sum <= limit)  {ans++;     //两人一船l++;       r--;}}return ans;

变种:两个人一船时,必须体重之和为偶数。就把数组中奇偶分开,单独求最优,然后相加。

475. 供暖器

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>houses = { 1,5,7,10,12,15 };vector<int>heaters = { 3,6,10,13,19 };//进行一个排序是为了找到最优选择sort(houses.begin(), houses.end());sort(heaters.begin(), heaters.end());int ans = 0;   //ans就是目前最优记录//i指针代表房屋,j指针代表供暖//for就是一个一个遍历当前房屋最优择//然后k就是一个lambda表达式,当然你也可以自己定义一个函数,无所谓的//k解析:首先j进行边界约束。如果距离当前供暖<下一个供暖我们就停止,直接更新ans,否则下一个供暖检测//注意ans是公用的,自己看题目要求即可for (int i = 0, j = 0; i < houses.size(); i++)  {auto k = [=,&j]{return j == heaters.size() - 1 ||abs(houses[i] - heaters[j]) < abs(houses[i] - heaters[j + 1]);};while (!k())j++;ans = max(ans, abs(houses[i] - heaters[j]));}cout << ans << endl;

41. 缺失的第一个正数

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

整体思路就是:我们要实现,i下标索引上面放到数值是i+1,当出现间断的时候,就说明找到了target。

void f(vector<int>&nums, int l, int r);//交换函数main:vector<int>nums = { -3,2,1,8,5,4,2,3,5,13 };int l = 0, r = nums.size();//l指向0,r指向超出的部分,r属性1:代表“垃圾区域”。2:假设《最好的状态》,也是就[1,r]都有//l前面的元素肯定都满足我们《i上面是i+1的性质》while (l < r)   //l和r装上时说明[1,r]目标完成了{if (nums[l] == l + 1)   //代表我们找到了预期,直接下一个l++;   //不符合的放到垃圾区//nums[l]<=l,这个都<=l了肯定不符合要求,而且我们l之前的元素都已经符合预期了,//这个没有意义。//nums[l]>r,都超出我们的《最好状态了》,比我们期望的目标还要大。//nums[nums[l]-1]==nums[l]代表重复元素//然后我们的《最好状态变差,--r》else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) f(nums, l, --r);//不是垃圾元素,就开始排号else      f(nums, l, nums[l] - 1);}return l+1;

相关文章:

【算法——双指针】

922. 按奇偶排序数组 II 算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili main:vector<int>nums { 3,1,2,4 };int i 0, j 1;int n nums.size() - 1;while (j < nums.size() && i < nums.size()) //如果奇偶任一方排好了&#xff0c;另…...

Rocky Linux 9 中添加或删除某个网卡的静态路由的方法

使用ip命令配置临时路由 添加静态路由 ip route add <目的网络> via <下一跳IP> dev <网卡接口名称>例: 给eth0网卡添加一个到达 192.168.2.0/24 网络&#xff0c;下一跳为 192.168.1.254 的路由 ip route add 192.168.2.0/24 via 192.168.1.254 dev eth0…...

网站建设中常见的网站后台开发语言有哪几种,各自优缺点都是什么?

市场上常见的网站后台开发语言有PHP、Python、JavaScript、Ruby、Java和.NET等。这些语言各有其独特的优缺点&#xff0c;适用于不同的开发场景和需求。以下是对这些语言的具体介绍&#xff1a; PHP 优点&#xff1a;PHP是一种广泛用于Web开发的动态脚本语言&#xff0c;特别适…...

【程序大侠传】应用内存缓步攀升,告警如影随形

前序 在武侠编码的江湖中&#xff0c;内存泄漏犹如隐秘杀手&#xff0c;潜伏于应用程序的各个角落&#xff0c;悄无声息地吞噬着系统资源。若不及时发现和解决&#xff0c;必将导致内存枯竭&#xff0c;应用崩溃。 背景&#xff1a;内存泄漏的由来 内存泄漏&#xff0c;乃程序…...

JavaWEB概述

JavaWEB概述 一、什么是JavaWEB 用Java技术解决web互联网领域的技术栈。要学习JavaWEB首先得知道什么是客户端和服务端 客户端&#xff1a;简而言之&#xff0c;这就是使用方&#xff0c;比如我们下载一个软件去使用&#xff0c;里面有很多我们可以使用的功能&#xff0c;那…...

半结构化知识抽取案例

半结构化知识抽取是指从半结构化数据源&#xff08;如HTML、XML、JSON等&#xff09;中提取有用的信息&#xff0c;并将其转换为更易于理解和使用的知识形式。半结构化数据通常包含一些结构化的标记或标签&#xff0c;但不像完全结构化的数据那样严格。 比如抽取如下网页到neo …...

Oracle Truncate和delete的区别

DropTruncatedelete语句类型 DDl &#xff08;数据定义语言 Data Definition Language DDl &#xff08;数据定义语言 Data Definition Language DML&#xff08;数据操作语言 Data Manipulation Language 速度 快 删除整个表 快 一次性删除 慢 逐行删除 回滚不可不可可del…...

应用层协议 --- HTTP

序言 在上一篇文章中&#xff0c;我们在应用层实现了一个非常简单的自定义协议&#xff0c;我们在我们报文的首部添加了报文的长度并且使用特定的符号分割。但是想做一个成熟&#xff0c;完善的协议是不简单的&#xff0c;今天我们就一起看看我们每天都会用到的 HTTP协议 。 UR…...

网卡Network Interface Card

文章目录 网卡&#xff08;Network Interface Card&#xff0c;简称NIC&#xff09;是一种计算机硬件设备&#xff0c;用于将计算机连接到计算机网络&#xff0c;使计算机能够进行数据通信。它是计算机与外部网络&#xff08;如局域网、互联网&#xff09;之间的接口&#xff0…...

9.1 Linux_I/O_基本知识

文件类型 一切I/O皆文件&#xff0c;文件就是存放在磁盘上面的有序数据的集合。 文件类型&#xff1a; 常规文件 r &#xff1a;就是普通文件目录文件 d &#xff1a;就是目录&#xff0c;是一个索引字符设备文件 c &#xff1a;键盘、鼠标块设备文件 b &#xff1a;U盘、磁…...

[Java]一、面向对象核心编程思想

G:\Java\1.JavaSE 1. 继承 1.1 继承的概述 重点内容:1.知道继承的好处2.会使用继承3.知道继承之后成员变量以及成员方法的访问特点4.会方法的重写,以及知道方法重写的使用场景5.会使用this关键字调用当前对象中的成员6.会使用super关键字调用父类中的成员7.会定义抽象方法以…...

科研绘图系列:R语言多个AUC曲线图(multiple AUC curves)

文章目录 介绍加载R包导入数据数据预处理画图输出结果组图系统信息介绍 多个ROC曲线在同一张图上可以直观地展示和比较不同模型或方法的性能。这种图通常被称为ROC曲线图,它通过比较不同模型的ROC曲线下的面积(AUC)大小来比较模型的优劣。AUC值越大,模型的诊断或预测效果越…...

JavaWeb--纯小白笔记06:使用Idea创建Web项目,Servlet生命周期,注解,中文乱码解决

使用Idea创建一个web项目----详细步骤配置&#xff0c;传送门&#xff1a;http://t.csdnimg.cn/RsOs7 src&#xff1a;放class文件 web&#xff1a;放html文件 out&#xff1a;运行过后产生的文件 一创建一个新的web项目(配置好了后)&#xff1a; 在src创建一个文件…...

jQuery——jQuery的2把利器

1、jQuery 核心函数 ① 简称&#xff1a;jQuery 函数&#xff0c;即为 $ 或者 jQuery ② jQuery 库向外直接暴露的是 $ 或者 jQuery ③ 引入 jQuery 库后&#xff0c;直接使用 $ 即可 当函数用&#xff1a;$&#xff08;xxx&#xff09; 当对象用&#xff1a;$.xxx&#x…...

Day29笔记-Python操作pdfPython发送邮件

一、Python操作PDF【了解】 1.pdf 简介 PDF是Portable Document Format的缩写&#xff0c;这类文件通常使用.pdf作为其扩展名。在日常开发工作中&#xff0c;最容易遇到的就是从PDF中读取文本内容以及用已有的内容生成PDF文档这两个任务。 在Python中&#xff0c;可以使用名为P…...

Seata分布式事务实践

理论篇 什么是事务 关于事务我们一定会想到下面这四大特性: 原子性:所有操作要么全都完成&#xff0c;要么全都失败。 一致性: 保证数据库中的完整性约束和声明性约束。 隔离性:对统一资源的操作不会同时发生的。 持久性:对事务完成的操作最终会持久化到数据库中。 理解&…...

数字IC设计\FPGA 职位经典笔试面试整理--基础篇2

1. 卡诺图 逻辑函数表达式可以使用其最小项相加来表示&#xff0c;用所有的最小项可以转换为卡诺图进行逻辑项化简 卡诺图讲解资料1 卡诺图讲解资料2 卡诺图讲解资料3 最小项的定义 一个函数的某个乘积项包含了函数的全部变量&#xff0c;其中每个变量都以原变量或反变量的形…...

(务必收藏)推荐市面上8款AI自动写文献综述的网站

在当前的学术研究和论文写作中&#xff0c;AI技术的应用已经变得越来越普遍。特别是在文献综述这一环节&#xff0c;AI工具能够显著提高效率并减少人工劳动。以下是市面上8款推荐的AI自动写文献综述的网站&#xff1a; 一、千笔-AIPassPaper 是一款备受好评的AI论文写作平台&…...

【python】运算符

学习目标 了解 Python 中常见 算术&#xff08;数学&#xff09;运算符赋值运算符 算术&#xff08;数学&#xff09;运算符 a 是 10&#xff0c;b 是 20 运算符描述实例加两个对象相加 a b 输出结果 30-减得到负数或是一个数减去另一个数 a - b 输出结果 -10*乘两个数相…...

C++深入学习string类成员函数(1):默认与迭代

引言 在 C 编程中&#xff0c;std::string 类是处理字符串的核心工具之一。作为一个动态管理字符数组的类&#xff0c;它不仅提供了丰富的功能&#xff0c;还通过高效的内存管理和操作接口&#xff0c;极大地方便了字符串操作。通过深入探讨 std::string 的各类成员函数&#…...

DownKyi完全指南:三步解锁B站8K视频下载的终极方案

DownKyi完全指南&#xff1a;三步解锁B站8K视频下载的终极方案 【免费下载链接】downkyi 哔哩下载姬downkyi&#xff0c;哔哩哔哩网站视频下载工具&#xff0c;支持批量下载&#xff0c;支持8K、HDR、杜比视界&#xff0c;提供工具箱&#xff08;音视频提取、去水印等&#xff…...

Windows平台QT BLE开发避坑指南:从环境搭建到稳定通信

1. Windows平台QT BLE开发环境搭建 在Windows平台上使用QT进行BLE开发&#xff0c;首先需要确保开发环境正确配置。我遇到过不少开发者因为环境问题卡在第一步&#xff0c;白白浪费好几天时间。这里分享几个关键点&#xff1a; 编译器选择是第一个坑。实测发现必须使用MSVC编译…...

终极CoreCycler教程:简单三步完成CPU稳定性测试与优化

终极CoreCycler教程&#xff1a;简单三步完成CPU稳定性测试与优化 【免费下载链接】corecycler Script to test single core stability, e.g. for PBO & Curve Optimizer on AMD Ryzen or overclocking/undervolting on Intel processors 项目地址: https://gitcode.com/…...

FPGA高速ADC数据采集实战——基于AD9253 LVDS接口与ISERDESE2设计

1. AD9253高速ADC核心特性解析 AD9253这颗14位125MSPS四通道ADC芯片&#xff0c;在通信和医疗成像领域堪称经典。我经手过的多个雷达项目中&#xff0c;它的信噪比表现总能带来惊喜——75.3dBFS的实测数据比手册标称值还要稳定。但真正让工程师们又爱又恨的&#xff0c;是它那个…...

ADXL335模拟传感器读数不稳?手把手教你用Arduino进行软件滤波与校准

ADXL335模拟传感器读数不稳&#xff1f;手把手教你用Arduino进行软件滤波与校准 当你把ADXL335加速度计接入Arduino&#xff0c;兴奋地跑起第一个测试程序时&#xff0c;那些跳动的数字可能很快会浇灭你的热情。原始读数像得了疟疾般颤抖&#xff0c;静止时本该稳定的1g重力加速…...

纯视觉纵深无感管控,落地硐室无人少人化透明值守模式技术白皮书

纯视觉纵深无感管控&#xff0c;落地硐室无人少人化透明值守模式技术白皮书副标题&#xff1a;摒弃井下繁杂传感布设&#xff0c;依靠暗光三维实景重构、深部空间无感感知、盲区跨镜无痕跟踪、身体指纹生物核验&#xff0c;实现井下 24 小时无人值守、全域透明运维前言矿山井下…...

实战指南:用UABEA高效解析Unity资源结构的5个关键要点

实战指南&#xff1a;用UABEA高效解析Unity资源结构的5个关键要点 【免费下载链接】UABEA c# uabe for newer versions of unity 项目地址: https://gitcode.com/gh_mirrors/ua/UABEA 在Unity开发的世界里&#xff0c;资源管理往往是项目优化中最棘手的一环。你是否曾经…...

【ElevenLabs情绪模拟技术白皮书】:基于2,147小时情感语音标注数据集的11类基础情绪迁移模型验证报告

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;ElevenLabs情绪模拟技术白皮书概述 ElevenLabs的情绪模拟技术并非简单调节音高或语速&#xff0c;而是基于多模态情感表征学习&#xff08;Multimodal Affective Representation Learning, MARL&#x…...

LLVM开发实战指南:从入门到精通编译器与程序分析

1. 项目概述&#xff1a;为什么你需要一份LLVM指南&#xff1f;如果你是一名C开发者&#xff0c;或者对编译器、程序分析、代码优化这些底层技术感兴趣&#xff0c;那么“LLVM”这个名字对你来说一定不陌生。它早已不是象牙塔里的学术玩具&#xff0c;而是驱动着从iOS、macOS到…...

【Canvas动画录制实战】从WebM到MP4:MediaRecorder全流程解析与避坑指南

1. Canvas动画录制基础与准备工作 如果你正在开发一个数据可视化项目或者HTML5小游戏&#xff0c;可能会遇到需要将动态内容保存为视频的需求。Canvas动画录制就是解决这个问题的关键技术方案。相比传统的录屏软件&#xff0c;直接通过代码录制能获得更清晰的画质&#xff0c;还…...