C++刷题笔记(2)——leetcode27、26、283

本文主要是介绍C++刷题笔记(2)——leetcode27、26、283，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

双指针法

双指针法利用两个指针对数组进行扫描，利用问题本身所给的序列特性(升序或降序)，通常是相反方向的或者相同方向不同速度(快慢指针)

并非是一种算法，更像是一种变成技巧；

快慢指针中，在慢指针循环内定义快指针，快指针在慢指针之前，对数组后续元素依次扫描，在扫描到指定元素或者数组结尾的时候快指针返回，慢指针后移，并且根据题目要求移动或替换元素。

题目1：27.移除元素

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

暴力解法

两层for循环，一个for循环遍历数组元素，第二个for循环更新数组
在这里插入图片描述
暴力算法的解题思路很简单，就是遍历数组找到目标元素，然后依次移动目标元素后面的元素将其覆盖

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < nums.size(); i++) {            //遍历数组if (nums[i] == val) {                          //发现需要移除的元素for (int j = i + 1; j < size; j++) {       //就将数组集体向前移动一位nums[j - 1] = nums[j];             }i--;                                       //因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--;                                    //此时数组的大小-1}}return size;}
};

双指针法

在这里插入图片描述
当碰到target数值，慢指针停止移动，快指针保持移动，并把快指针指向的数组元素移动到慢指针
单向双指针方法：
没有改变数组中元素的相对位置

//单向双指针
class Solution {
public:int removeElement(vector<int>& nums, int val) {int i = 0;                                         //i为慢指针for (int j = 0; j < nums.size() - 1; j++) {        //j为快指针，这里不能写j < nums.size() - 1，防止数组长度为1和0if (val != nums[j]) {nums[i++] = nums[j];                      //nums中的j元素如果不等于val，则慢指针后移一位，快指针后移一位}}                                                //若j等于val，则再次进入循环体，快指针后移，慢指针不动return i;}
};

单向双指针方法解题思路：
在这里插入图片描述
首先就是快指针、慢指针的索引初始为0，根据循环条件j < nums.size()进入循环，寻找数组中等于目标值的元素，这里要注意后置递增是先计算表达式、再对变量进行加1

直到i=2、j=2，此时j的值仍满足循环条件，但不满足if语句，因此不会执行if语句，直接执行j++，j=3
在这里插入图片描述
再次进行循环，j=3，满足循环条件且满足if语句，此时j=3、i=2，执行if语句会将进行赋值操作nums[2] = nums[3]; 完成移除元素操作

之后会依次将快指针的值赋给慢指针

当i=3、j=4时依然满足循环条件和if语句条件，继续进行一个循环后i=4、j=5，不再满足循环条件，返回i，返回移除后数组的新长度。
在这里插入图片描述

双向指针方法：
基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素

class Solution {
public:int removeElement(vector<int>& nums, int val) {int i = 0;                                      //左指针int j = nums.size() - 1;                        //右指针while (i <= j) {                                while (i <= j && nums[i] != val) {          //找左边等于val的元素，如果这里不加i <= j的限制，就可能i一直右移到j右边，造成数组长度不准确++i; }while (i <= j && nums[j] == val) {          //找右边不等于val的元素，这里i<=j同上--j;}if (i < j) {                                //将右边不等于val的元素覆盖左边等于val的元素，这里i<j没有等于，如果可以等于，那么执行i++、j--后同样i可能移动到j右边nums[i++] = nums[j--];}}return i;                                       //i一定指向了最终数组末尾的下一个元素}
};

双向指针方法解题思路：
在这里插入图片描述
这种解法的思路左指针从数组的左边开始遍历数组，寻找等于目标值的元素；右指针从右开始遍历数组，寻找不等于目标值的元素，

于是就有了等于目标值的元素的索引和正常的元素，用正常元素覆盖等于目标值的元素完成移除元素操作
在这里插入图片描述
之后左指针继续遍历数组，当左指针i=4时仍满足while (i <= j)和while (i <= j && nums[i] != val)的循环条件，因此还会继续进行累加，累加后i=5，不再满足循环条件，返回i，返回移除后数组的新长度。

题目2：26.删除排序数组中的重复项

在这里插入图片描述
单向双指针方法：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int i = 0;                                //i慢for (int j = 1; j < nums.size(); j++) {   //j快if (nums[i] != nums[j]) {i++;                              //移到下一位，将不同的数放入nums[i] = nums[j];}}return i + 1;                            //删除后数组的新长度}
};

单向双指针方法解题思路：
在这里插入图片描述
解题思路大概和27题差不多，当i=2、j=3时，将会跳过if语句，执行j++，此时i=2、j=4，

继续执行代码i++;nums[i] = nums[j];(i=3,nums[3] = nums[4])，删除数组中的重复项，j++，此时i=3、j=5，不再满足循环条件，返回数组成都
在这里插入图片描述
然后进行j++，此时i=3、j=5，不再满足循环条件，返回数组长度。

题目3：283.移动零

在这里插入图片描述
这一题和27题非常的类似了
单向双指针方法：

class Solution {
public:void moveZeroes(vector<int>& nums) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (nums[fastIndex] != 0) {nums[slowIndex++] = nums[fastIndex];}}// 将slowIndex之后的冗余元素赋值为0for (int i = slowIndex; i < nums.size(); i++) {nums[i] = 0;}}
};