提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 5.1 移除元素(3.30)
- 5.2 翻转字符串(3.30)
- 5.3 替换数字(3.30)
- 5.4 翻转字符串里的单词(3.31)
- 5.5 翻转链表(3.31)
- 5.6 删除链表的倒数第N个节点(3.31)
- 5.7 链表相交(3.31)()
- 5.8 环形链表II(4.3)()
- 5.9 三数之和(4.3)()
- 5.10 四数之和(4.3)()
- 5.11 双指针总结
前言
提示:这里可以添加本文要记录的大概内容:
5.1 移除元素(3.30)
5.2 翻转字符串(3.30)
5.3 替换数字(3.30)
//扩充字符串s的大小,每个数字替换成number
s.resize(s.size()+count*5);
#include<iostream>
#include<string>
using namespace std; //注意分号
if (s[j] > '9' || s[j] < '0') { //这里是 或
s[i] = s[j];
}
5.4 翻转字符串里的单词(3.31)
注意增删空格之后要重新设置字符串的大小
s.resize(j)
翻转每个单词的循环中,i应该≤s.size(),不能忘了=,否则最后一个单词无法翻转
翻转每个单词时,判断if(s[i]’ '|| is.size())
5.5 翻转链表(3.31)
不需要虚拟头结点
返回的是 pre,因为翻转之后pre是头结点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//定义一个虚拟头结点,不然还要处理头结点和非头结点的区别
//不需要虚拟头结点
ListNode* cur=head;
ListNode* pre=NULL;
ListNode* temp;
while(cur){
temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
5.6 删除链表的倒数第N个节点(3.31)
1、链表总长度固定
2、 slow和fast起始位置都在虚拟头结点,那么fast先走n+1,然后slow和fast同时移动,直到fast是NULL,此时slow还余下n+1个节点没有走,那么此时slow就在要删除节点的前一个节点,也就是倒数第n+1个节点
3、 ListNode* temp=slow->next;
slow->next=slow->next->next;
delete temp; //C++需要手动释放内存
虚拟头结点
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
5.7 链表相交(3.31)()
1、求出两个链表长度的差值
2、curA移动到和curB末尾对齐的位置
3、此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点。否则循环退出返回空指针。
if(coutA<coutB){ //保证A是最长的
swap(cura,curb); //交换的是当前指针,不是headA,headB
swap(coutA,coutB);
}
5.8 环形链表II(4.3)()
之前的分析
5.9 三数之和(4.3)()
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
这句话是将三个数nums[i], nums[left], nums[right]作为一个vector对象添加到result向量中。这样做的目的是将这三个数作为一个整体保存起来,方便后续的处理和操作。
// 错误去重a方法,将会漏掉-1,-1,2 这种情况,当遍历到第一个-1 的时候,判断 下一个也是-1,那这组数据就pass了
if (nums[i] == nums[i + 1]) {
continue;
}