【算法挨揍日记】day01——双指针算法_移动零、 复写零

简介: 题目:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。

283.移动零

题目:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

解题思路:

我们可以利用两个指针(dest和cur)的方法,将这个数组分为三个区域

我们可以将dest初始化为-1,cur初始化为0

cur走一遍数组遇到的两种情况:

  • cur位置为0
  • cur位置为非0

当cur位置为0,cur++;

当cur不为0时,swap交换一下就好,dest++;

解题代码:

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

1089. 复写零

题目:

给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

解题思路:

本题要求我们要就地修改,不能使用额外的数组,我们先用额外的数组想一想

我们发现结果是这样的

我们再将使用额外数组的双指针方法用在本地去实验一下,我们发现dest=-1和cur=0,去正向解决问题不可以,会有元素被覆盖丢失的问题!

我们试着反向去操作呢,dest=size-1(指向最后一个元素),那我们如何确定cur的位置呢?

我们可以再利用一次双指针的方法来确认cur的位置,一开始cur=0,dest=-1

遍历数组,当cur遇到0时,dest+=2;当cur遇到非0时,cur++;

这里会有一种边界情况需要我们去考虑:

示例:1 0 2 3 0

我们通过上述方式来确定cur时,会出现以下这种情况:

会出现dest越界的情况,我们考科一让size-1的位置置为0,然后cur--,dest-=2这样就可以解决问题了

然后从后向前遇到0就是置两次0,遇到非0就是复制咯,这一步简单

解题代码:

class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int dest=-1;
int cur=0;
int size=arr.size();
//确认cur的位置
while(cur<size)
        {
if(arr[cur]==0)dest+=2;
else dest++;
if(dest>=size-1)break;
           cur++;
        }
//边界情况,示例:1 0 2 3 0,当dest的位置越界了
if(dest==size)
        {
            arr[size-1]=0;
            dest-=2;
           cur--;
        }
while(cur>=0)
        {
if(arr[cur]!=0)
           {
               arr[dest--]=arr[cur--];
           }
else
            {
                arr[dest--]=0;
               arr[dest--]=0;
                cur--;
           }
        }
     }
};


相关文章
|
2月前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
5月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
102 4
|
4月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
6月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
存储 C语言
C语言如何使用结构体和指针来操作动态分配的内存
在C语言中,通过定义结构体并使用指向该结构体的指针,可以对动态分配的内存进行操作。首先利用 `malloc` 或 `calloc` 分配内存,然后通过指针访问和修改结构体成员,最后用 `free` 释放内存,实现资源的有效管理。
305 13
|
8月前
|
C语言
指针进阶(C语言终)
指针进阶(C语言终)
|
4月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
57 0
|
5月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
210 4
|
6月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)

热门文章

最新文章