双指针经典题目
1089. 复写零
法一：用栈实现
解题思路： ❁ 将遍历到的数据放入栈中 ❁ 如果放入的数据为0，且栈中数据 < arr.size()，则再放入一个0 ❁ 如果栈中数据 >= arr.size()，直接结束循环 ❁ 将栈中的数据逆序（因为栈是先进后出）放入答案数组ans
class Solution {
public:
// 用栈来实现
void duplicateZeros(std::vector<int>& arr) {
int size = arr.size();
std::stack<int> st;
int top = 0, i = 0;
while (top < size) {
st.push(arr[i]);
top++;
if (top < size && arr[i] == 0) {
st.push(0);
top++;
}
i++;
}
for (int i = 0; i < size; i++) {
arr[size - 1 - i] = st.top();
st.pop();
}
}
};法二：用双指针
解题思路： ❁ 题目要求：原地操作 ❁ 我们可以先思考异地的操作，然后发现可以定义一个cur指针和一个dest指针，cur指向原数组，dest指向答案数组，当cur指向的值为非0，则cur++, dest++，否则cur++, dest += 2 ❁ 再由异地操作思考原地操作，但是发现当dest > cur时，会修改cur后面的值，导致答案错误 ----> 思路转换 ----> 转换为从后向前修改 ❁ 需要我们先找到最后一个被放入答案数组的位置 -----> 也就是找到cur最后指向的位置 ❁ 从后向前修改数组，arr[dest] = arr[cur],如果arr[cur] == 0,则arr[dest - 1] = arr[cur] ❁ 注意点：dest可能再修改数组前 = size，那将造成越界访问；而dest = size的原因是：cur最后指向的元素为0，因此在修改数组前，应该判断是否dest == size，如果满足，则将arr[size - 1] = 0, cur--, dest -= 2
如下代码用top替代上面的dest,用i替代上面的cur
class Solution {
public:
// 双指针实现
void duplicateZeros(vector<int>& arr)
{
int size = arr.size();
int top = -1/*因为指向最后位置*/, i = 0;
// 注意顺序
// 找cur最后的位置
// 1、判断cur位置的值
// 2、根据cur的值移动dest
// 3、判断dest的位置
// 4、移动cur
while (i < size)
{
if (arr[i] == 0)
top++;
top++;
if (top >= size - 1)// 已经到达最后一个位置
break;
i++;
}
// 越界了，dest = size
if (top == size)
{
arr[size - 1] = 0;
top -= 2;
i--;
}
// 从后向前修改数组
while (i >= 0 && top >= 0)
{
arr[top] = arr[i];
top--;
if (arr[i] == 0)
{
arr[top] = 0;
top--;
}
i--;
}
}
};202. 快乐数
题目链接：. - 力扣（LeetCode）
解题思路： 1、实际上这是一个一定成环的问题，我以2为例，这个例子不会变成1
2、如果能变为1，也将陷入循环
3、不管会不会变成1，都会陷入循环，我们只需要判断环内的数是不是为1就好了 4、既然变为环，我们就可以联想到判断链表是否成环的那个问题的解法：快慢指针 ，在判断链表是否成环的那个问题中快指针每一次走两步，慢指针每一次走一步，而这一题，我们的慢指针只要计算每一位的平方和一次，而快指针要计算每一位的平方和两次
class Solution {
public:
// 快慢指针
int GetAns(int a) {
int ans = 0;
while (a) {
ans += ((a % 10) * (a % 10));
a /= 10;
}
return ans;
}
bool isHappy(int n) {
int s = n, f = GetAns(n); // 因为如果s和f相等，则下面的循环进不去，因为一定成环，不用继续判断成环的位置
// 获得成环时的入口数据
// 如当n = 2时，入口数据为4
while (s != f) {
s = GetAns(s);
f = GetAns(GetAns(f));
}
// 判断入口数据是否为1
return s == 1;
}
};11. 盛最多水的容器
题目链接：. - 力扣（LeetCode）
这题太经典了，OI中的题目也常考
解题思路： ⚀ 该题有点贪心思维，根据贪心的思想，我们容易知道，两边的柱子高度越高，盛的水会更容易多 ⚁ 因此，我们可以用两个指针，一个指向开头，一个指向最后一个元素，然后每次移动较矮的那个指针即可
class Solution {
public:
// 用双指针，一个指向左边，一个指向右边，移动更矮的那个指针
int maxArea(vector<int>& height)
{
int ret = 0;
int l = 0, r = height.size() - 1;
while (l < r)
{
if (height[l] < height[r])
{
ret = max(ret, (r - l) * height[l]);
l++;
}
else
{
ret = max(ret, (r - l) * height[r]);
r--;
}
}
return ret;
}
};611. 有效三角形的个数
题目链接：. - 力扣（LeetCode）
解题思路: 双指针 三角形的判断条件是：a + b > c 所以我们可以先排序，然后固定c，a、b为双指针 1、如果a + b > c:那么说明a和a到b之间的所有数据都满足a + b > c，因此 ret += b - a; 同时移动b指针 2、如果a + b <= c:那么说明a太小了，因此要找一个能满足a + b > c的a，因此要移动a指针 当a和b指针重叠时，移动c,a定位到0位置，b定位为c的前面一个位置
// 判断是否为三角形：两个小边的和 > 第三边
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
if (nums.size() < 3)
return 0;
int ret = 0;
sort(nums.begin(), nums.end());
int size = nums.size();
int l = 0, r = size - 2;
int ptr = size - 1;
while (l < r)
{
if (nums[l] + nums[r] > nums[ptr])
{
ret += r - l;
r--;
}
else
{
while (l < r && nums[l] + nums[r] <= nums[ptr])
l++;
}
if (l == r)
{
ptr--;
l = 0;
r = ptr - 1;
}
}
return ret;
}
};LCR 179. 查找总价格为目标值的两个商品
题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
原剑指offer：和为s的两个数
// 数组已经是升序了
// 解法1 哈希：存数据
// 解法2 双指针：查找
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
int l = 0, r = 1;
vector<int>ans(2);
int size = price.size();
while (r < size && price[l] + price[r] != target)
{
if (price[l] + price[r] > target)
{
l++;
r = l + 1;
continue;
}
r++;
if (r == size)
{
l++;
r = l + 1;
}
}
ans[0] = price[l];
ans[1] = price[r];
return ans;
}
};15. 三数之和
题目链接：. - 力扣（LeetCode）
解法汇总： 1、使用map，固定两个数，查找第三个数 超时超内存 2、排序 + 暴力枚举 + set去重 3、有序算法要想到：二分 或者 双指针 如果可以用双指针，就用双指针（可以降低时间复杂度） 可以运用两数之和 = target的做法，将三数之和转化为：固定一个数值nums[i]，在其他元素中找和为target3 - nums[i] 这个固定的数值就可以用循环遍历数组来实现
class Solution {
public:
// 3、双指针
// 先排序，再遍历i，固定i，先判断nums[i] == nums[i - 1]，等于就要continue跳过（去重操作）
// 另外l指针为i + 1，r为size - 1，
// 1、如果和 > 0，l++
// 2、如果和 < 0，r--
// 如果和 = 0，加入答案数组，并去重
vector<vector<int>> threeSum(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<vector<int>>ans;
if (nums.size() < 3)
return ans;
int size = nums.size();
for (int i = 0; i < size - 2; i++)
{
if (nums[i] > 0)
return ans;
// 去重
if (i > 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1, r = size - 1;
while (l < r)
{
int sum = nums[i] + nums[l] + nums[r];
if (sum > 0)
r--;
else if (sum < 0)
l++;
else
{
ans.push_back({nums[i], nums[l], nums[r]});
// 去重
while (l < r && nums[l + 1] == nums[l])
l++;
while (l < r && nums[r - 1] == nums[r])
r--;
l++;
r--;
}
}
}
return ans;
}
};18. 四数之和
题目链接：. - 力扣（LeetCode）
解题思路： 四数之和 转化为 三数之和，三数之和 转化为 两数之和
//注意：不重复
/*法一：双指针法，l,r,i,j*/
// 与三数之和类似，无非多了一层循环
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>>ans;
if (nums.size() < 4)
return ans;
sort(nums.begin(), nums.end());
int size = nums.size();
for (int i = 0; i < size - 3; i++)
{
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < size - 2; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int l = j + 1, r = size - 1;
while (l < r)
{
long long sum = (long long)/**/nums[i] + nums[j] + nums[l] + nums[r];
if (sum < target)
l++;
else if (sum > target)
r--;
else
{
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
while (l < r && nums[l + 1] == nums[l])
l++;
while (l < r && nums[r - 1] == nums[r])
r--;
l++;
r--;
}
}
}
}
return ans;
}
};腾讯云开发者
