本次作业完成了力扣《面试经典 150 题》「双指针」部分的全部题目，并参加了 Educational Codeforces Round 158 (Rated for Div. 2)，赛时通过 A ~ D 四题，排名 919 / 21392（参赛用户名为 _zsq）。
力扣 面试经典 150 题 - 双指针
LeetCode 125. 验证回文串
思路
双指针，从两端向中间遍历，遇到非字母数字的字符则跳过，字母或数字字符需要先通过 tolower 函数转换为小写字母再进行比较。
代码
提交记录：4 ms (93.16%) / 7.35 MB (52.06%)
class Solution {
public:
bool isPalindrome(string s) {
for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
while (!isalpha(s[i]) && !isdigit(s[i]) && i < j) ++i;
while (!isalpha(s[j]) && !isdigit(s[j]) && i < j) --j;
if (i < j && tolower(s[i]) != tolower(s[j])) return false;
}
return true;
}
};
LeetCode 392. 判断子序列
思路
如果 s 是 t 的子序列，则 s 的每个字符都在 t 中出现，且相对顺序不变。因此可以使用双指针，分别指向 s 和 t 的开头，然后向后遍历，如果 s 的字符在 t 中出现，则 s 的指针向后移动，否则 t 的指针向后移动。如果 s 的指针移动到末尾，则说明 s 是 t 的子序列。
代码
提交记录：0 ms (100.00%) / 6.32 MB (74.99%)
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0;
for (int j = 0; i < s.length(), j < t.length(); j < t.length() && ++i, ++j) while (s[i] != t[j] && j < t.length()) ++j;
return i == s.length();
}
};
LeetCode 167. 两数之和 II - 输入有序数组
思路
因为数组是有序的，所以可以使用双指针，分别指向数组的开头和结尾，然后向中间遍历，如果两个指针指向的数字之和大于目标值，则尾指针向前移动，否则头指针向后移动。因为答案存在且唯一，所以找到答案后直接返回即可。
代码
提交记录：4 ms (99.47%) / 15.17 MB (60.09%)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
for (int i = 0, j = numbers.size() - 1;; numbers[i] + numbers[j] > target ? --j : ++i) if (numbers[i] + numbers[j] == target) return {i + 1, j + 1};
}
};
LeetCode 11. 盛最多水的容器
思路
双指针，分别指向数组的开头和结尾，然后向中间遍历，每次计算当前两个指针指向的数字组成的容器的容量，然后更新答案。因为容器的容量取决于两个指针指向的数字中较小的那个，所以每次移动较小的那个指针，能够保证答案尽量大，直到两个指针相遇。
代码
提交记录：60 ms (97.48%) / 56.61 MB (41.16%)
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0;
for (int l = 0, r = height.size() - 1; l < r; height[l] > height[r] ? --r : ++l) ans = max(ans, min(height[l], height[r]) * (r - l));
return ans;
}
};
LeetCode 15. 三数之和
思路
先对数组进行排序，然后我们可以先确定第一个数作为三个数中的最小值，然后便可以转化为在剩下的数组中寻找两个数之和等于第一个数的相反数的问题。因为数组已经排序，所以可以使用双指针，分别指向第一个数的后一个数和数组的最后一个数，然后向中间遍历，如果两个指针指向的数字之和大于目标值，则尾指针向前移动，否则头指针向后移动。因为答案存在且唯一，所以找到答案后直接返回即可。唯一需要注意的是，因为答案中不能包含重复的三元组，所以在确定一个数后，如果该位置的数和前一个数相同，则跳过。
代码
提交记录：120 ms (67.35%) / 23.28 MB (39.64%)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0, lst = -1e5 - 7; i < nums.size(); ++i) {
if (nums[i] == lst) continue; else lst = nums[i];
for (int j = i + 1, lst = -1e5 - 7, k = nums.size() - 1, t = -nums[i]; j < nums.size() && j < k; ++j) {
if (nums[j] == lst) continue; else lst = nums[j];
while (nums[j] + nums[k] > t && j < k) --k;
if (j < k && nums[j] + nums[k] == t) ans.push_back({-t, nums[j], nums[k]});
}
}
return ans;
}
};
Educational Codeforces Round 158 (Rated for Div. 2)
CF1901A. Line Trip
题意
有一条长为 $x$ 的路，路上有 $n$ 个加油站，驾驶汽车从 $0$ 出发到 $x$ 再回到 $0$，每单位长度耗油 $1L$ ，遇到加油站便可以加满油箱，问至少需要多大的油箱才能完成行程。
思路
因为遇到加油站便可以加满油，因此只要油箱比任意两个加油站之间的距离都大即可。需要注意的是，因为需要折返，所以需要特别计算从最后一个加油站到 $x$ 再回到最后一个加油站的距离。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int t, n, a[maxn], x;
int main()
{
for (scanf("%d", &t); t--; )
{
scanf("%d%d", &n, &x);
int ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
ans = max(ans, a[i] - a[i - 1]);
}
ans = max(ans, x - a[n] << 1);
printf("%d\n", ans);
}
return 0;
}
CF1901B. Chip and Ribbon
题意
有 $n$ 个格子，每个格子都包含一个整数 $0$。最开始指针指向第一个格子，每次操作可以将指针向右移动 $1$ 格，或将指针传送到任意单元格。最开始以及每次操作后，指针指向的格子的值都会增加 $1$，问至少需要多少次传送操作才能使格子与目标值 $c_i$ 相等。
思路
因为题目想要让传送次数最少，因此每次传送后都应该尽可能多地让指针向右移动。不难发现，传送的目的地总是应该是目标值比左边大的格子，而为了让每次传送后指针尽可能多地向右移动，则传送次数至少为该格子与左边格子目标值之差（左边格子目标值的部分可以在前面向右移动指针来覆盖）。因此，只需要计算所有目标值比左边格子大的格子与左边格子目标值之差的和即可。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int t, n, a[maxn];
int main()
{
for (scanf("%d", &t); t--; )
{
scanf("%d", &n);
long long ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if (a[i] > a[i - 1]) ans += a[i] - a[i - 1];
}
printf("%lld\n", ans - 1);
}
return 0;
}
CF1901C. Add, Divide and Floor
题意
给定 $n$ 个整数，每次操作将所有数加任意整数 $x$ 然后除以 $2$ 并向下取整（即将 $a_i$ 替换为 $\lfloor {a_i + x \over 2} \rfloor$），问至少需要多少次操作才能使所有数相等。输出最少操作次数以及每次操作的 $x$，如果操作次数 $\ge n$，则无需输出 $x$。
思路
不难发现，我们只需要让所有数中的最大值和最小值经过若干次操作相等即可。那么目标就转化为了通过尽可能少的操作让最大值和最小值差值变成 $0$，贪心地想，便是每次操作都让最大值和最小值的差值减少尽可能多。而我们又容易发现，每次操作后最大值和最小值的差值减少量只有两种情况，即 $x$ 为奇数和偶数的情况。因此，我们只需要计算两种情况下的差值减少量，然后取减少量较大的那个即可。
代码
_case = int(input())
for _ in range(_case):
n = int(input())
a = list(map(int, input().split()))
mi = min(a)
ma = max(a)
ans = []
while mi != ma:
if (ma + 1 >> 1) - (mi + 1 >> 1) < (ma >> 1) - (mi >> 1):
ans.append(1)
mi = mi + 1 >> 1
ma = ma + 1 >> 1
else:
ans.append(0)
mi = mi >> 1
ma = ma >> 1
print(len(ans))
if n >= len(ans) > 0:
print(' '.join(map(str, ans)))
CF1901D. Yet Another Monster Fight
题意
有 $n$ 个怪物，第 $i$ 个怪物的生命值为 $a_i$。现在希望用一发魔法带走所有怪物。该魔法需要选取一个怪物 $i$，然后对该怪物造成 $x$ 点伤害，然后再随机选择一个已经被击中怪物旁边未被击中的怪物，对其造成 $x - 1$ 点伤害，然后再随机选择一个已经被击中怪物旁边未被击中的怪物，对其造成 $x - 2$ 点伤害……以此类推，直到击中所有怪物。问 $x$ 至少是多少才能只用一发魔法就一定能带走所有怪物。
思路
魔法的伤害是一个差值为 $1$ 的递减数列，因为被攻击的怪物只会是已被击中怪物旁边未被击中的怪物，因此当 $i$ 被确定后，所有怪物可能受到的伤害最小值也可以确定。因此，我们只需要枚举 $i$，计算使得所有怪物可能受到的伤害最小值都大于等于生命值的 $x$，然后保留所有 $i$ 对应 $x$ 的最小值即可。
具体来说，对于从编号为 $t$ 的怪物开始的攻击，第 $i (i < t)$ 个怪物可能收到的伤害最小值为 $x - n + i$，第 $i (i > t)$ 个怪物可能收到的伤害最小值为 $x + 1 - i$。因此对于所有 $i < t$ 的怪物都要有 $x - n + i \ge a[i] \Rightarrow x \ge a[i] + n - i$，对于所有 $i > t$ 的怪物都要有 $x + 1 - i \ge a[i] \Rightarrow x \ge a[i] + i - 1$，注意到 $a[i] + n - i$ 的前缀最大值和 $a[i] + i - 1$ 的后缀最大值会被使用多次，因此我们可以预处理出这两个值，然后枚举 $i$，计算 $x$ 的最小值即可。
代码
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 3e5 + 7;
int n, a[maxn], ma[maxn], mb[maxn];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ma[i] = max(ma[i - 1], a[i] + n - i);
for (int i = n; i >= 1; --i) mb[i] = max(mb[i + 1], a[i] + i - 1);
int ans = max(a[1], mb[2]);
for (int i = 2; i <= n; ++i) ans = min(ans, max(a[i], max(ma[i - 1], mb[i + 1])));
printf("%d\n", ans);
return 0;
}
