【刷题】双指针入门

news/2024/4/19 14:37:44/文章来源:https://blog.csdn.net/JLX_1/article/details/136515779

在这里插入图片描述

双指针入门

  • 双指针
  • 283.移动零
  • 1089. 复写零
  • 202. 快乐数
  • 11. 盛最多水的容器
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

双指针

双指针是非常经典的算法,包括但不限于前后双指针,快慢双指针,特殊双指针
尤其需要注意的是双指针并不能只局限于指针,数组下标,过程数据都可以成为“指针”。重要的是能够灵活使用双指针的思想,把解题思路捋顺
下面,我们来会会几道双指针的题目:

283.移动零

家人们 !!! 上连接:283.移动零

在这里插入图片描述
通过题目,发现这并不是一到很复杂的题。主要难点在于不改变数组的相对顺序。
这里我们使用前后双指针,逐渐遍历完成操作:

  1. 首先定义两个数组下标 i j
  2. 我们赋予他们不同含义:
    [ 0 ,i)是已经处理过,已经没有零的部分 并按相对顺序排好
    [i , j] 是零的部分
    (j , n) 待处理的部分
  3. 我们控制 j 来进行整个数组的遍历,0 到 i是非零数据。
  4. 遇到 0 ,i j 位置互换即可
    在这里插入图片描述
    来看代码:(类似冒泡排序的过程,把零向后挪动)
class Solution {
public:void moveZeroes(vector<int>& nums) {for(int i = 0,j = 0;j<nums.size();j++)if(nums[j] != 0) swap(nums[j],nums[i++]);}
};

非常简洁的代码。就可以完成我们的操作。来看效果:
在这里插入图片描述
很好!过啦!!!!

1089. 复写零

家人们!!!跟上节奏:1089. 复写零
在这里插入图片描述
这道题与前面的移动零很像,但使用的算法细节不同。
这里需要的也是双指针 i j:

  1. 首先定义两个数组下标 i j
  2. 赋予他们不同含义:
    0 到 i 是处理完的部分
    i 到 j 是 未处理部分
  3. 首先使用 i 遍历整个数组,j 负责调换未处理的数据(将数据后移,空出新的零的位置)
    在这里插入图片描述
    来看代码:
class Solution {
public:void duplicateZeros(vector<int>& arr) {for(int i = 0;i<arr.size();i++){if(arr[i] == 0){for(int j = arr.size() - 1 ; j > i ; j--){arr[j] = arr[j - 1];}++i;}}}
};

运行效果:
在这里插入图片描述

202. 快乐数

家人们!!! 继续干:202. 快乐数

在这里插入图片描述
这道题是比较特殊的一道题,我们来看奥:
首先看测试用例的 1 9 和 2 ;
在这里插入图片描述
可以发现最后都会处于循环:这里可以证明一下为什么都会处于循环:
假设我们最大数为 99999 99999 那对应的数为 810 ,相当于 0 到 9999999999 只有 810 个数与之对应,所以必然会出现循环。
到这里,大家应该也看出这和判断链表是否有环很像,使用快慢指针,慢指针依次进行一步操作,快指针一次两步操作。这里“指针”代指数字。


class Solution {
public://操作函数int getsum(int n ){int sum = 0;while(n){int i = n % 10;sum += i*i;n /= 10;}return sum;}bool isHappy(int n) {//初始化int slow = n;int fast = getsum(n);//进行循环 直到相遇while(slow != fast){slow = getsum(slow);fast = getsum(getsum(fast));}//判断一下即可if(slow == 1) return true;return false;}
};

来看效果:
在这里插入图片描述
很好! 过啦!!!!

11. 盛最多水的容器

家人们,终于到了最后一题: 11. 盛最多水的容器
这道题可谓十分抽象:
在这里插入图片描述
这里使用前后双指针,代我细细到来为什么:
首先我们选取前后这一片段,然后得到一个体积值。
这时我们可以进行一下分析:

  1. 如果移动较大这边的指针,那长必然减小 , 高一定不会增加所以不需移动较高这边
  2. 再来看较小这边,移动后不能确定到底是增加还是减少,所以需要移动进行遍历

根据这两条规矩我们就可以完成操作:来看图解(来自 力扣官方题解)
在这里插入图片描述
这样必然可以得到答案。

