尺取法
程序员文章站
2022-06-04 16:06:55
...
首先要感谢蒋ls提供的图片,这个是他的网站,欢迎访问。传送门
一、简介:
-
尺取法,通俗的来讲,就是双指针法。
-
为什么叫做尺取法呢??借用挑战书程序上面的话来水说,尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。
-
尺取法比暴力枚举要高效的多,一般情况暴力枚举需要O(n^2)的复杂度,则尺取法就用O(n*log n)的复杂度。
二、选用尺取法的情况:
- 通常适用于所选取的区间具有一定的规律,如单调性。
- 其次,我们能知道对当前区间进行判断之后,指针如何进行改变。
- 尺取法,在一般情况下需要对某些量进行预处理,以便更快速得到答案。
三、尺取法的两种选择:
1、左右指针:两个指针反向扫描,一个在最左端,一个在最右端。
2、快慢指针:两个指针同向,但是指针的移动快慢速度不同。
图示法:第一行是左右指针,第二行是快慢指针。
四、尺取法一般情况下的步骤:
- 对于给定的一个序列,对其进行排序(根据题目再定)。
- 预处理,比如:有的时候要进行前缀和操作。
- 设立双指针,i ,j ,再根据题意选定合适的尺取法。
五、小运用:
1、用尺取法进行数组的去重(快慢指针):
sort(num + 1, num + n + 1); //必须是有序的
for (int i = 1, j = 0; i <= n; i++) //i是快指针,j是慢指针
{
if (num[i] == num[i + 1])
num[++j] = num[i];
}
六、实战应用+题解:
1、POJ 3061 Subsequence
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = 1e5 + 5;
int ans = 0x3f3f3f;
int sum[maxn], num;
int main()
{
int t;
while (~scanf("%d", &t))
{
while (t--)
{
int n, s;
memset(sum, 0, sizeof(sum));
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i++)
{
scanf("%d", &num);
sum[i] = sum[i - 1] + num; //前缀和
}
int ans = 0x3f3f3f;
bool flag = 0;
for (int i = 0, j = 1; i <= n && j <= n;)//快慢指针尺取法,j是快指针
{
if (sum[j] - sum[i] >= s)//符合情况,取答案
{
ans = min(ans, j - i);
++i;
flag = 1;
}
else//不符合,移动
++j;
}
if (flag)
printf("%d\n", ans);
else
printf("0\n");
}
}
return 0;
}
2、LintCode 415 有效回文串
要求O(n)得出。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
int main()
{
ios::sync_with_stdio(false);
string s;
getline(cin, s);
int l = 0, r = s.size();
bool flag = 0;
if (r == 0)
puts("true");
else
{
r--;
for (int i = 0; i <= r; i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] = s[i] - 'A' + 'a';
else if (s[i] >= 'a' && s[i] <= 'z')
continue;
else
s[i] = ',';
}
while (l < r)
{
if (s[l] == ',')
++l;
else if (s[r] == ',')
--r;
else if (s[l] == s[r])
{
++l;
--r;
}
else
{
flag = 1;
break;
}
}
if (flag)
puts("false");
else
puts("true");
}
return 0;
}
上一篇: php中引用符号(&)的使用详解_PHP