一、復習枚舉算法

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