双指针刷题和总结

文章目录 双指针LeetCode反转字符串题目题解代码 删除有序数组中的重复项 II题目题解代码 除字符串中的所有相邻重复项题目题解代码 删除有序数组中的重复项题目题解代码 蓝桥杯拔河题解代码

双指针

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; }