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

day1·算法-双指针

在这里插入图片描述
今天是第一天,GUNDOM带你学算法,跟上我的节奏吗,一起闪击蓝桥杯!
在这里插入图片描述

正文展开,今天先上点小菜供大家想用,如有错误或者建议直接放评论区,我会一个一个仔细查看的哦。

双方指针问题一般是在数组中定义两个指针变量,通过对这两个指针变量进行操作来达到解决问题的目的。
用一道最显而易见的题目来解释。
移动0
在这里插入图片描述
 将所有的0都移动到数组的最后,我们可以遍历查找不是0的元素,然后将他们从下标位置为i=0位置依次放在数组中,因为可能有0元素的存在,所以在循环之后非零元素的值不会补齐数组中的所有元素,就像上边那个例子一样,我们要将nums.size()-i的部分置为0,这道题就算是结束了。
C++代码如下

void moveZeroes(vector<int>& nums) {//解法1int k=0;for(auto i:nums){if(i!=0){nums[k]=i;k++;}i++;}cout<<k<<endl;for(int j=k;j<nums.size();j++){nums[j]=0;}//写法二:int pre,tail;for(pre=0,tail=0;tail<nums.size();tail++){if(nums[tail]!=0){swap(nums[pre++],nums[tail]);}}}

复写零
在这里插入图片描述
 如果数组中有零元素,就将该0复写,后边的元素顺序不变,可以知道,如果有0元素,就一定会有元素越界被丢弃。
这道题目思路很容易想到,但是还是有一点坑点。
思路如下
 首先要找到最终复写的位置,然后从这个位置依次向前复写
在这里插入图片描述
在找到要求数组的最后一位后,根据值向前遍历。
 假设找到的位置为head,根据head位置的值来确定数组从后往前写什么,初始写入的位置一定是arr.size()-1。如果tail位置是0,就可以往前确定两个位置都是零,如果不是零,就在当前tail位置写入head位置的值,然后更新head和tail的数值。
代码如下

void duplicateZeros(vector<int>& arr) {int head = 0;int tail = 0;while (tail < arr.size()){if (arr[head] == 0){tail ++;}tail++;head++;}head--;cout << head << endl;tail = arr.size() - 1;while (tail>0){if (arr[head] == 0){arr[tail--] = 0;arr[tail--] = 0;}else{arr[tail--] = arr[head];}head--;}for (auto i : arr){cout << i;}
}

动图演示如下
在这里插入图片描述
但是写完后提交……
在这里插入图片描述
推演一遍我们就会发现,head落在了不对的地方,所以才会造成一连串错误。
在这里插入图片描述
 如果tail位置大于size,那就直接将数组末尾元素置0,将tail和head向前移动,重新锁定位置。

if (tail > arr.size()){arr[arr.size() - 1] = 0;tail =arr.size()-2;head=head-1;}else{tail = arr.size() - 1;}

顺利过关。
在这里插入图片描述
盛水最多的容器在这里插入图片描述
 以x轴为桶宽,以y轴为木桶高度,我们知道水桶效应,判断木桶能装多少水是取决于短板的。
 分析题目,如果用暴力求解的方法,依次算出不同变量下木桶能盛多少水,然后就可以知道最大的装水量。
使用双指针算法可以遍历更少的次数求解出答案。
在这里插入图片描述
 包含第一个轴的最大盛水量就求出来了,保存该值,以第二个轴和第一个轴为木桶边界(以下称head,tail)此时两轴中低的是7,移动前边的轴宽度会减小,且高度最大还是7,所以又求出一个最大值49。
 移动后边的轴即tail,以倒数第二个轴即3的高度继续以同样的形式继续求最大值,可以得到18,移动前边的轴,即head,继续判断。
可以看出这种方式只遍历一遍,就可以找到最大的面积。
代码如下

class Solution {
public:
int maxnum(int a,int b)
{return a>b?a:b;
}
int minnum(int a,int b)
{return a<b?a:b;
}int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int width=right;int mul=0;int ret=0;while(left!=right){int length=minnum(height[left],height[right]);ret=length*width;if(ret>mul){mul=ret;}if(height[left]<height[right]){left++;}else{right--;}width--;}return mul;}   
};

