1. 183. 移动零
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
题目链接
. - 力扣（LeetCode）
画图 和 文字 分析
这种题，它有一种很明显的划分区间的行为（划分成 非0 和 0 的区间）
这里我们用双指针划分区域
非0：[0,dest]
0 : [dest + 1,cur - 1]
未处理 ：[cur , n - 1]
我们让 dest 一直指向最后一个 非0 的位置
cur遍历一遍数组，一直指向未处理区域的第一个位置
现在问题只有两个：
dest , cur 最开始指向哪 ？如果移动保证区域划分不会出问题 ?
对于第一个问题：
cur 因为要遍历一遍数组，所以它从 0 下标开始，而 dest开始没有区间，就从 -1 下标开始
对于第二个问题：
cur 在遍历数组的时候只会遇到两者情况，要么碰到 0 ,要么碰到 非0
如果碰到 0：cur++
如果碰到 非0 ：先 dest++ (此时dest所指的位置一定是 0 或者未处理的第一个位置)，再将此时 cur 和 dest 所指向的位置交换（保证了顺序不变），最后 cur++ (cur 又指向未处理区域)
代码
class Solution {
public:
void moveZeroes(vector
{
int dest = -1;
int cur = 0;
while(cur < nums.size())
{
if(nums[cur] == 0)
{
;
}
else
{
dest++;
swap(nums[dest],nums[cur]);
}
cur++;
}
}
};
2. 1089 复写零
题目
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
题目链接
. - 力扣（LeetCode）
画图 和 文字 分析
这道题考虑到时间复杂度和空间复杂度的情况下，我们决定用双指针来做
现在就是考虑两个指针的位置关系，首先，思考一下，如果两个指针都从下标 0 开始的话，很可能会发生把 0 把没有处理过的数据覆盖住了，所以换一种思路，两个指针从后开始覆盖
举例： 1 0 2 3 0 4 5 0
我们用 dest 指向最后一个要复写的位置
那么怎么找到最后一个要复写的位置呢？
我们可以知道，另一个指针cur 遇到 非0 跨一步，遇到 0 跨两步，而 dest 一直在跨一步，当大于等于总数组的长度时，dest 指向最后一个位置，这里我们让 cur 从下标为 -1 位置开始，dest 从下标为 0 的位置开始
如果我们要倒这覆盖，就按指针就从如图所示的位置开始
注意：
但是这里会碰到一种情况，cur 指针最后可能走两步，直接到下标为 n 的位置了，在倒退的时候，这种情况一定要单独处理，防止发生越界访问现象因为 dest 开始从 -1 开始找，类似是 int，而 vector 的size() 是 size_t 类型的，比较大小时，一定要记得发生类型转换
代码
class Solution {
public:
void duplicateZeros(vector
{
int cur = 0;
int dest = -1;
while(dest < (int)(arr.size() - 1))
{
if(arr[cur] != 0)
{
dest++;
}
else
{
dest += 2;
}
if(dest >= arr.size() - 1)
{
break;
}
cur++;
}
while(dest >= 0)
{
if(arr[cur] == 0)
{
if(dest > arr.size() - 1)
{
dest--;
arr[dest] = 0;
}
else
{
arr[dest--] = 0;
arr[dest] = 0;
}
}
else
{
swap(arr[cur],arr[dest]);
}
dest--;
cur--;
}
}
};
精彩文章
发表评论