有些题目已经刷过了✅不过双指针在算法中有非常多的应用🔥下面解法就统一用再双指针速刷一遍
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0;
while(fast < nums.size()){ // fast pointer is to find the element that is equal to val
if(nums[fast] != val) nums[slow++] = nums[fast++];
else fast++;
}
return slow;
}
};class Solution {
public:
void reverseString(vector<char>& s) {
int slow = 0, fast = s.size() - 1;
while(slow < fast){
swap(s[slow++], s[fast--]);
}
}
};#include<bits/stdc++.h>
using namespace std;
int main(){
string s; cin >> s;
int c = 0;
for(int i = 0; i < s.size(); i++){
if('0' <= s[i] && s[i] <= '9') c++;
}
int n = (int)s.size();
s.resize(n + c * 5);
int l = n - 1;
int r = (int)s.size() - 1;
while(l >= 0){
if('0' <= s[l] && s[l] <= '9'){
s[r--] = 'r';
s[r--] = 'e';
s[r--] = 'b';
s[r--] = 'm';
s[r--] = 'u';
s[r--] = 'n';
l--;
}
else s[r--] = s[l--];
}
cout << s << endl;
return 0;
}151. Reverse Words in a String
class Solution {
public:
string reverseWords(string s) {
int slow = 0, fast = 0;
reverse(s.begin(), s.end());
bool wordstart = false;
for(fast = 0; fast < s.size(); fast++){
if(s[fast] != ' '){
if(wordstart && slow > 0) s[slow++] = ' ';
int start = fast;
while(fast < s.size() && s[fast] != ' '){
s[slow++] = s[fast++];
}
reverse(s.begin() + slow - (fast - start), s.begin() + slow);
wordstart = true;
}
}
s.resize(slow);
return s;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tmp;
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur){
tmp = cur -> next;
cur -> next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = dummyhead;
while(cur->next != nullptr && cur->next->next != nullptr){
ListNode* tmp = cur->next;
ListNode* tmp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp;
cur->next->next->next = tmp1;
cur = cur->next->next;
}
ListNode* result = dummyhead->next;
delete dummyhead;
return result;
}
};19. Remove Nth Node From End of List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* slow = dummyhead;
ListNode* fast = dummyhead;
while(n-- && fast!= nullptr) fast = fast->next;
fast = fast->next;
while(fast != nullptr){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyhead->next;
}
};160. Intersection of Two Linked Lists
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while(curA){
curA = curA->next;
lenA++;
}
while(curB){
curB = curB->next;
lenB++;
}
curA = headA;
curB = headB;
if(lenB > lenA){ //让A是最长链表
swap(curB, curA);
swap(lenA, lenB);
}
int gap = lenA - lenB;
while(gap--) curA = curA->next;
while(curA){
if(curA == curB) return curA;
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
};class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum < 0) left++;
else if(sum > 0) right--;
else {
ans.push_back({nums[i], nums[left], nums[right]});
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return ans;
}
};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());
for(int i = 0; i < nums.size() - 3; i++){
if(long(nums[i]) + nums[i + 1] + nums[i + 2] + nums[i + 3]> target) break;
if(long(nums[i]) + nums[nums.size() - 1] + nums[nums.size() - 2] + nums[nums.size() - 3] < target) continue;
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < nums.size() - 2; j++){
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.size() - 1;
while(left < right){
long sum = long(nums[i]) + nums[j] + nums[left] + nums[right];
if(sum < target) left++;
else if(sum > target) right--;
else {
ans.push_back({nums[i], nums[j], nums[left], nums[right]});
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
}
return ans;
}
};