【算法——双指针】
922. 按奇偶排序数组 II
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>nums = { 3,1,2,4 };
int i = 0, j = 1;
int n = nums.size() - 1;
while (j < nums.size() && i < nums.size()) //如果奇偶任一方排好了，另一方自然排好了
{
//判断最后一个元素奇偶
if (nums[n] % 2 != 0) {
swap(nums[j], nums[n]);
j += 2; //来到下一个奇数位置
}
else {
swap(nums[i], nums[n]);
i += 2; //来到下一个偶数位置
}
}
287. 寻找重复数
快慢指针
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>nums = {};
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) //一开始快指针一次2步，慢指针一次1步
{
fast = nums[nums[fast]];
slow = nums[slow];
}
fast = 0; //二者第一次相遇后，快指针重置为初始位置
while (slow != fast) //快慢都一次一步
{
fast = nums[fast];
slow = nums[slow];
}
//最后返回fast和slow都可以
42. 接雨水
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
思想：每个格子上方的水量进行累加，首先求这个格子左边的最大格子和右边的最大值。
如果左边比右边小，那么左边就是一个兜底，我当前格子装水量就是左减当前格子数。
右比左小同理，右边就是兜底。
总结：
min(left_max, max_right)-nums[i]
特例:当前格子数比左右都大，就直接为0，这时候没有人兜底了
最终式子:max(min(left_max, max_right)-nums[i],0)两侧最大值怎么求？
main
vector<int>nums = { 0,1,0,2,1,0,1,3,2,1,2,1 };
int n = nums.size();
vector<int>lmax(n);
lmax[0] = nums[0];
for (int i = 1; i < n; i++) //左侧最大值不断继承
lmax[i] = max(nums[i], lmax[i - 1]);
vector<int>rmax(n);
rmax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0 ; i--) //右侧最大值不断继承
rmax[i] = max(nums[i], rmax[i + 1]);
int sum = 0;
for (int i = 1; i < n - 1; i++) //计算
sum += max(min(lmax[i - 1], rmax[i + 1]) - nums[i], 0);
cout << sum;
881. 救生艇
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>people = { 3,5,3,4 };
int limit = 3;
int n = people.size();
sort(people.begin(), people.end()); //进行一个排序
int l = 0, r = n - 1; //左右指针
int ans = 0; //计数
while (l <= r)
{
//这个边界处理至关重要，防止l和r指向同一个地方重复计数
int sum = l==r ? people[l]:people[l] + people[r];
//最大和最小的都已经装不下来，所以直接最大的单独一个船
if ( sum > limit)
{
ans++; //装当前遍历的最大的
r--;
}
else if( sum <= limit)
{
ans++; //两人一船
l++;
r--;
}
}
return ans;
变种：两个人一船时，必须体重之和为偶数。就把数组中奇偶分开，单独求最优，然后相加。
原文地址：https://blog.csdn.net/2301_76758064/article/details/142419281
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！