27. 移除元素
- 快慢指针,最终返回index值为移除元素后的数组末尾元素下标+1.
#include<vector> using namespace std; class Solution { public: int removeElement(vector<int>& nums, int val) { //快慢指针 int nums_length = nums.size(); int index = 0;//慢指针 for (int i=0;i<nums_length;i++){//i为快指针 if(nums[i]!=val){ nums[index]=nums[i]; index++; } } return index; } };
344. 反转字符串
class Solution { public: void reverseString(vector<char>& s) { int len = s.size(); for(int i=0, j=len-1;i<j;i++,j--){ // int temp = s[i]; // s[i] = s[j]; // s[j] = temp; swap(s[i],s[j]); } return ; } };
题目:剑指Offer 05.替换空格
- C++中string字符串replace函数,str.replace(start_index, length, "%20")
class Solution { public: string replaceSpace(string s) { string c = "%20"; for(int i=0;i<s.size();i++){ if(s[i]==' '){ s.replace(i,1,c); } } return s; } };
151.翻转字符串里的单词
class Solution { public: string reverseWords(string s) { vector<string> a; string ans = ""; for(int i=0;i<s.size();i++){ if(s[i]!=' '){ ans += s[i]; } if(s[i] ==' '&&ans!=""){ a.push_back(ans); ans = ""; } } if(ans!=""){ a.push_back(ans); } ans = ""; for(int i=a.size()-1;i>=0;i--){ if(i==0){ ans += a[i]; } else{ ans += a[i] + ' '; } } return ans; } };
206. 反转链表
- 双指针:pre、cur
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pre = nullptr, *cur = head, *temp; while(cur){ temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } };
19.删除链表的倒数第N个节点
- 虚拟头结点dummyHead
- 先行指针fast、后行指针slow,fast先走n+1步,当fast为null时,slow->next即为要删除的节点
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummyHead = new ListNode(-1); dummyHead->next = head; ListNode *slow = dummyHead, *fast = dummyHead; while(n+1){ fast = fast->next; n--; } while(fast){ fast = fast->next; slow = slow->next; } ListNode *temp = slow->next; slow->next = temp->next; delete temp; return dummyHead->next; } };
面试题 02.07. 链表相交
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *curA = headA, *curB = headB; int lenA = 0, lenB = 0; while(curA){ lenA++; curA = curA->next; } while(curB){ lenB++; curB = curB->next; } //指针复位 curA = headA, curB = headB; int gap = lenA > lenB ? lenA-lenB : lenB - lenA; //这里默认链表A更长 if(lenA < lenB) swap(curA, curB); while(gap){ curA = curA->next; gap--; } while(curA){ if(curA == curB) return curA; curA = curA->next; curB = curB->next; } return nullptr; } };
142.环形链表II
- 快慢指针判断链表是否有环:fast每次两步,slow每次一步
- 当有环时,p1指向head,p2指向相遇点,当p1、p2相遇时,即为环的入口节点
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while(fast&&fast->next){ slow = slow->next; fast = fast->next->next; if(fast == slow){ ListNode *p1 = head, *p2 = slow; while(p1!=p2){ p1 = p1->next; p2 = p2->next; } return p1; } } return nullptr; } };
第15题. 三数之和
- 剪枝
- 去重
- 双指针
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end());//原地排序 vector<vector<int>> ans; for(int i=0;i<nums.size();i++){//a+b+c中的a if(nums[i]>0){ return ans; } //a去重,因为答案中不可以包含重复三元组 if(i>0 &&nums[i]==nums[i-1]){ continue; } for(int left=i+1, right=nums.size()-1;left<right;){ int sum = nums[i]+nums[left]+nums[right]; if(sum>0){ right--; } else if(sum<0){ left++; } else if(sum==0){ 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; } };
第18题. 四数之和
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; sort(nums.begin(),nums.end()); // for(int i=0;i<nums.size()-3;i++){ //a+b+c+d,遍历a for(int i=0;i<nums.size();i++){ //a+b+c+d,遍历a //剪枝 if(nums[i]>target&&nums[i]>=0){ break; } //a去重 if(i>0&&nums[i]==nums[i-1]){ continue; } // for(int j=i+1;j<nums.size()-2;j++){ //遍历b for(int j=i+1;j<nums.size();j++){ //遍历b //剪枝 if(nums[i]+nums[j]>target&&nums[j]>=0){ //这里a+b不会溢出,int:2^31-1==2.e9; break; } if(j>i+1&&nums[j]==nums[j-1]){ continue; } for(int left=j+1, right=nums.size()-1;left<right;){ //双指针 long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];//防溢出 if(sum>target){ right--; } else if(sum<target){ left++; } 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; } };
双指针总结
- 对于数组,不真正删除,只覆盖,采用双指针
- 对于字符串,头尾双指针
- 对于链表,快慢双指针
标签:slow,ListNode,nums,int,随想录,fast,next,刷题,指针 From: https://www.cnblogs.com/daxiawan2022/p/17686066.html