您现在的位置是:首页 > 短信大全

【C++ leetcode 】双指针问题

作者:欧阳逸时间:2024-03-24 12:11:03分类:短信大全

简介  文章浏览阅读949次,点赞59次,收藏51次。【C++ leetcode】有关双指针解法的两道题:183. 移动零 和 1089 复写零

点击全文阅读

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>& nums)     {       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>& arr)     {        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--;        }    }};

 

点击全文阅读

郑重声明:

本站所有活动均为互联网所得,如有侵权请联系本站删除处理

我来说两句

fetch1("select plface from {$dbtbpre}enewspl_set limit 1"); $facer=explode("||",$r[plface]); $count=count($facer); $plface=''; $plfacereply=''; for($i=1;$i<$count-1;$i++) { $face=explode("##",$facer[$i]); $img = $public_r[newsurl].'e/data/face/'.$face[1]; $plface.='
  • '; $plfacereply.='
  • '; } $userpiclink = ''; $username = getcvar('mlusername'); $userid=getcvar('mluserid'); $rnd = getcvar('mlrnd'); if($username&&$userid&&$rnd){ $user_r = sys_ShowMemberInfo($userid,'ui.userpic'); $userpic=$user_r[userpic]?$user_r[userpic]:$public_r[newsurl].'e/extend/lgyPl/assets/nouserpic.gif'; $userpiclink = ''; $userlink=''.$username.''; } ?>
    连接失败,请检查您的网络!
    热门评论
    0人参与,0条评论
    正在载入评论列表...