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. 反转链表
题目链接
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;
}
};
双指针总结
- 对于数组，不真正删除，只覆盖，采用双指针
- 对于字符串，头尾双指针
- 对于链表，快慢双指针