当前位置: 首页 > 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数据库驱动的问题以…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...