总结:
 双指针的题目只需要有清晰的思路,要清楚指针的位置,把握好结束条件,双指针的思路上边的题目玩的很简单,最后一道题要善于观察分析,就可以写出更加高效的方法。

相关文章:

day1·算法-双指针

今天是第一天&#xff0c;GUNDOM带你学算法&#xff0c;跟上我的节奏吗&#xff0c;一起闪击蓝桥杯&#xff01; 正文展开&#xff0c;今天先上点小菜供大家想用&#xff0c;如有错误或者建议直接放评论区&#xff0c;我会一个一个仔细查看的哦。 双方指针问题一般是在数组中…...

在vue中,切换页面之后如何关闭定时器

在vue中&#xff0c;使用了element-ui的框架&#xff0c;点击左侧切换内部页面。 有些页面使用了定时器&#xff0c;在其换到其他页面的时候&#xff0c;希望能够关闭这些定期请求和复杂操作。 那么&#xff0c;切换页面之后如何关闭定时器&#xff1f;vue的创建流程中没找到能…...

观测云产品更新 | 日志、场景仪表板、监控器等

观测云更新 用户访问监测 &#xff08;RUM &#xff09; 公网 Dataway 支持 ip 转换成地理位置信息。 日志 > 查看器详情页 1、新增 BPF 网络日志采集及日志详情页&#xff0c;支持 Json 格式转化&#xff1b; 2、上述 1 中的日志详情页中新增可读的展示模式&#xff0c…...

【JupyterLab】在 conda 虚拟环境中 JupyterLab 的安装与使用

【JupyterLab】在 conda 虚拟环境中 JupyterLab 的安装与使用 1 JupyterLab 介绍2 安装2.1 Jupyter Kernel 与 conda 虚拟环境 3 使用3.1 安装中文语言包(Optional)3.2 启动3.3 常用快捷键3.3.1 命令模式下 3.4 远程访问个人计算机3.4.1 局域网下 1 JupyterLab 介绍 官方文档: …...

HTML--JavaScript--引入方式

啊哈~~~基础三剑看到第三剑&#xff0c;JavaScript HTML用于控制网页结构 CSS用于控制网页的外观 JavaScript用于控制网页的行为 JavaScript引入方式 引入的三种方式&#xff1a; 外部JavaScript 内部JavaScript 元素事件JavaScript 引入外部JavaScript 一般情况下网页最好…...

第28关 k8s监控实战之Prometheus(七)

大家好&#xff0c;我是博哥爱运维。 今天继续Prometheus的课程&#xff0c;在之前的几节课里面&#xff0c;我带大家认识并部署了prometheus服务&#xff0c;并将一些服务做好了监控&#xff0c;同时通过grafana展示监控数据图表出来。对于怎么使用promql语法&#xff0c;也教…...

SSC | Blue Prism报告:2024年智能自动化(IA)7大趋势预测

近日&#xff0c;RPA行业领导者SS&C | Blue Prism发布《2024智能自动化&#xff08;IA&#xff09;趋势与预测》报告。报告中提到&#xff0c;智能自动化&#xff08;IA&#xff09;与流程管理的有效融合&#xff0c;是实现数字化转型成功的核心。采用业务流程管理&#xf…...

el-tree定义左边箭头,包括下级出现连线

效果图&#xff1a; 代码&#xff1a; <template><div class"agency-wrap"><el-treeclass"filter-tree":data"detailList":props"defaultProps"default-expand-allnode-click"onClickNode":filter-node-me…...

C++ 多线程顺序打印

打印要求&#xff1a; 三个打印线程顺序进行。 线程要求如下&#xff1a; 线程A&#xff1a;打印A 线程B&#xff1a;打印B 线程C&#xff1a;打印C 打印结果&#xff1a; A B C A B C A B C A B C A B C 法一&#xff1a;需要锁和共享变量 #include <iostream>…...

x-cmd pkg | duf - df 命令的现代化替代品

目录 简介用户首次快速实验指南技术特点竞品和相关作品进一步探索 简介 Duf &#xff08;Disk Usage/Free Utility&#xff09;是一个磁盘分析工具。其直观的输出和多样化的自定义选项&#xff0c;帮助用户更好地管理和优化存储资源。 用户首次快速实验指南 使用 x duf 即可自…...

202406读书笔记|《沉睡的线条世界》——翻山越岭,只为与你分享点滴的快乐