class Solution {
public:int maxArea(vector<int>& height) {int i = 0;int j = height.size() - 1;// 记录答案值int ans = 0;while(i != j){//求得新的体积int v = min(height[i],height[j]) * (j - i);//取最大值ans = max(ans,v);// 移动较小的指针if(height[i] < height[j])i++;elsej--;}return ans;}
};

来看效果:
在这里插入图片描述
过啦!!!(还存在改进空间)

经过这四道题目的洗礼,我大概对双指针有了初步印象,接下来我会继续努力!!!

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996326.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++之获取Windows系统信息

目录 1. 操作系统版本 2. 获取CPU信息 3. 获取内存信息 4. 获取硬盘信息 5.获取网络接口信息 6.获取计算机名称、用户名 在C中&#xff0c;你可以使用Windows API函数来获取Windows系统的各种信息。以下是一些常见的API函数和示例代码&#xff0c;用于获取Windows系统信息…

vant van-field 密码输入框小程序里隐藏、显示密码bug总结

老规矩先上效果图: vant 输入框组件 密码的隐藏与显示功能&#xff1a; 注: 用password属性控制密码的显示与隐藏 不要用type属性&#xff0c;type属性在真机上有时会没有效果 1、当然如果只用typepassword 不需要切换显示、隐藏也可以使用。 2、如果用到了密码的显示与…

MES系统是怎么进行数据采集的?

在MES管理系统中&#xff0c;数据采集作为最基础也最为关键的一环&#xff0c;对于实现生产过程的透明化、可控好以及优化生产流程具有重要意义。 mes系统是怎么采集数据的? 一、PLC类数据采集&#xff1a;使用C#或C直接编程访问PLC(不需要花钱买组态软件或第三方软件) 二、…

Java精品项目--第6期基于SpringBoot的茶叶商城的设计分析与实现

项目技术栈 SpringBootMavenMySQLJAVAMybatis-PLusVue.js&#xff08;非前后端分离&#xff09;Element-UI&#xff08;非前后端分离&#xff09;… 表截图 项目截图

VGW在 Windows 平台上局域网就绪的旁路由器程序

在查阅本篇文章之前可以查看下&#xff0c;本人前两年写的关于VGW软件路由器的文章 Linux 平台上面单网卡 TUN/TAP实现局域网其它设备上网_linux 物理网卡与tun同网段-CSDN博客 VGW软件路由器是一个工作IEEE以太网&#xff08;L2&#xff09;链路层的路由器程序&#xff0c;它…

哪个牌子宠物空气净化器好?质量好的宠物空气净化器推荐

即使我们很爱自家的宠物&#xff0c;但我们也无法否认处理房间里飘荡的宠物毛发和皮屑&#xff0c;以及那些令人不快的气味&#xff08;比如地毯上的意外和垃圾桶里的气味&#xff09;的挑战。对于过敏患者来说&#xff0c;这几乎是无法忍受的。寻找有效的方法来减少这些问题对…

利用axios库在Node.js中进行代理请求的实践

前言 随着互联网的蓬勃发展&#xff0c;Web应用程序越来越依赖于从外部服务器获取数据。在这个过程中&#xff0c;我们经常需要通过代理服务器来访问外部资源。本文将介绍如何充分利用axios库&#xff0c;在Node.js中进行代理请求的最佳实践&#xff0c;并通过一个实际案例来展…

【NVCC,CUDA,NVIDIA驱动】装了pytorch,nvcc -V不能用,但能正常使用gpu

这里写目录标题 问题描述问题原理为什么anaconda安装的Pytorch&#xff0c;其能够直接在gpu上运行NVCC是什么&#xff0c;怎么查看装没装 如果没有NVCC文件夹&#xff0c;应该如何安装NVCC&#xff1f;CUDNN&#xff1a;Local Installer for Linux x86_64和Local Installer for…

单例模式及应用场景

如果希望自己的代码更优雅、可维护性更高以及更简洁&#xff0c;往往离不开设计模式这一解决方案。 在JS设计模式中&#xff0c;最核心的思想&#xff1a;封装变化&#xff08;将变与不变分离&#xff0c;确保变化的部分灵活&#xff0c;不变的部分稳定&#xff09;。 那么来…

ssm基于javaEE+springboot校园闲置二手物品拍卖交易平台_ngad7

为提升浏览用户观感及使用体验&#xff0c;本系统要具有易用性和美观性。通过页面的简单提示就可完成操作&#xff0c;校园闲置物品交易平台展示界面应该清楚简洁&#xff0c;使用户通过美观的前台页面能快速定位想要浏览的校园闲置物品交易平台信息。后台界面也应简约&#xf…

YOLOv5创新改进:SPPF创新涨点篇 | SPPELAN:SPP创新结合ELAN ,效果优于SPP、SPPF| YOLOv9

💡💡💡本文独家改进:新颖SPPF创新涨点改进,SPP创新结合ELAN,来自于YOLOv9,助力YOLOv5,将SPPELAN代替原始的SPPF 💡💡💡在多个私有数据集和公开数据集VisDrone2019、PASCAL VOC实现涨点 收录 YOLOv5原创自研 https://blog.csdn.net/m0_63774211/category_12…

基于ACM32 MCU的两轮车充电桩方案,打造高效安全的电池管理

随着城市化进程的加快、人们生活水平的提高和节能环保理念的普及&#xff0c;越来越多的人选择了电动车作为代步工具&#xff0c;而两轮电动车的出行半径较短&#xff0c;需要频繁充电&#xff0c;因此在城市中设置两轮车充电桩就非常有必要了。城市中的充电桩不仅能解决两轮车…

Linux 之三:CentOS7 目录结构 和 日期及时区设置

Linux 目录 以下是对这些目录的解释&#xff1a; /bin&#xff1a;bin是Binary的缩写, 这个目录存放着最经常使用的命令。/boot&#xff1a; 这里存放的是启动Linux时使用的一些核心文件&#xff0c;包括一些连接文件以及镜像文件。/dev &#xff1a; dev是Device(设备)的缩写…

深度学习1:神经网络原理与算法详解

一、神经网络&#xff1a;模拟大脑的信息处理机制 神经网络&#xff0c;作为深度学习的基础&#xff0c;其灵感来源于人脑神经元之间的复杂连接和信号传递方式。在神经网络中&#xff0c;每个神经元都是一个计算单元&#xff0c;它接收来自其他神经元的输入信号&#xff0c;并…

RabbitMQ 交换器

RabbitMQ 交换器 官方例子 http://www.rabbitmq.com/getstarted.html direct 如上图所示&#xff0c;两个队列绑定到了direct交换器上&#xff0c;第一个队列绑定的 binding key 为 orange &#xff0c;第二个队列有两个绑定&#xff0c;分别是 black 和 green 。 如上图所示…

Three.js--》探寻Cannon.js构建震撼的3D物理交互体验(二)

我们用three.js可以绘制出各种酷炫的画面&#xff0c;但是当我们想要一个更加真实的物理效果的话&#xff0c;这个时候我们就需要一个物理的库&#xff0c;接下来我们就讲解一下今天要学习的canon&#xff0c;它可以给我们提供一个更加真实的物理效果&#xff0c;像物体的张力、…

Django学习记录08——图表及文件上传案例

1.图表Echarts的应用 Apache ECharts 1.1 使用方法 引用echarts.js即可到官方文档中查询使用 1.2 常用图标的使用 图表展示页面的部署&#xff08;主要展示折线图、柱状图、饼图&#xff09; {% block content %}<div class"container"><div class&qu…

Java单测Mock升级实践

Java单测Mock升级实践 一、背景 众所周知&#xff0c;单元测试是改善代码质量&#xff0c;提升研发交付品质的手段之一&#xff0c;能否写出好的单元测试用例&#xff0c;也是衡量我们研发专业性的标准之一。所以&#xff0c;想要成为一名合格的研发&#xff0c;就应该要有编…

Android Studio中debug功能详解

本文为大家分享了Android Studio debug功能的具体使用方法&#xff0c;供大家参考&#xff0c;具体内容如下 运行debug模式 \1. 进入debug – 点击图中红色圆圈圈起的左边绿色按钮&#xff0c;运行app的debug模式&#xff0c;快捷键ShiftF9 – 点击图中红色圆圈圈起的右边按…

【异常处理】Vue报错 Component template should contain exactly one root element.

问题描述 启动VUE项目后控制台报错&#xff1a; Component template should contain exactly one root element. If you are using v-if on multiple elements, use v-else-if to chain them instead.翻译为&#xff1a;组件模板应该只包含一个根元素 查看vue代码&#xff0…