做ppt的网站有哪些,唐山制作手机网站,网站建设公司比较好的有哪些,软文投放平台有哪些?目录
双指针算法介绍
练习#xff1a;移动零 双指针算法介绍
双指针算法常见于数组和双向链表的题型
在数组中#xff0c;双指针中的指针代表数组元素的下标#xff0c;而不是真正的指针类型变量
在双向链表中#xff0c;双指针中的指针即为真正意义上的指针#xff…目录
双指针算法介绍
练习移动零 双指针算法介绍
双指针算法常见于数组和双向链表的题型
在数组中双指针中的指针代表数组元素的下标而不是真正的指针类型变量
在双向链表中双指针中的指针即为真正意义上的指针该指针一般是双向链表节点类型的指针
常见的双指针有两种形式
对撞指针从结构的两端开始向中间移动一般存在两种情况 left right代表两个指针指向的时同一个位置left right代表连个指针已经相遇过一次相遇的下一次形成交错快慢指针所谓快慢指针即为一个指针走得快一个指针走得慢 快慢指针一般的思路是慢指针走一步快指针走两步 练习移动零 题目链接283. 移动零 - 力扣LeetCode 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。 思路解析 本题可以采用双指针算法进行解决定义一个指针cur和dest通过这两个指针构建出三个区间分别是 [0, dest] 代表已处理区间中的非0部分[dest1, cur-1] 代表已处理的区间中的0[cur, nums.size()-1] 代表未处理的区间 当每一次的遍历移动数据后形成的区间满足上面三个区间的内容则代表最后结果正确如图所示 此时的区间[0, dest]为不存在的区间所以不存在非0部分而[dest1, cur-1]也为不存在区间[cur, nums.size()-1]区间中有一个未处理数据0 操作的基本思路为 当遇到0时dest不动cur向前走一步当遇到非0时dest向前走一步交换dest的数据和cur的数据交换完毕后cur向前走一步 在上面的区间中[0, dest]区间中有一个数字1[dest1, cur - 1]区间中存在一个数字0[cur, nums.size()-1]区间中均为未处理的数据 在上面的区间中[0, dest]区间中有数字1和3[dest1, cur - 1]区间中存在两个数字0[cur, nums.size()-1]区间中均为未处理的数据 在上面的区间中[0, dest]区间中有数字1、3和12[dest1, cur - 1]区间中存在连个数字0[cur, nums.size()-1]区间不存在此时数组已经遍历交换完成所有的数字零移到了数组的末尾并且没有改变数组非0元素的相对位置 参考代码 /** lc appleetcode.cn id283 langcpp** [283] 移动零*/// lc codestart
class Solution
{
public:void moveZeroes(vectorint nums){// 记录已处理的区间中最后一个非零元素的位置int dest -1;// 遍历数组int cur 0;while (cur nums.size()){// 遇到0不交换if (nums[cur] 0){cur;}else{// 遇到非0元素交换dest下一个位置的数据和cur位置的数据swap(nums[dest], nums[cur]);}}}
};
// lc codeend 或者写成下面的形式 /** lc appleetcode.cn id283 langcpp** [283] 移动零*/// lc codestart
class Solution
{
public:void moveZeroes(vectorint nums){for (int cur 0, dest -1; cur nums.size(); cur){if (nums[cur]){swap(nums[dest], nums[cur]);}}}
};
// lc codeend
