双指针

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    3sp-1  sp        bp // bp != sp-1
1    1    1    2    2    3sp-1  sp        bp // bp != sp-1
1    1    1    2    2    3sp-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;
}