《沉睡的线条世界》登登登Dn绘著&#xff0c;简简单单的小画&#xff0c;简简单单的线条&#xff0c;简简单单的语言&#xff0c;温馨又有一点暖心。 怎样的你都好&#xff0c;做最真实的自己。 部分节选如下&#xff1a; 愿你我永远有热情&#xff0c;永远能为生活的每一个小惊…...

[论文阅读]4DRadarSLAM: A 4D Imaging Radar SLAM System for Large-scale Environments

目录 1.摘要和引言&#xff1a; 2. 系统框架&#xff1a; 2.1 前端&#xff1a; 2.2 回环检测&#xff1a; 2.3 后端&#xff1a; 3.实验和分析&#xff1a; 4.结论 1.摘要和引言&#xff1a; 这篇论文介绍了一种名为“4DRadarSLAM”的新型4D成像雷达SLAM系统&#xff0…...

Python: vars()详细解释

vars() 是一个内置函数&#xff0c;用于返回一个对象的 __dict__ 属性。它接受一个对象作为参数&#xff0c;如果省略参数&#xff0c;它返回当前局部作用域的字典。 具体而言&#xff0c;vars() 的行为取决于参数的类型&#xff1a; 1. 没有参数&#xff1a; 如果没有提供参…...

2024年1月15日Arxiv最热论文推荐:斯坦福LLM精准微调新框架、GPT不愿承认回答错误、速度快15倍的3D全景分割新突破

本文整理了今日发表在ArXiv上的AI论文中最热门的TOP5。 论文解读、论文热度排序、论文标签、中文标题、推荐理由和论文摘要均由赛博马良平台上的智能体 「AI论文解读达人」提供。 如需查看其他热门论文&#xff0c;欢迎移步赛博马良 ^_^ TOP1 APAR: LLMs Can Do Auto-Paral…...

1.5 面试经典150题 - 轮转数组

轮转数组 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 注意&#xff1a;本题需要原地操作 class Solution(object):def rotate(self, nums, k):""":type nums: List[int]:type k: int:rtype: None Do not…...

Linux的基础命令学习

pwd - 显示当前工作目录的路径 cd - 切换工作目录&#xff0c;ls - 列出当前目录的文件和子目录 rm - 删除文件或目录 mkdir - 创建新目录 rm - 删除目录 nano/vi - 编辑文本文件&#xff0c;按Enter键进入 之后按i键就可以进入写入模式 之后输入文字以后按Esc键与:q就不保…...

个人数据备份方案分享(源自一次悲惨经历)

文章目录 1 起源2 备份架构2.1 生活照片2.2 生活录音2.3 微信文件2.4 工作文件2.5 笔记、影视音乐、书籍 3 使用工具介绍3.1 小米云服务3.2 中国移动云盘3.3 小米移动硬盘&#xff08;1T&#xff09;3.4 FreeFileSync 4 总结 1 起源 本文的灵感源于我个人的一次不幸遭遇&#…...

SpringBoot教程(八) | SpringBoot统一结果封装

SpringBoot教程(八) | SpringBoot统一结果封装 经过了前面几篇文章&#xff0c;SpringBoot中MVC相关的配置其实都已经差不多了&#xff0c;接下来就可以完全进入接口开发阶段了。前面我们写过几个接口&#xff0c;虽然都加了RestController注解&#xff0c;相当于统一了我们的…...

Ubuntu 22.04 安装Fail2Ban

Fail2Ban是一种用来防止暴力破解的工具&#xff0c;一般要和iptables配合使用。其原理是读取系统日志&#xff0c;并通过正则表达式匹配&#xff0c;监控IP在一段时间内的登录尝试、身份验证失败日志等并进行计数。超过阈值则进行IP封禁&#xff0c;过一段时间后再解封。 总的…...

Ubuntu 22.04 编译安装 Qt mysql驱动

参考自 Ubuntu20.04.3 QT5.15.2 MySQL驱动编译 Ubuntu 18.04 编译安装 Qt mysql驱动 下边这篇博客不是主要参考的, 但是似乎解决了我的难题(找不到 libmysqlclient.so) ubuntu18.04.2 LTS 系统关于Qt5.12.3 无法加载mysql驱动&#xff0c;需要重新编译MYSQL数据库驱动的问题以…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...