C++知识点总结(8)：尺取法真题代码

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

一、最长连续小写子串

#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;
}

二、小于s的最短子串和

#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;
}

三、最长递增字串

#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;
}

四、最短包含所有小写字母子串的长度

#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;
}