日野弥生：勉強しよう
two pointers
发表于2024年12月30日
介绍
双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。
过程I
使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇
实现
例如原地进行反转字符串：
class Solution {
public:
void reverseString(vector<char>& s) {
int i=0,j=s.size()-1;
while(i<j)
{
swap(s[i],s[j]);
i++;
j--;
}
}
};过程II
有时，我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow=0,fast=0;
for(;fast<nums.size();fast++)
{
if(nums[fast]!=val)
{
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
};链表中的双指针的注意事项
- 在调用next字段之前，始终检查节点是否为空。
获取空节点的下一个节点将导致空指针错误。例如，在运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
- 仔细定义循环的结束条件。
// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow && fast && fast->next) {
slow = slow->next; // move slow pointer one step each time
fast = fast->next->next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem