数据结构和算法笔记3:双指针法(快慢指针)

news/2024/11/15 5:41:58/

双指针法(快慢指针法)在数组、字符串和链表的操作中是非常常见的,这里结合力扣上的题进行可一下梳理,主要的思路是我们要明确快指针指的是什么,慢指针指的是什么。

1. 移除元素类问题

27. 移除元素

要我们移除目标元素,返回移动后元素的新长度。

  • 快指针:原数组的索引,这里是fast
  • 慢指针:移除后数组的索引,这里是slow

我们循环时一定是快指针遍历整个数组,然后慢指针根据条件移动,如果发现快指针不等于指定的目标元素val:nums[fast] != val,我们对当前的nums[slow]赋值为nums[fast],让后slow自增。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0; fast < nums.size(); ++fast){if (nums[fast] != val)nums[slow++] = nums[fast];}return slow;}
};

26. 删除有序数组中的重复项

要我们移除数组重复的元素,返回移动后元素的新长度。

  • 快指针:原数组的索引,这里是fast
  • 慢指针:移除后数组的索引,这里是slow

为了看是否有重复项我们一定是比较nums[fast]nums[fast - 1]看是否相等,如果不相等,说明不重复,我们可以把当前的nums[fast]赋值给nums[slow],并且slow往前移动一位,为了fast-1不越界,fast的遍历应该从1开始,也是遍历整个数组,既然从1开始,slow的初始值也应该是1,因为第一个元素我们认为不需要删除。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1;for (int fast = 1; fast < nums.size(); ++fast){if (nums[fast] != nums[fast - 1])nums[slow++] = nums[fast];}return slow;}
};

283.移动零

要我们把零全部移动到最后,一种直观的思路是使用移除元素的方法,把零移除完,然后从这时的slow开始把数组后面的值都赋值为0:

  • 快指针:原数组的索引,这里是fast
  • 慢指针:移除后数组的索引,这里是slow

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for (int fast = 0; fast < nums.size(); fast++){if (nums[fast] != 0)nums[slow++] = nums[fast];}for (; slow < nums.size(); slow++){nums[slow] = 0;}}
};

但我们要移动0,其实也可以直接进行位置的调换,每当发现一个nums[fast]的值不为0,我们就调换当前nums[slow]nums[fast]的值(而不是把nums[fast]直接幅值给nums[slow]),然后slow自增:

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for (int fast = 0; fast < nums.size(); ++fast){if (nums[fast] != 0){swap(nums[slow++], nums[fast]);}}}
};

增加元素类题目

1089. 复写零

要我们对输入的数组就地进行上述修改,将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

  • 快指针:原数组的索引,这里是i
  • 慢指针:复写零新数组的索引,这里是j

按照题目要求如果原数组的元素arr[i]碰到0,新数组的索引arr[j]要额外走一步,直到新数组索引越界走出整个循环.

这时候要注意的是原数组多走了一步,我们需要对原数组和新数组进行一步回退。

然后往回赋值(逆序遍历),循环继续进行的条件是原数组的索引i大于等于0,如果新数组索引j没有越界,就把arr[i]的值赋值给arr[j],如果arr[i]碰到0,我们要判断当前索引j前面能不能再赋值(有没有越界),如果可以就把j自减,并且arr[j]赋值为0,接着索引ij继续自减回退,直到循环结束条件达到,数组也就成功复写了零:

class Solution {
public:void duplicateZeros(vector<int>& arr) {int len = arr.size(); int i = 0;int j = 0;while (j < len){if (arr[i] == 0)j++;i++;j++;}i--;j--;while (i >= 0){if (j < len)arr[j] = arr[i];if (arr[i] == 0 && j - 1 >= 0){j--;arr[j] = 0;}i--;j--;}}
};

http://www.ppmy.cn/news/1279702.html

相关文章

【量化金融】证券投资学

韭菜的自我修养 第一章&#xff1a; 基本框架和概念1.1 大盘底部形成的技术条件1.2 牛市与熊市1.3 交易系统1.3.1 树懒型交易系统1.3.2 止损止损的4个技术 第二章&#xff1a;证券家族4兄弟2.1 债券&#xff08;1&#xff09;债券&#xff0c;是伟大的创新&#xff08;2&#x…

uniapp怎么动态渲染导航栏的title?

直接在接口请求里面写入以下&#xff1a; 自己要什么参数就写什么参数 本人仅供参考&#xff1a; this.name res.data.data[i].name; console.log(名字, res.data.data[i].name); uni.setNavigationBarTitle({title: this.name}) 效果&#xff1a;

kubernetes集群 应用实践 kafka部署

kubernetes集群 应用实践 kafka部署 零.1、环境说明 零.2、kafka架构说明 zookeeper在kafka集群中的作用 一、Broker注册 二、Topic注册 三、Topic Partition选主 四、生产者负载均衡 五、消费者负载均衡 一、持久化存储资源准备 1.1 创建共享目录 [rootnfsserver ~]# mkdir -…

模式识别与机器学习(十):梯度提升树

1.原理 提升方法实际采用加法模型&#xff08;即基函数的线性组合&#xff09;与前向分步算法。以决策树为基函数的提升方法称为提升树&#xff08;boosting tree&#xff09;。对分类问题决策树是二叉分类树&#xff0c;对回归问题决策树是二叉回归树。提升树模型可以表示为决…

爬虫工作量由小到大的思维转变---<第二十三章 Scrapy开始很快,越来越慢(医病篇)>

诊断篇https://blog.csdn.net/m0_56758840/article/details/135170994?ops_request_misc%257B%2522request%255Fid%2522%253A%2522170333243316800180644102%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id1703332433168001806441…

pycharm修改项目文件夹名称

目录 1 修改项目文件夹名称 2 修改代码中的项目名称 1 修改项目文件夹名称 选中项目文件夹&#xff0c;右键&#xff0c;选择refactor-rename。 选择rename project&#xff1a; 然后输入新的项目名称。 此时进入资源管理器&#xff0c;修改项目文件夹的名字&#xff0c;完成…

说说对React refs 的理解?应用场景?

先了解&#xff0c;是什么&#xff1f; React 中的 Refs提供了一种方式&#xff0c;允许我们访问 DOM节点或在 render方法中创建的 React元素。 本质为ReactDOM.render()返回的组件实例&#xff0c;如果是渲染组件则返回的是组件实例&#xff0c;如果渲染dom则返回的是具体的do…

十五、W5100S/W5500+RP2040之MicroPython开发<Modbus示例>

文章目录 1. 前言2. 相关网络信息2.1 简介2.2 指令构成2.3 优点2.4 应用 3. WIZnet以太网芯片4. Modbus TCP通信示例讲解以及使用4.1 程序流程图4.2 测试准备4.3 连接方式4.4 相关代码4.5 烧录验证 5. 注意事项6. 相关链接 1. 前言 在这个智能硬件和物联网时代&#xff0c;Micr…