Coding Practice，48天强训（26）
Topic 1：小红的ABC(回文串特性)
小红的ABC
#include <bits/stdc++.h>
using namespace std;
int main()
{// 回文的特性，只需要找长度为2和长度为3的子串，判断是否回文即可 aa aba 像afdgdfa里面也有一个dgd，只要是回文就只用考虑2和3的长度即可string s; cin >> s;int n = s.size(), res = -1;for(int i = 0; i < n-1; ++i){if (s[i] == s[i + 1]) return cout << (res = 2), 0; // 检查长度为2的回文,找到就是最小，直接返回,这输出括号还能这样写哈哈哈if (i < n - 2 && s[i] == s[i + 2]) res = 3; // 检查长度为3的回文，找到不一定是最小，后面可能还有2的，所以不立刻返回}return cout << res, 0;
}
Topic 2：不相邻取数(打家劫舍)
不相邻取数_牛客题霸da_牛客网
打家劫舍变体，老生常谈
#include <iostream>
using namespace std;int main()
{// 打家劫舍的变体，间隔房间不选// dp[i] : 0-i之间不相邻元素的最大价值// dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])int n; cin >> n;int nums[n], dp[n];for(int i = 0; i < n; ++i) cin >> nums[i];dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);for(int i = 2; i < n; ++i) dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);cout << dp[n - 1] << endl;
}当然，还有优化空间
#include <iostream>
using namespace std;int main()
{int n; cin >> n;int nums[n];for(int i = 0; i < n; ++i) cin >> nums[i];if (n == 1) return cout << nums[0] << endl, 0;// 剪枝，1个元素直接返回int prev2 = nums[0], prev1 = max(nums[0], nums[1]);// 实际上，每次计算 dp[i] 时，只依赖于 dp[i-1] 和 dp[i-2]。因此，你不需要维护整个 dp 数组，两个变量就可以解决问题，从而减少空间复杂度。for(int i = 2; i < n; ++i) {int current = max(prev1, prev2 + nums[i]);prev2 = prev1;prev1 = current;}cout << prev1 << endl;
}
这个简洁度，理解，看着就舒服
Topic 3：空调遥控(滑动窗口)
G-空调遥控_牛客小白月赛40
#include <bits/stdc++.h>
using namespace std;int main()
{int n, p; cin >> n >> p;vector<int> a(n);for(int i = 0; i < n; ++i) cin >> a[i];sort(a.begin(), a.end());int ret = 0, tmp = 0;for(int k = a[n - 1]; k > 0; --k){ret = max(ret, tmp);tmp = 0;for(int j = 0; j < n; ++j){if(abs(a[j] - k) <= p) tmp++;}}cout << ret;return 0;
}暴力一下，超时，改进一下，用二分处理
#include <bits/stdc++.h>
using namespace std;int main()
{int n, p; cin >> n >> p;vector<int> a(n);for(int i = 0; i < n; ++i) cin >> a[i];sort(a.begin(), a.end());// 排序温度诉求int res = 0;for(int i = 0; i < n; ++i)// 用每个队员的喜好温度作为k值，查找[k + p, k - p]这个温差区间内的人数，输出最多的那个{int low = a[i] - p;// 当前温度的最低温差int high = a[i] + p;// 最高温差int l = lower_bound(a.begin(), a.end(), low) - a.begin();int r = upper_bound(a.begin(), a.end(), high) - a.begin();//lower_bound 找到第一个不小于(大于等于) low 的位置（区间左边界）//upper_bound 找到第一个大于 high 的位置（区间右边界）res = max(res, r - l); //右边界用了upper这里相减就不用+1了，因为右边是开区间}cout << res << endl;return 0;
}
手搓一下lower_bound 和 upper_bound，复习二分
int lower_bound(vector<int>& a, int target)// 找第一个 >= target 的位置
{int left = 0, right = a.size(); // 注意是右开区间 [left, right)while (left < right) {int mid = (left + right) / 2;//二分if (a[mid] >= target) right = mid; // 二分后都还>=,很可能在左边，right往左来到之前mid的位置，缩小范围else left = mid + 1; //二分mid比target小，left走到之前mid的后一位，缩小范围}return left; // 不断缩小范围，最后left就是第一个 >= target 的位置
}}
int upper_bound(vector<int>& a, int target) //找第一个 > target 的位置
{int left = 0, right = a.size(); // 还是右开区间while (left < right) {int mid = (left + right) / 2;if (a[mid] > target) right = mid; //和lower基本类似，就是这里>=改成了>else left = mid + 1;}return left; // 最后left就是第一个 > target 的位置
}再改改来个终极版，滑动窗口，首先理清楚一个条件——2p
最终的滑动窗口就是这样啦：
#include <bits/stdc++.h>
using namespace std;int main()
{int n, p; cin >> n >> p;vector<int> a(n);for(int i = 0; i < n; ++i) cin >> a[i];sort(a.begin(), a.end());// 排序温度诉求int l = 0, res = 0;for(int r = 1; r < n; ++r)// 控制r不断扩大符合<=2p条件的窗口{while(a[r] - a[l] > 2 * p) l++;//走到一定位置发现最左边的l>2p,没有温度交集了，不能一起愉快的训练了// 循环去控制l右移，把不能一起训练的排除，直到能忍受当前温度l停止res = max(res, r - l + 1);// 找到所有这些组合里面人最多的那个保存}cout << res << endl;return 0;
}