C++算法：双指针
双指针
1.移动零
属于一类数组划分或数组分块题型，使用双指针算法，类似快排的双指针法，以a[key]将数组划分为<=a[key]部分和>a[key]部分。
定义两个指针cur、dest。
cur：从左往右扫描数组，即遍历数组。
dest：在已处理区间内，记录非0元素最后一个位置。
首先cur会把数组划分为已处理区间和未处理区间 [0,cur-1]和[cur,n-1]。
在已处理区间，dest会分出[0,dest]和[dest+1,cur-1]，[0,dest]为相对顺序不变的非0数，[dest+1,cur-1]全为0。
关键：时刻保证
[0,dest] ——》非0
[dest+1,cur-1] ——》0
[cur,n-1] ——》待处理
如何做到：
dest先置为-1，cur为0，则一开始无[0,dest]，[dest+1,cur-1]。随着cur++，[0,dest]，[dest+1,cur-1]两个区间开始变化，可以假定现在[0,dest]全为非0，[dest+1,cur-1]全为0。当cur遇到非0时，要把a[cur]放到[0,dest]里，所以区间[0,dest]要扩大，即dest++，然后交换a[dest]和a[cur]。dest++后，a[dest]落在全为0的区间，此时交换就把0交换出非0区间了。
代码实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1;
int cur = 0;
for (int i = 0;i < nums.size();i++)
{
if (nums[cur] != 0)
{
dest++; //扩大非0区间
swap(nums[cur], nums[dest]);
}
cur++; //cur扫描数组
}
}
};
2.复写零
使用 双指针算法 ，先根据异地操作，再优化成双指针的就地操作。
异地操作即另开一个数组，定义cur指向首元素，dest指向新数组的第一个位置。cur遍历原数组，arr[cur]不为0时，dest对应为arr[cur]，dest++；arr[cur]为0时，dest和dest+1对应为0，dest+=2。最后就完成了异地复写。
就地操作分2步：
- 用双指针算法找到最后一个复写的数。
- 为避免覆盖，选择“从后向前”完成复写操作。
对于第1步，
-
一开始cur置为0，dest置为-1，cur遍历数组，判断arr[cur]的值。
-
arr[cur]不为0，dest向后走一步，arr[cur]为0，dest向后走两步。
-
dest每次走完后，判断dest是否已经到arr.size()-1，若是，则循环结束。
-
每次循环都要cur++。
第1步的特例，arr[]={1,0,2,3,0,4}。因为第1步出循环的条件是cur>arr.size()-1或dest>=arr.size()-1，对于这个特例，最后一次循环中，arr[cur]=0，dest+=2后越界，跳出循环。
此时从后往前复写即把arr[dest]和arr[dest-1]置为0，这样会越界访问，所以直接把arr[dest-1]置为0，然后dest-=2，cur–。
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0;
int dest = -1;
int n = arr.size();
while (cur < n)//第1步
{
if (arr[cur])
dest++;
else
dest += 2;
if (dest >= n - 1)//
break;
cur++;
}
if (dest == n)//越界处理特例
{
arr[dest - 1] = 0;
dest -= 2;
cur--;
}
while (cur >= 0)//第2步复写
{
if (arr[cur])
arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
3.快乐数
以19和2为例：
可以看到，一个数经过快乐数的操作，最终都会进入一个循环，只要最终在1循环，就是快乐数。类似判断链表是否带环，所以此题可用快慢指针求解，当两指针相遇时，说明有循环，如果在1循环，即slow=1，则是快乐数。
由鸽巢原理，最终是一定会进入循环的。
810个数，经过大于810次操作后，必然会出现重复的数，即循环。
class Solution {
public:
int Sum(int n)//快乐数操作
{
int sum = 0;
while (n)
{
int ret = n % 10;
sum += ret * ret;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = Sum(n);//先拉开距离，两指针才能进入while循环
while (slow != fast)
{
slow = Sum(slow);//注意更新n
fast = Sum(Sum(fast));
}
if (slow == 1)
return true;
return false;
}
};
4.盛最多水的容器
解法1：暴力枚举，两两取垂线，得出一系列体积，再从这些体积中找到最大值。
解法2：找规律，发现单调性，使用双指针解决问题。
任取一段区间[i,j]，定住min(height[i]，height[j])对应的height[i]或height[j]，上图即定住4，发现如果区间缩小，体积Vij一定比一开始区间求出体积小，所以，值小的一端可以不用考虑。所以定义left=0，right=height.size()-1，谁小谁往中间移动，二者相遇时结束，这个过程中会得到一系列体积，用max记录最大体积。
class Solution {
public:
int maxArea(vector<int>& height)
{
int n = height.size();
int left = 0;
int right = n - 1;
int max = 0;
int v = 0;
while (left != right)
{
if (height[left] < height[right])
{
v = height[left] * (right - left);
left++;
}
else
{
v = height[right] * (right - left);
right--;
}
if (max < v)
max = v;
}
return max;
}
};
5.有效三角形的个数
给3个数，看能否构成三角形，需同时满足3个条件：a+b>c，a+c>b，b+c>a。
解法1：暴力枚举
对于所给数组，先用循环固定一个数，再用循环固定第二个数，最后再来一层循环遍历剩下的数并判断是否满足三角形的条件。
//伪代码
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=j+1;k<n;k++)
{
check(nums[i],nums[j],nums[k]);//判断是否构成三角形
}
时间复杂度为O(N^3)，显然是不行的。
解法2：找规律，利用单调性，使用双指针算法。
如果三角形三边a,b,c是有序的，即a<=b<=c，由于c是最大的，那么只要判断a+b>c即可。所以，对于给定数组nums，先进行升序排序。
例如，排序后的nums为[2，2，3，4，5，9，10]。
先固定最大的数nums[n-1]作为c，定义left=0，right=n-2，显然nums[left]<=nums[right]。若nums[left]+nums[right]>nums[n-1]，定住nums[right]，剩下的元素都比nums[left]大，所以有right-left个三元组能构成三角形。
接下来right–，继续上述操作，若nums[left]+nums[right]<=nums[n-1]，则left++，由于是升序数组，nums[left]才会变大。当left和right相遇时，缩小区间，固定最大数nums[n-2]。如此循环，直到最大数为nums[0]。
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
sort(nums.begin(), nums.end());//排序优化
int sum = 0; //构成三角形的三元组数
for (int i = nums.size() - 1;i >= 0;i--)
{
int left = 0;
int right = i - 1;
while (left < right)
{
if (nums[left] + nums[right] > nums[i])
{
sum += (right - left);
right--;
}
else
{
left++;
}
}
}
return sum;
}
};
6.和为s的两个数
解法1：暴力枚举
解法2：发现单调性，使用双指针
定义left=0，right=n-1，sum=price[left]+price[right]。因为数组price是升序的，如果sum<target，由于price[right]是数组中最大的，所以left++，使price[left]增大，sum才会增大；如果sum>target，则sum要减小，只能让right–，sum才减小；当sum==target时，即得所求结果。在循环中，如果left与right相遇，则说明数组中没有两个数相加等于target。
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
vector<int> v;
int n=price.size();
int left=0;
int right=n-1;
while(left<right)
{
int sum=price[left]+price[right];
if(sum<target)
left++;
else if(sum>target)
right--;
else
return {price[left],price[right]};
}
return v;
}
};
7.三数之和
解法1：排序，暴力枚举，set去重。
对于去重，把枚举结果放入vector<vector<int>> vv中，再用迭代器区间构造传给set<vector<int>> s去重，再用迭代器区间构造传回vv。这个时间复杂度为O(N^3)，显然是不行的。
解法2：排序 + 双指针
先将数组排成升序，i=0，遍历数组，在i后面的区间用双指针快速找到两个数的和为 -nums[i]，用前面“和为s的两个数”的类似方法求解，nums[i]、nums[left]、nums[right]即为所求三元组。
处理细节：
-
不漏
找到一种结果后不要停，缩小区间，继续寻找，避免遗漏。
-
去重
找到一种结果后left和right要跳过重复元素；当使用完一次双指针算法后，即left与right相遇，i也要跳过重复元素。同时都要避免越界。
小优化：
当nums[i]>0时，nums[left]+nums[right]>0是必然的，此时nums[left]+nums[right]一定不等于-nums[i]，无需继续遍历。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> vv;
sort(nums.begin(), nums.end());//先排为升序
int n = nums.size();
for (int i = 0;i < n;)
{
if (nums[i] > 0)//小优化
break;
int target = (-nums[i]);
int left = i + 1;
int right = n - 1;
while (left < right)//双指针
{
int sum = nums[left] + nums[right];
if (sum < target)
left++;
else if (sum > target)
right--;
else
{
vv.push_back({ nums[i],nums[left],nums[right] });
left++;
right--;
//双指针去重
while (left < right && nums[left] == nums[left - 1])
left++;
while (left < right && nums[right] == nums[right + 1])
right--;
}
}
i++;
while (i < n && nums[i] == nums[i - 1])//i去重
i++;
}
return vv;
}
};
8.四数之和
与三数之和类似，相当于里面套了一个三数之和。先将数组排成升序，然后固定一个数，在该数后面的区间进行三数之和操作，即再定一个数，在其后面用双指针，使nums[left]+nums[right]==target-nums[i]-nums[j]，四元组nums[i]、nums[j]、nums[left]、nums[right]即为所求结果。
class Solution11 {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> vv;
sort(nums.begin(), nums.end());//先排成升序
int n = nums.size();
if (n < 4) //元素数量不足，无法构成四元组
return vv;
for (int i = 0;i < n;)
{
if (nums[i] > 0 && target < 0)
break;
for (int j = i + 1;j < n;)
{
int left = j + 1;
int right = n - 1;
long long t = (long long)target - nums[i] - nums[j];
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum < t)
{
left++;
}
else if (sum > t)
{
right--;
}
else
{
vv.push_back({ nums[i],nums[j],nums[left],nums[right] });
left++;
right--;
//去重一
while (left < right && nums[left] == nums[left - 1])
left++;
while (left < right && nums[right] == nums[right + 1])
right--;
}
}
j++;
while (j < n && nums[j] == nums[j - 1])//去重二
j++;
}
i++;
while (i < n && nums[i] == nums[i - 1])//去重三
i++;
}
return vv;
}
};
更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)