网站建设哪儿好,营销案例分析,app网站与普通网站的区别,现货交易十大平台#x1f525;个人主页#xff1a;草莓熊Lotso #x1f3ac;作者简介#xff1a;C研发方向学习者 #x1f4d6;个人专栏#xff1a;《C知识分享》《Linux 入门到实践#xff1a;零基础也能懂》《数据结构与算法》《测试开发实战指南》《算法题闯关指南》 ⭐️人生格言个人主页草莓熊Lotso 作者简介C研发方向学习者 个人专栏《C知识分享》《Linux 入门到实践零基础也能懂》《数据结构与算法》《测试开发实战指南》《算法题闯关指南》 ⭐️人生格言生活是默默的坚持毅力是永久的享受。 前言聚焦算法题实战系统讲解三大核心板块优选算法剖析动态规划、二分法等高效策略学会寻找“最优解”。 递归与回溯掌握问题分解与状态回退攻克组合、排列等难题。 贪心算法理解“局部最优”到“全局最优”的思路解决区间调度等问题 内容以题带点讲解思路与代码实现帮助大家快速提升代码能力 目录 双指针算法介绍
对撞指针
快慢指针
01.移动零
题目链接
题目描述
题目示例
解法(快排的思想数组划分区间-数组分两块)
算法思路
算法流程
C代码演示
算法总结笔记展示
02.复写零
题目链接
题目描述
题目示例
解法原地复写-双指针
算法思路
算法流程
C代码演示
算法总结笔记展示 双指针算法介绍
常见的双指针有两种形式一种对撞指针一种是左右指针。
对撞指针
一般用于顺序结构中也称左右指针。
对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼近。对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结构直接跳出循环也就是leftright两个指针指向同一个位置leftright两个指针错开
快慢指针
又称龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。
快慢指针的实现方法有很多种最常用的一种就是
在一次循环中每次让慢的指针向后移动一位而快的指针往后移动两位实现一快一慢 01.移动零
【数组分两块】是非常常见的一种题型主要就是根据一种划分方式将数组的内容分成左右两部分。这种类型的题一般就是使用【双指针】来解决。
题目链接 283. 移动零 - 力扣LeetCode 题目描述 题目示例 解法(快排的思想数组划分区间-数组分两块)
算法思路
在本题中我们可以用一个 cur 指针来扫描整个数组另一个 dest 指针用来记录非零序列的最后一个位置根据 cur 在扫描的过程中遇到的不同情况分类处理实现数组的划分。在 cur 遍历期间使【0dest】的元素全部都是非零元素【dest1cur-1】的元素全是零
算法流程
1.初始化 cur0用来遍历数组dest-1指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置因此初始化为 -1
2.cur 依次往后遍历每个元素遍历到的元素会有下面两种情况 2.1遇到的元素是 0 cur 直接 。因为我们的目标是让【dest1cur-1】内的元素全都是零因此当 cur 遇到 0 的时候直接 ,就可以让 0 在 cur-1 的位置上从而在【dest1cur-1】内 2.2遇到的元素不是 0 dest并且交换 cur 位置和 dest 位置的元素之后让 cur扫描下一个元素。
因为 dest 指向的位置是非零元素区间的最后一个位置如果扫描到一个新的非零元素那么他的位置应该在 dest1 的位置上因此 dest 先自增 1dest 之后指向的元素就是 0 元素因为非零元素区间末尾的后一个元素就是 0 因此可以交换到 cur 所处的位置上实现 【0dest】的元素全部都是非零元素【dest1cur-1】的元素全是零。
C代码演示
class Solution {
public:void moveZeroes(vectorint nums) {int cur0,dest-1;while(curnums.size()){if(nums[cur]){swap(nums[dest],nums[cur]);}cur;}}
};
算法总结笔记展示 这里用到的方法是我们学习 【快排算法】的时候【数据划分】过程的重要一步。如果将快排算法拆解的话这一小段代码就是实现快排算法的【核心步骤】。
笔记的字有点丑大家见谅 02.复写零
题目链接 1089. 复写零 - 力扣LeetCode 题目描述 题目示例 解法原地复写-双指针
算法思路
如果【从前往后】进行原地复写操作的话由于 0 的出现会复写两次导致没有复写的数【被覆盖掉】。因此我们选择【从后往前】的复写策略。但是 【从后往前】复写的时候我们需要找到 【最后一个复写的数】因此我们的大体流程分两步1.先找到最后一个复写的数2.然后从后往前进行复写操作
算法流程
1.初始化两个指针 cur0dest0
2.找到最后一个复写的数
判断 cur 位置的元素1如果是 0 的话dest 往后移动两位2否则dest 往后移动一位判断 dest 这时候是否已经到结束位置如果结束就终止循环如果没有结束cur继续判断。
3.判断 dest 是否越界到 n 的位置
如果越界执行下面三步
n-1 位置的值修改成 0 cur 向前移动一步cur--dest 向前移动两步dest - 2)
4.从 cur 位置开始往前遍历原数组依次还原出复写后的结果数组
4.1 判断 cur 位置的值
如果是 0 dest 以及 dest-1 位置修改成 0 dest-2如果非零dest 位置修改成 0 dest - 1
4.2 cur--复写下一个位置。
C代码演示
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1;int narr.size();//找到最后一个复写的数while(curn){if(arr[cur])dest;else dest2;if(destn-1) break;cur;}if(destn){arr[n-1]0;dest-2;cur--;}while(cur0){if(arr[cur]){arr[dest--]arr[cur];}else{arr[dest--]0;arr[dest--]0;}cur--;}}
};
算法总结笔记展示
笔记的字有点丑大家见谅 往期回顾
《吃透 C 类和对象中拷贝构造函数与赋值运算符重载深度解析》
《吃透 C 类和对象中const 成员函数与取地址运算符重载解析》
结语本篇博客系统讲解了双指针算法在数组处理中的应用重点分析了移动零和复写零两道典型题目。针对移动零问题采用快排思想实现数组划分复写零问题则通过前后双指针策略完成原地操作。如果文章对你有帮助的话欢迎评论点赞收藏加关注感谢大家的支持。
