Acwing-基础算法课笔记之基础算法（双指针）
Acwing-基础算法课笔记之基础算法（双指针）
- 一、双指针算法概念
- 二、关于双指针的一个问题
- 三、模板
一、双指针算法概念
双指针（又称尺取法）是一个常用的优化技巧，用来解决序列的区间问题。
两个指针i，j，有两种扫描方向：
1、反向扫描：i、j方向相反，i从头到尾，j从尾到头，在中间相会。
2、同向扫描：i、j方向相同，都从头到尾，可以让j跑在i前面。
同向扫描的两个指针称为“快慢指针”，快慢指针在序列上产生一个大小可变的“滑动窗口”，有灵活性应用。
二、关于双指针的一个问题
问题描述：将单词abc def ghi按列输出出来
输出结果：
abc
def
ghi
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main() {
char str[100];
gets(str);
int n = strlen(str);
for (int i = 0; i < n; i ++) {
int j = i;
while (j < n && str[j] != ' ') { // 找当前单词的最后一个位置
j ++
}
// 这道问题的具体逻辑
for (int k = i; k < j; k ++) cout << str[k];
cout << endl;
i = j;
}
}
三、模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作