算法基础学习Day1(双指针)

1.题目

1. 283. 移动零 - 力扣（LeetCode）
2. 1089. 复写零 - 力扣（LeetCode）

2.题目解答

1.移动零

题目

算法学习

这类题主要是在数组中进行,将数组划分为若干个区间

这道题就是将数组划分为非零区间和零区间

解决这类题就是双指针算法,如果在数组中就直接用下标充当指针

cur:从左向右扫描数组,遍历数组

dest:已经处理过的区间(非零元素的最后一个位置)

这里有三个区间:

位置	区间数据
[0,dest]	非零元素
[dest+1,cur-1]	零元素
[cur,n-1]	未处理

这里的思想和快排的思想是差不多的,快排是将数组分成多个部分,进而向下继续排序,这里就不向下进行了

代码提交

C语言代码:

void swap(int *a,int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void moveZeroes(int* nums, int numsSize) {
    int dest = -1;
    int cur = 0;
    while(cur<numsSize)
    {
        if(nums[cur] == 0)
        {
            cur++;
        }
        else
        {
            dest++;
            swap(&nums[dest],&nums[cur]);
            cur++;
        }
    }
}

C++代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur = 0, dest = -1;cur<nums.size();cur++)
        {
            if(nums[cur])
            {
                swap(nums[++dest],nums[cur]);
            }
        }
    }
};

2.复写零

题目

算法学习

这里我们的处理方法是:先找到最后一个要复写的数,从后向前完成复写工作

第一个问题如何找到最后一个要复写的数呢?

这里推荐的仍然是双指针算法:

1. 先判断cur位置的值

2. 根据cur的值来决定dest向后移动一步或者两步

3. 判断一下dest是否已经到结束位置

但是这里有个问题:

如果在最后的时候出现了一个零,此时让dest向后++,就会导致dest直接越界,这里我们就要处理一下了

代码提交

class Solution 
{
 public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 1.先找到最后⼀个数
 
        int cur = 0, dest = -1, n = arr.size();
        while(cur < n)
        {
            if(arr[cur]) dest++;
            else dest += 2;
            if(dest >= n - 1) break;
            cur++;
        }
        // 2. 处理⼀下边界情况
 
        if(dest == n)
        {
            arr[n - 1] = 0;
            cur--; dest -=2;
        }
        // 3. 从后向前完成复写操作
 
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
 };

原文地址：https://blog.csdn.net/2302_82004664/article/details/144273766

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！