当前位置: 首页 > 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 的各类成员函数&#…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

python读取SQLite表个并生成pdf文件

代码用于创建含50列的SQLite数据库并插入500行随机浮点数据&#xff0c;随后读取数据&#xff0c;通过ReportLab生成横向PDF表格&#xff0c;包含格式化&#xff08;两位小数&#xff09;及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...