60天零基础干翻C++———

60天零基础干翻C++————双指针问题

news/2024/5/7 7:53:43

移动零

题目链接：移动零
在这里插入图片描述
本题是典型的双指针算法中的数组划分类型：
以下面为例：
删除该数组所有的0.
下面引入两个指针：

这两个指针将区间分为了三段

初始如图定义两个指针：

cur会有两种情况：

遇到非零元素。
遇到0元素。
此时为cur第一种情况：我们需要将dest和cur直接的非零元素移动到dest之前。

dest++后，和cur 互换。然后cur++，持续上述过程。当走到下图所示时

cur指向0，则cur++，dest不变

在这里插入图片描述
此时进入cur指向非零元素，cur指向的元素需要移动到dest之前

持续此流程就可以完成。
下面打印出每次交换流程：

在这里插入图片描述
打印测试代码：

void Swap(int& a,int& b)
{int c = a;a = b;b = c;
}void print(vector<int> x)
{for (int i = 0; i < x.size(); i++){cout <<x.at(i)<<' ';}cout << endl;
}void Movezeroes(vector<int>& k)
{print(k);int cur = 0;int dest = -1;for (cur = 0; cur < k.size(); cur++){if (k[cur] != 0){dest++;Swap(k[cur], k[dest]);print(k);}}
}int main()
{vector<int> a;a.push_back(1);a.push_back(2);a.push_back(0);a.push_back(0);a.push_back(0);a.push_back(2);a.push_back(1);a.push_back(0);a.push_back(1);Movezeroes(a);return 0;}

复写0

题目链接：复写0
在这里插入图片描述
复写0是典型的双指针算法。刚拿到题目可能被简单迷惑。本题如果从前往后会数据覆盖。从后往前的话双指针又指向哪里呢？我们看下面几个例子：

可以看出关键就是要找到复写之后的最后一个数。那么如何找出这个复写的数呢？
此时可以看出可以将数组分成两个区间
在这里插入图片描述

可以看出当0越多，需要的复写空间越。那么我们可以用双指针用tail统计需要留出多少空间

int head = 0;int tail = arr.size()-1;while(tail>head){if (arr[head] == 0){tail--;}++head;                                                 		}

复写占用空间相当于被抛弃的空间，所以遍历不在扫描。

此时的tail所指向的位置就是红色字，tail指向的位置有三种情况

tail指向0，该0不需要复写，因为后面空间不够。这是最特殊的情况。
tail指向0，需要复写。
tail指向非0.
此时当tail指向0时，我们如何得知是否需要复写就需要单独讨论呢。

我们发现，需要复写时head走到了tail后面。不需要复写时他们相等。这是什么原因呢

先分析第一种情况，tail和head不相等。
在这里插入图片描述
当head指向的0是离tail最近的一个时，此时分为两种情况：

tail和head指向同一个0；
head指向tail之前的0；

因为复写占用的空间是在head和tail之间，所以可以通过tail-head是否为0判断是否可以复写。显然第一种可以复写，第二种，复写空间为0，不能复写。所以当head和tail同时指向的0不能复写。这种情况我们提前处理，把0当成普通元素。

int cur = tail;int dest = arr.size();if (head == tail && arr[cur] == 0 ){dest--;arr[dest] = arr[cur];cur--;}

后面就是简单的重后往前的复写操作了。

while (dest > 0){if (arr[cur] == 0){dest--;arr[dest] = 0;}dest--;arr[dest] = arr[cur];cur--;}

快乐数

题目链接：快乐数
在这里插入图片描述

根据第一条，我们需要得到余数的平方和，这个是很容易的

int Add(int n)
{int  len = log10(n)+1;int sum = 0;int tmp = 0;for (int i = 1; i < len+1; i++){tmp = n %10;sum = sum + tmp * tmp;n = n / 10;}return sum;
}

在这里插入图片描述
2. 当出现1时 1单独成环。没有1时，其他数成环
我们只要验证，成环之时，有没有1即可
此处使用快慢指针。快指针走两步，慢指针走一步。在环内部，快慢指针一定会相遇。如果相遇是1，则环内只有1，相遇不是1，则环内一定没用1.因为1，是单独成环，

  bool isHappy(int n) {
int slow = 0;int fast = 0;slow = n;fast = Add(n);// 调用一次Add相当于走一步。while (slow != fast){slow = Add(slow);fast = Add(Add(fast));}if (slow==1)// 如果等于1.则环内只有1.{return true;}return false;}

盛最多水的容器

题目链接：盛最多水的容器

在这里插入图片描述
v= len*wide。显然随着左右指针向中间靠拢，wide一直减少。决定v的只有len。而len由左右最小的数决定。
所以，随着wide的减小决定v的关键就是左右最小的数 len。所以在移动时也应该移动最小的，

图中可以看出，v随着wide变小，最终由min(left,right)决定。所以，最小的移动才能改变v，在wide减少的情况下

  int maxArea(vector<int>& height) {int head = 0;//leftint tail = height.size() - 1;// rightint high = 0;  // min（rigrht，left）int wide = 0;int v = 0;while (tail > head){wide = tail - head;high = min(height[tail], height[head]);v = Max(wide * high, v);//记录体积最大的情况。if (height[tail] > height[head]){head++;}else{tail--;}}return v;}

有效三角形的个数

题目链接：有效三角形的个数
在这里插入图片描述
首选需要三个指针分别表示三条边的数值。为了让指针abc指向不重复，我们可以考虑将数组排序。排序有两个好处：

只要让一个指针a指向最大值，那么只需要满足较小b c满足b+c>a.
abc 不会重复选择。
画图说明各个情况排序完成后

分为两大类情况

a+b>c 满足情况,此时调小a+b 左移b
a+b<=c 不满足此时

1.调小a+b 2. 调小c
在这里插入图片描述

调小a+b
调小c

注意事项：

int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());
int head=0;
int Maxtail=nums.size()-1;
int tail=nums.size()-2;
int num=0;
for(Maxtail;Maxtail>1;Maxtail--)
{head=0;tail=Maxtail-1;while(tail>head){if(nums[tail]+nums[head]>nums[Maxtail]){num+=tail-head;tail--;}else{head++;}}
}
return num;}