c语言使用指针的基本原则：双指针之快慢指针
c语言使用指针的基本原则：双指针之快慢指针// 快慢指针 L = 0 R = 0 while 没有遍历完 if 一定条件 L = 1 R = 1 return 合适的值典型实例：步长不等的快慢指针是指针使用两个步长不同的指针，通常快指针用于读，慢指针用于写。I 步长不等的快慢指针（两个指针步长不同），如用来排除重复元素。II 左右端点指针（两个指针分别指向头尾，并往中间移动，步长不确定），如实现二分查找。III 步长相等的快慢指针（两个指针间距相同，步长相同），如一次遍历（OnePass）求链表的中点或求单链表的倒数第k个元素。
遍历是实现许多算法的基本操作。遍历数据或链表通常通过指针（或索引）在循环内实现指针的移动来进行。
我们遍历一个数组，并输出数组每一项，我们需要一个指针来记录当前遍历的项，这个指针我们可以叫单指针（index）。在某些情况下，可能使用两个这样的指针来遍历更方便问题求解，称为双指针。
伪代码：
// 单指针
for(int i = 0;i < nums.size(); i ) {
输出(nums[i]);
}
// 双指针
int L = 0;
int R = nums.size() - 1;
while (L < R) {
if(一定条件)
return 合适的值，一般是 L 和 R 的中点
if(一定条件) L
if(一定条件) R--
}
// 因为 L == R 因此返回 I 和 R 都是一样的
return L
双指针是指对数据结构（如数组和链表）使用两个指针或两个索引来操作数据，其策略一般有：
I 步长不等的快慢指针（两个指针步长不同），如用来排除重复元素。
II 左右端点指针（两个指针分别指向头尾，并往中间移动，步长不确定），如实现二分查找。
III 步长相等的快慢指针（两个指针间距相同，步长相同），如一次遍历（OnePass）求链表的中点或求单链表的倒数第k个元素。
1 步长不等的快慢指针步长不等的快慢指针是指针使用两个步长不同的指针，通常快指针用于读，慢指针用于写。
// 快慢指针
L = 0
R = 0
while 没有遍历完
if 一定条件
L = 1
R = 1
return 合适的值
典型实例：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1：
给定 int nums[] = {1 1 1 2 2 3};
函数应返回新长度 length = 5 并且原数组的前五个元素被修改为 1 1 2 2 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2：
给定 int nums[] = {0 0 1 1 1 1 2 3 3};
函数应返回新长度 length = 7 并且原数组的前五个元素被修改为 0 0 1 1 2 3 3 。
你不需要考虑数组中超出新长度后面的元素。
实际上这种问题可以更抽象一步，即“删除排序数组中的重复项，使得相同数字最多出现 k 次” 。 那么这道题 k 就是 2，如果 k 为 1，则是删除重复元素。。
- 初始化快慢指针 slow ， fast ，全部指向索引为 0 的元素。
- fast 每次移动一格
- 慢指针选择性移动，即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
- 如果一致，我们不应该写。 否则我们就得到了三个相同的数字，不符合题意。
- 如果不一致，我们需要将 fast 指针的数据写入到 slow 指针。
- 重复这个过程，直到 fast 走到头，说明我们已无数字可写。
图解（红色的两个数字，表示我们需要比较的两个数字）：
code:
#include <stdio.h> // 快慢指针（读写指针）
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums int k) {
int i = 0;
for(int j=0;j<nums.size();j )
if (i < k || nums[j] != nums[i - k]) {
nums[i] = nums[j];
i ;
}
return i;
}
};
template <typename TT>
void print(TT tt int n)
{
for(int i=0;i<n;i )
printf("%d " tt[i]);
printf("\n");
}
int main()
{
int nums[] = {0 0 1 1 1 1 2 3 3};
int size = sizeof nums / sizeof *nums;
vector<int> vc(nums nums size);
Solution st;
int n = st.removeDuplicates(vc 2);
print(nums size);
print(vc n);
vector<int> vc2(nums nums size);
n = st.removeDuplicates(vc2 1);
print(vc2 n);
getchar();
return 0;
}
/*
0 0 1 1 1 1 2 3 3
0 0 1 1 2 3 3
0 1 2 3
*/2 左右端点指针
两个指针分别指向头尾，并往中间移动，步长不确定。
// 左右端点指针
L = 0
R = n - 1
while L < R
if 找到了
return 找到的值
if 一定条件1
L = 1
else if 一定条件2
R -= 1
return 没找到
典型实例：二分查找：
先定义搜索区间（非常重要）
根据搜索区间定义循环结束条件
取中间元素和目标元素做对比（目标元素可能是需要找的元素或者是数组第一个，最后一个元素等）（非常重要）
根据比较的结果收缩区间，舍弃非法解（也就是二分）
如果是整体有序通常只需要nums[mid]和target比较即可。如果是局部有序，则可能需要与其周围的特定元素进行比较。
code:
#include <stdio.h>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums int target){
if(nums.size() == 0)
return -1;
int left = 0 right = nums.size() - 1;
while(left <= right){
int mid = left ((right - left) >> 1);
if(nums[mid] == target){ return mid; }
// 搜索区间变为 [mid 1 right]
else if(nums[mid] < target)
left = mid 1;
// 搜索区间变为 [left mid - 1]
else
right = mid - 1;
}
return -1;
}
int main()
{
int arr[] = {1 2 3 4 5 6 7};
vector<int> vc(arr arr 7);
printf("%d\n" binarySearch(vc 5));
getchar();
return 0;
}
回文验证：
#include <stdio.h>
#include <string>
using namespace std;
bool isPalindrome(string s) {
if (s.empty())
return true;
const char* left = s.c_str();
const char* end = left s.length() - 1;
while (end > left) {
if (!isalnum(*left)) { left; continue;}
if (!isalnum(*end)) {--end; continue;}
if (tolower(*left) != tolower(*end)) return false;
else {--end; left;}
}
return true;
}
int main()
{
string s = "20122102";
string t = "abcabc";
printf("%d %d\n" isPalindrome(s) isPalindrome(t));
getchar();
return 0;
}3 步长相等的快慢指针
两个指针步长相同。
// 步长相等的快慢指针
L = 0
R = k
while没有遍历完
自定义逻辑
L = 1
R = 1
return 合适的值
典型实例：利用固定间距指针寻找链表中点
利用两个指针fast、slow同时指向头节点，fast指针每次走两步，slow指针每次走一步，当fast指针到达链表尽头时，slow指针就处于链表中点处。
Node* middle(Node* head)
{
Node* fast *slow;
fast = slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow; //slow即在中间位置
}
如果链表长度是奇数时，此时slow 正好为中点，如果为偶数，那么slow位置是中间偏右。
典型实例：一次遍历（OnePass）求单链表的倒数第k个元素：
#include<stdio.h> // 一次遍历（OnePass）求单链表的倒数第k个元素
#include<stdlib.h>
typedef struct Node
{
int num;
Node *next;
}Linklist;
Linklist * creat_linklist(); //尾插法创建含有头结点的单链表
int Search_K(Linklist *h int k) //双指针算法查找节点
{
Linklist *fast = h->next;
Linklist *slow = h->next;
int count = 0; // 计数器
while(fast!=NULL)
{
fast = fast->next;
if(count < k)
count ;
else
slow = slow->next;
}
if(count < k) //如果K大于链表的长度情况
{
printf("您要查找的节点不存在！");
return 0;
}
else
{
printf("倒数第%d个节点的数据为：%d\n" k slow->num);
printf("*** 查找完成！***");
return 1;
}
}
Node* middle(Node* head)
{
Node* fast *slow;
fast = slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow; //slow即在中间位置
}
void print(Linklist* head)
{
while(head->next != NULL)
{
printf("%d " head->next->num);
head = head->next;
}
printf("%\n");
}
int main()
{
int k;
Linklist *head;
head = (Linklist *)malloc(sizeof(Linklist));
head = creat_linklist();
print(head);
printf("中间节点是：%d\n" *middle(head));
printf("请输入要查找的倒数第几个节点：");
scanf("%d" &k);
Search_K(head k);
while(1);
return 0;
}
Linklist * creat_linklist()
{
int n=0 t=1;
Linklist *h *p *q;
h = q =(Linklist *)malloc(sizeof(Linklist));
for(int i=0;i<100;i )
{
p = (Linklist *)malloc(sizeof(Linklist));
p->num = i 1;
q->next = p;
q = p;
}
q->next = NULL;
return h;
}
在一些场合还需要考虑使用三个指针，如链表逆转：
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while(cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
ref:
https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/two-pointers
-End-
