文章目录
双指针
1. 同向双指针:两个指针从同一侧开始，按照相同的方向移动。通常用于滑动窗口或需要维护某个区间的问题。
2. 反向双指针：两个指针分别从数据结构的左右两端开始，向中间移动。通常用于有序数组或需要从两端逼近的问题。
3. 快慢指针：两个指针以不同的速度移动，通常用于链表问题或检测循环。
LeetCode
反转字符串
题目
题解
1. 很明显这题要用反向双指针，将字符串反过来，就是把字符串第一个字符和最后一个字符交换位置，以此类推就可以将字符串反过来了
代码
class Solution
{
public:
void reverseString(vector<char>& s)
{
int n = s.size();
int l = 0,r = n - 1;
while(l < r)
{
swap(s[l],s[r]);
l++;
r--;
}
}
};
删除有序数组中的重复项 II
题目
题解
1. 快慢指针，快指针bp=2，慢指针sp = 1，快指针遍历数组一遍，找到sp-1元素和bp元素不等的情况，将++sp替换为bp
1 1 1 2 2 3
sp-1 sp bp // bp = sp-1
1 1 1 2 2 3
sp-1 sp bp // bp != sp-1
1 1 2 2 2 3
sp-1 sp bp // bp != sp-1
1 1 1 2 2 3
sp-1 sp bp // bp != sp-1
1 1 1 2 2 3
sp-1 sp bp
代码
class Solution
{
public:
int removeDuplicates(vector<int>& nums)
{
int n = nums.size();
if(n < 3) return n;
int sp = 1,bp = 2;
for(bp = 2;bp < n;bp++)
{
if(nums[sp-1] != nums[bp])
{
nums[++sp] = nums[bp];
}
}
return sp + 1;
}
};
除字符串中的所有相邻重复项
题目
题解
1. 这题用栈比较简单，如果栈为空，把元素插入到栈中，再和数组中的元素比较，如果相同就出栈，如果不同就入栈，最后剩余的元素就是答案
2. 但是要返回字符串，如果栈非空就把元素插入到字符串中，最后得到的字符串和答案是相反的，再逆置一下即可
代码
class Solution
{
public:
string removeDuplicates(string s)
{
// 栈
stack<char> sk;
for(auto ch : s)
{
if(sk.empty()) sk.push(ch);
else
{
if(sk.top() == ch) sk.pop();
else sk.push(ch);
}
}
string s1;
while(!sk.empty())
{
s1.push_back(sk.top());
sk.pop();
}
reverse(s1.begin(),s1.end());
return s1;
}
};
删除有序数组中的重复项
题目
题解
1. 这题用栈也是可以的，先把第一个元素插入到空栈中，再和数组中的元素比较如果相同就不入栈，如果不同就入栈，就可以达到只保留一个数的目的
2. 可以用set去重，但是这题有个坑，不能直接返回n，要去重后把数组中的元素修改为去重后的，可能是它自己也要检测
3. 同向双指针，一个元素不需要去重直接返回，cur指针和i指针如果相同i就往后走，cur不动，如果不相同cur走到下一位置，i位置的指针赋给cur指针（就是直到找到不同的就给cur的下一个位置的指针，达到了不重复的效果）
代码
class Solution
{
public:
int removeDuplicates(vector<int>& nums)
{
// set去重,还要修改nums中元素的顺序
// int m = nums.size();
// set<int> st(nums.begin(),nums.end());
// int n = st.size();
// nums.clear();
// for(auto& ch : st) nums.push_back(ch);
// return n;
int n = nums.size();
if(n == 1) return 1;
int cur = 0;
for(int i = 0;i < n;i++)
{
if(nums[cur] != nums[i])
{
cur++;
nums[cur] = nums[i];
}
}
cur++;
return cur;
}
};
蓝桥杯
拔河
题解
1. 这题其实可以用枚举算出每一种情况，如果两数的差最小，排序后一定相邻，最好是都开long long不然可能会爆空间
代码
#include <iostream>
#include<algorithm>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
long long a[N];
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> a[i];
vector<long long> ret;
for(int i = 0;i < n;i++)
{
long long s = 0;
for(int j = i;j < n;j++)
{
s += a[j];
ret.push_back(s);
}
}
long long ans = 1e9 + 10;
sort(ret.begin(),ret.end());
for(int i = 1;i < ret.size();i++)
{
ans = min(ans,ret[i] - ret[i-1]);
}
cout << ans << '\n';
return 0;
}