代码随想录之双指针刷题总结
目录
1.移除元素
2.反转字符串
3.替换数字
4.翻转字符串里的单词
5.翻转链表
6.删除链表的倒数第N个节点
7.链表相交.
8.环形链表||
9.三数之和
10.四数之和
该文是对前面的算法题中用到的双指针方法的题目进行罗列归纳
1.移除元素
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
思路：
数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
因此使用快慢指针(从下标0开始)，遇到目标数字快指针动，慢指针先暂停，没遇到就一起
注意：
明确指针的起始和移动
代码：
class Solution {
public:
int remove(vector<int>& nums, int val) {
int slowindex = 0;
int fastindex = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
nums[slowindex++] = nums[fastindex++];
}
else {
fastindex++;
}
}
return slowindex;
}
};2.反转字符串
题目描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：
左右指针，分别在两端，不断地交换即可
注意：
注意终止条件，也就是i<s.size()即可
代码：
class Solution {
void reverseString(vector<char>& s) {
int start = 0;
int end = s.size() - 1;
for (int i = start, j = end; i < s.size() / 2; i++, j--) {
swap(s[i], s[j]);
}
}
};3.替换数字
题目描述：
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为love。
例如，对于输入字符串 "a1b2"，函数应该将其转换为 "aloveblove"。
对于输入字符串 "a5b"，函数应该将其转换为 "aloveb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：alovebloveclove
思路：
双指针法，一个指向旧的还没扩充的末尾，一个指向新的扩充后的末尾，检测到数字进行填充即可
注意：
对数字的范围判定要写正确，不然会出错。
代码：
int main() {
string s;
while (cin >> s) {
int count = 0;
int oldindex = s.size() - 1;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
count++;
}
}
s.resize(s.size() + 3 * count);
int newindex = s.size() - 1;
//这里也可以写为
//while (oldindex >= 0);
for (int i = 0; i <=oldindex; i++) {
if (s[oldindex] >= '0' && s[oldindex] <= '9') {
s[newindex--] = 'e';
s[newindex--] = 'v';
s[newindex--] = 'o';
s[newindex--] = 'l';
}
else {
s[newindex--] = s[oldindex];
}
oldindex--;
}
cout << s << endl;
}
}4.翻转字符串里的单词
题目描述：
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个
思路：
分为两个步骤进行：
1.先对多余的空格进行去掉操作
2.将元素进行反转交换
注意：
对去空逻辑的处理要理解透彻，不要写错
去空和反转的顺序要搞清楚，反转的区间要搞清
代码：
class Solution {
public:
void Reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
void removeExtra(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); ++i) {
//错误写法
//if (oldindex != 0) s[oldindex++] = ' ';
//while (s[i] != ' ') {
// if (s[i] != ' ' && oldindex != 0) {
// s[oldindex] = s[i];
// }
// oldindex++;
//}
if (s[i] != ' ') {
if (slow != 0) s[slow++] = ' ';
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
//移除空格之后，数组的大小记得重新恢复一下
s.resize(slow);
}
string reversewords(string& s) {
removeExtra(s);
//根据下标翻转
Reverse(s, 0, s.size() - 1);
//赋值这个过程的顺序不要反了，是去除多余空格后的s
int start = 0;
int end = s.size();
for (int i = 0; i <= s.size(); ++i) {
if (s[i] == ' ' || i == end) {
Reverse(s, start, i - 1);
start = i + 1;
}
}
return s;
}
};5.翻转链表
题目描述：
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：
定义两个指针pre和cur，分别代表NULL，以及头节点，然后不断差序更新
注意：
记得提前保存好cur的下一个节点，因为cur指向改变了
代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = NULL;
while (cur) {
//此时记得要保存一下cur的下一个节点，因为接下来要改变指向
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return head;
}
};6.删除链表的倒数第N个节点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路：
定义fast指针和slow指针，初始值为虚拟头结点
fast指针先移动n步
快慢指针一起移动，直到慢指针移动到要删除的节点的前一个节点(这里是fast->NULL的时候)
注意：
注意内存的释放以及节点的处理
代码：
class Solution {
public:
ListNode* deleteList(ListNode* head, int n) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* slowindex = dummyhead;
ListNode* fastindex = dummyhead;
while (n--) {
fastindex = fastindex->next;
}
while (fastindex->next != NULL) {
fastindex = fastindex->next;
slowindex = slowindex->next;
}
ListNode* temp = slowindex->next;
slowindex->next = slowindex->next->next;
delete temp;
temp = nullptr;
return dummyhead->next;
}
};7.链表相交.
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
示例 2：
示例 3：
思路：
求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
然后curA和curB同时移动，直到curA=curB，或者未找到结果为NULL
注意：
比较的时候节点记得重新设置一下，因为指向改变了
代码：
class Solution {
public:
ListNode* listXiangjiao(ListNode* headA, ListNode* headB) {
int countA = 0;
int countB = 0;
ListNode* curA = headA;
ListNode* curB = headB;
while (curA != NULL) {
countA++;
curA = curA->next;
}
while (curB != NULL) {
countB++;
curB = curB->next;
}
if (countB - countA > 0) {
swap(countA, countB);
swap(headA, headB);
}
int cha = 0;
cha = countA - countB;
//确实需要重新设置
ListNode* newcurA = headA;
ListNode* newcurB = headB;
while (cha--) {
newcurA = newcurA->next;
}
while (newcurA != NULL && newcurB != NULL) {
if (newcurA == newcurB) {
return newcurA;
}
//不要忘记更新哦，不断地更新寻找
newcurA = newcurA->next;
newcurB = newcurB->next;
}
return NULL;
}
};8.环形链表||
题目描述：
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
思路：
首先需要判断环形链表，也就是定义快慢指针，快二慢一，然后若相等就有环
若有环，那么快慢指针相交的地方，以及head节点同时移动，相等的地方就是环的开始位置
注意：
注意while循环条件的限定，理解fast指针的含义
代码：
class Solution {
ListNode* huanxing(ListNode* head) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* slowindex = dummyhead->next;
ListNode* fastindex = dummyhead->next;
//while(1)循环是错误的，下面是正确的写法
while (fastindex!=NULL&&fastindex->next!=NULL) {
slowindex = slowindex->next;
fastindex = fastindex->next->next;
if (fastindex == slowindex) {
ListNode* beginindex = head;
while (beginindex != slowindex) {
beginindex = beginindex->next;
slowindex = slowindex->next;
}
return beginindex;
}
}
return NULL;
}
};9.三数之和
题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路：
首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
注意：
对三个元素的去重与剪枝处理要很明确，尤其是对nums的处理
在对左右指针处理的时候，最后一定要记得更新！！！！！！！
代码：
class Solution {
public:
vector<vector<int>> threeNum(vector<int>nums) {
vector<vector<int>> result;
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 leftindex = i + 1;
int rightindex = nums.size() - 1;
while (leftindex < rightindex) {
if (nums[i] + nums[leftindex] + nums[rightindex] < 0) leftindex++;
else if (nums[i] + nums[leftindex] + nums[rightindex] > 0) rightindex--;
else {
result.push_back(vector<int>{nums[i], nums[leftindex], nums[rightindex]});
while (leftindex < rightindex && nums[leftindex] == nums[leftindex + 1]) leftindex++;
while (leftindex < rightindex && nums[rightindex] == nums[rightindex - 1]) rightindex--;
//千万记得更新
leftindex++;
rightindex--;
}
}
}
return result;
}
};10.四数之和
题目描述：
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路：
和三数之和类似，只不过多了一个nums[j]元素，而且要进行两次剪枝处理
注意：
left一定是仅仅跟在第二个数组元素后面的，这个不要搞错，同时剪枝处理不能少，要深刻理解
代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int> nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0 && nums[i] >= target) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] > 0 && nums[i] + nums[j] >= target) break;
if (j > i+1 && nums[j] == nums[j - 1]) continue;
int leftindex = j + 1;
int rightindex = nums.size() - 1;
while (leftindex < rightindex) {
//此处应该加一个long，不然会溢出(整型溢出)
if ((long)nums[i] + nums[j] + nums[leftindex] + nums[rightindex] < target) leftindex++;
else if (nums[i] + nums[j] + nums[leftindex] + nums[rightindex] > target) rightindex--;
else {
result.push_back(vector<int>{nums[i], nums[j], nums[leftindex], nums[rightindex]});
while (leftindex < rightindex && nums[leftindex] == nums[leftindex + 1]) leftindex++;
while (leftindex < rightindex && nums[rightindex] == nums[rightindex - 1]) rightindex--;
leftindex++;
rightindex--;
}
}
}
}
return result;
}
};