【鼠鼠优选算法-双指针】001：移动零 & 002：复写零
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
在学习了这么多基础知识之后，我们就从今天开始操练一下我们的基本技能吧，先来两道简单的题目试试手：
1.移动零：题目链接~~~
2.复写零：复写零
那我们就一题一题来讲讲吧~~~
一、移动零
题目描述:
看到题目,这道题是想让我们将一个数组中的所有0移动到数组的末尾.
题目意思明了,但是我们该怎么操作呢?
在这道题中我们第一个想到的就是重新创建新的数组,将数值不为0的元素移动到新的数组中,但是题目明确要求说了,只能再原地进操作,我们该怎么实现这个操作呢?又不能创建新的数组不急,我有妙招.
原理解析:
在这道题目中,我们可以用两个指针,current和dentist,一个用来遍历整个数组,另一个用来处理当下的数据
当cur遍历到值为0的元素时,就与dest交换,随后两者同时向后移动一步
但是不管cur碰到的元素是否等于0,都会向后移动一步
代码实现:
下面是用C语言实现的代码:
void Swap(int*a,int*b){ int temp = 0; temp = *a; *a = *b; *b = temp; } void moveZeroes(int* nums, int numsSize) { int current = 0; int dentist = 0; while(current<=numsSize-1){ if(nums[current]!=0){ Swap(nums+dentist,nums+current); dentist++; } current++; } }我们将这段代码提交到力扣平台上,看看运行结果:
显然,通过了,那么以上就是这道题的题解了~~~
二、复写零
题目描述:
这道题目的意思是想让我们在对于数组中的0元素复写一遍,也就是把0再写一遍,而且不用管数组后面的元素,可以被覆盖掉.我们可以通过下面的思路进行解题:
原理解析:
在这道题中,我们首先想到的方法就是从前向后把元素都遍历一遍,在碰到0的时候就再往后移动一次写一个0,但是这样我们会发现,在复写的过程中,会把0元素后面的非零元素给覆盖掉,很显然,从前往后这种方法是行不通的,那我们不妨试试从后往前呢.
想要实现从后往前复写,我们就要找出在原数组中会被复写到的最好一个元素,这样才知道我们要性哪里开始复写.这样的话我们的思路就明了了:
1.先找出最后被复写到的元素
2.判断倒数第二个元素是不是0元素,如果是,那就直接将最后两个元素置为0
3.从后向前实现复写操作
详细代码如下:
void duplicateZeros(int* arr, int arrSize) { //第一步:先找出最后一个元素: int cur=0; int dest=-1; while(cur<arrSize){ if(arr[cur]){ dest++; } else{ dest+=2; } if(dest>=arrSize-1) break; cur++; } //现在另外判断边界情况,也就是说,只有倒数第二个是0的这种情况 if(dest==arrSize){ arr[arrSize-1] = 0; cur--; dest-=2; }现在我们将代码提交到平台上看看结果:
显然是通过的,那么这就是这道题的所有题解啦~~~~~
文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读~
