【鼠鼠优选算法-双指针】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;

    }

现在我们将代码提交到平台上看看结果:

显然是通过的,那么这就是这道题的所有题解啦~~~~~

文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读~~~~

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=4d5t5y9undm