做视频课程网站,试用网站要怎么做,廊坊360推广方案,网络推广方案的制定流程目录
双指针算法讲解
移动零 双指针算法讲解
常见的双指针有两种形式#xff0c;一种是对撞指针#xff0c;一种是快慢指针。
对撞指针#xff1a;一般用于顺序结构中#xff0c;也称左右指针。
对撞指针从两端向中间移动。一个指针从最左端开始#xff0c;另一个从最…目录
双指针算法讲解
移动零 双指针算法讲解
常见的双指针有两种形式一种是对撞指针一种是快慢指针。
对撞指针一般用于顺序结构中也称左右指针。
对撞指针从两端向中间移动。一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼近。对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 left right 两个指针指向同一个位置left right 两个指针错开
快慢指针又称龟兔赛跑赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种最常用的一种就是
·在一次循环中每次让慢的指针向移动一位而快的指针往后移动两位实现一快一慢。
移动零
「数组分两块」是非常常见的一种题型主要就是根据一种划分方式将数组的内容分成左右两部分。这种类型的题一般就是使用「双指针」来解决
题目链接283.移动零 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。 解法快排的思想数组划分区间-数组分两块 算法思路
在本题中我们可以用一个 cur 指针来扫描整个数组另一个 dest 指针用来记录非零数序列的最后一个位置。根据cur在扫描的过程中遇到不同的情况分类处理实现数组的划分。以下是我们的目标 我们如何实现这种呢 1.cur 指针的目的是遍历数组那么cur指针一定是在数组首元素位置 2.既然cur指针在首元素为了实现数组被划分三个阶段那么des只能在cur之前的位置也就是 -1 处。 3.cur指针开始向后移动为了实现【des1 cur-1】中间是0那么控制cur的条件就是cur遇到0就跳过也就是继续往前走。如果遇到了不是0那么就将des1进行交换交换后cur当前位置就变成了0继续加加直到遍历完数组。 因此可以简化思想 cur 从前往后遍历过程中 1.遇到0元素cur 2.遇到非0元素1️⃣swap(des;cur) 2️⃣ cur void moveZeroes(vectorint nums) {int cur 0;int des -1;while(cur nums.size()){//cur是0就跳过if(nums[cur] 0) cur;else{//不是0就交换在swap(nums[des],nums[cur]);cur;}}
}也可以用for循环
void moveZeroes(vectorint nums) {for(int cur 0,des -1;cur nums.size();cur){if(nums[cur])//处理非0元素{swap(nums[des],nums[cur]);}}}
