C++知识点总结(8)：尺取法

本文主要是介绍C++知识点总结(8)：尺取法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、复习枚举算法

1. 算法三要素

【枚举对象】要枚举的对象
【枚举范围】每一个枚举对象从几开始，到几结束
【筛选条件】筛选满足一定条件的数据

2. 最小公倍数公式

假如现在要求整数 $a$ 和整数 $b$ 的最小公倍数。
求解公式如下：
$a\times b=gcd(a,b)\times lcm(a,b)$

3. 时间复杂度

一般指程序运行的最大次数，不能超过 $10^8$ ，即 $1e8$ ，时间复杂度越高，程序运行时间越长。

二、算法优化初级

1. 概念

通过针对题型的方式，来使算法的某一方面变得更强的过程（包括用时更短、空间更小）。

2. 例题

(1) 最长小写子串

【题目描述】

给定一个由若干大写小写字符组成的字符串 $str$ ，现在请你求出 $str$ 中最长的小写子串的长度。如果没有，则输出 $0$ 。

【输入描述】

1行，包含一个字符串 $str$ 。

【输出描述】

1行，包含最长小写子串的长度。

【样例1】

输入

abcdeACzxc

输出

5

【概念】

当串 a 中连续包含串 b 的所有元素时，
串 a 是串 b 的父串；
串 b 是串 a 的子串。
例如 $abcdefg$ 是 $cde$ 的子串。

Ⅰ 初步算法

for (int i = 0; i <= len-1; i++)
{for (int j = i; j <= len-1; j++){bool flag = true;for (int k = i; k <= j; k++){if (a[k] >= 'A' && a[k] <= 'Z'){bool flag = true;break;}}if (flag){// ...}}
}
// 打擂台...
// 输出...

Ⅱ 认识尺取法

尺取法，又称双指针法，是一种针对子串枚举问题的优化算法。
在上述题目中，可用用下面的伪代码来表示。

while (l < len) // 左指针没有到结尾
{if ((s[r] >= 'a' && s[r] <= 'z') && r < len) // 右指针在小写字母上并且不在结尾{r++;}erelse{max(..., r-l)l = r + 1;r = l;}
}

Ⅲ 尺取法程序

#include <iostream>
#include <string>
using namespace std;int main()
{// 输入string s;cin >> s;// 尺取法int len = s.length();int l = 0, r = 0; // l 表示左端点， r 表示右端点int maxlen = 0;while (l < len){if (s[r] >= 'a' && s[r] <= 'z' && r < len) // 右指针在小写字母上并且不在结尾{r++;}else{maxlen = max(maxlen, r-l);l = r + 1; // 移动左指针 r = l; // 右指针和左指针一起移动 }}// 输出cout << maxlen; return 0;
}

(2) 最长递增子串

#include <iostream>
#include <string> 
using namespace std;int main()
{// 输入int n, s[10005] = {};cin >> n;for (int i = 0; i <= n-1; i++){cin >> s[i];} // 尺取法int l = 0, r = 0, maxlen = 1;while (l < n){if (s[r] < s[r+1] && r < n){r++;}else{maxlen = max(maxlen, r-l+1);l = r + 1;r = l;}}// 输出cout << maxlen;return 0; return 0;
}

(3) 最小子串和

Ⅰ 伪代码

while (l < len)
{if (sum < 9 && r < len){sum += a[r];r++;}else{if (sum >= 9){// 更新 r-lsum -= a[l];l++;}}
}

Ⅱ 完整代码

#include <iostream>
using namepace std;int main()
{// 输入int n, s, a[10005] = {};cin >> n;for (int i = 0; i <= n-1; i++){cin >> a[i];}cin >> s;// 尺取法int l = 0, r = 0, minlen = 1e8, sum = 0;while (l < n){if (sum < s && r < n){sum += a[r];r++;}else{if (sum >= s){minlen = min(minlen, r-l);}sum -= a[l];l++;}}// 输出if (minlen == 1e8){cout << 0;}else{cout << minlen;}return 0;
}

(4) 最短字符串包含

Ⅰ 伪代码

while (l < len)
{if (sum <= 26 && r < len) // sum 表示出现了多少个不同的字母{cnt[s[r]]++;if (cnt[s[r]] == 1){sum++;}r++;}else{if (sum >= 26){minlen = min(minlen, );}cnt[s[l]]--;l++;}
}

Ⅱ 代码

#include <iostream>
#include <string>
using namespace std;int main()
{string s;cin >> s;int len = s.length();int l = 0, r = 0;int cnt[130] = {};int sum = 0;int minlen = 1e8;while (l < len){if (sum < 26 && r < len){cnt[s[r]]++;if (cnt[s[r]] == 1) sum++;r++;}else{if (sum >= 26){minlen = min(minlen, r-l);}cnt[s[l]]--;if (cnt[s[l]] == 0){sum--;}l++;}}cout << minlen;return 0;
}

这篇关于C++知识点总结(8)：尺取法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---