Leetcode Weekly Contest #133 (1029-1032) 思路与题解
这篇文章首先写上我自己做这周 Weekly Contest 的思路，可能会比较菜，日后看了大神的解法可能会更新。
本周的题共四道，分别是：
- Matrix Cells in Distance Order (4)
- Two City Scheduling (4)
- Maximum Sum of Two Non-Overlapping Subarrays (5)
- Stream of Characters (7)
较为艰难地 AK 了...，错误提交一堆，不过好在结果还是全做完了。
大佬们有什么想法欢迎与本菜鸡交流，谢谢（
1030. Matrix Cells in Distance Order
题目大意
输入一个 R, C, r0, rc 表示一个 R x C 的矩阵和一个给定坐标 (r0, c0)，要求按距离顺序输出这个矩阵中的所有坐标（距离相等的点之间的顺序任意均可），返回值是 vector<vector<int>> 类型，距离的定义为 |r1 - r2| + |c1 - c2|。
思路
因为数据量不大（题目说 R, C 取值范围在 100 以内），直接暴力即可（所有点插入结果数组，然后排序）。
代码
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> result;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
result.emplace_back(vector<int>({i, j}));
}
}
sort(result.begin(), result.end(), [r0, c0](const vector<int> &a, const vector<int> &b) {
return abs(a[0] - r0) + abs(a[1] - c0) < abs(b[0] - r0) + abs(b[1] - c0);
});
return result;
}
};1029. Two City Scheduling
题目大意
假设有 2 个城市，输入 2N 个有 2 个元素的数组对，分别代表第 i 个人前往 2 个城市的 cost，要求给每个城市分配 N 个人使得总 cost 最小，输出这个 cost。
思路
好像和运筹学里面的规划问题有点类似（
首先把所有人排序，排序依据为：前往两个城市的 cost 差值越大，顺序越前
然后按顺序检索，取两个城市中 cost 较小的一个分配过去，如果那个城市满了那就分配到另一个。
代码
写的时候一开始想把判断条件写到一起，然后就错了...干脆写多了几个 if，看起来也清楚一些
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
sort(costs.begin(), costs.end(), [](const vector<int> &a, const vector<int> &b) {
return abs(a[0] - a[1]) > abs(b[0] - b[1]);
});
int i = 0, j = 0, n = costs.size();
int cost = 0;
for (auto it: costs) {
if (it[0] < it[1]) {
if (i < n / 2) {
++i;
cost += it[0];
} else {
++j;
cost += it[1];
}
} else {
if (j < n / 2) {
++j;
cost += it[1];
} else {
++i;
cost += it[0];
}
}
}
return cost;
}
};1031. Maximum Sum of Two Non-Overlapping Subarrays
题目大意
给定一个非负数组以及两个正数 L, M，保证这两个数加起来小于等于数组的总长度。
要求找到两个没有重合部分的连续子数组，子数组长度分别为 L, M，要求子数组的和最大，输出这两个子数组和。
思路
因为数据量也不是特别大，先跑两遍 dp 把以位置 i 结束的长度为 L, M 的数组和求出来，然后暴力（
代码
我写这里的时候因为复制粘贴，变量名有地方忘了改，还以为是判断条件写错了（x，然后换了另一种判断条件之后才发现是变量名写错了...
总之我这个代码中是直接避开了重合部分扫描的，还有一种做法是用下标判断是否有重合，有就 continue（我一开始是这么写的然后改成了现在这种写法）
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
vector<int> dpL(A.size());
vector<int> dpM(A.size());
dpM[0] = dpL[0] = A[0];
for (int i = 1; i < A.size(); ++i) {
if (i < L) {
dpL[i] = dpL[i - 1] + A[i];
continue;
}
dpL[i] = A[i] + dpL[i - 1] - A[i - L];
}
for (int i = 1; i < A.size(); ++i) {
if (i < M) {
dpM[i] = dpM[i - 1] + A[i];
continue;
}
dpM[i] = A[i] + dpM[i - 1] - A[i - M];
}
for (auto it: dpL) cout << it << ", ";
cout << endl;
for (auto it: dpM) cout << it << ", ";
cout << endl;
int result = 0;
for (int i = L - 1; i < dpL.size(); ++i) {
for (int j = M - 1; j < i - L + 1; ++j)
result = max(result, dpL[i] + dpM[j]);
for (int j = i + M; j < dpM.size(); ++j) {
result = max(result, dpL[i] + dpM[j]);
}
}
return result;
}
};1032. Stream of Characters
题目大意
实现一个 StreamChecker，测评程序会先用一个 vector<string> 单词表实例化它，然后调用若干次 query(char)，返回值为 bool。
对于每次调用，如果存在某个 k >= 1 使得过去的 k 次 query 组成的字符串刚好和单词表里的某个单词匹配，则返回 true。
这道题算压轴（？
但是跟 ACM 还有 OI 的题比起来好像还是太菜了，总之是我太菜了
思路
意思就是后缀匹配，但是暴力肯定会 TLE（于是试了一下果然 TLE 了），我一共尝试了两种暴力，一种是直接存下所有单词表内单词长度的后缀，TLE 了之后改为了只存单词表内最长长度的后缀，匹配的时候再取后面的部分（当然不可能这么改一下就过的）
后来稍微想了一下想到了 KMP，但是普通的 KMP 匹配也是 O(n) 的复杂度，但我感觉这个动态的流处理的过程是可以使用 KMP 的一些经验的，也就是所谓的 “先验知识” 那一块思路，不过因为我太菜了所以没想出来，下面是我的解决方法。
想到了之前看字符串匹配算法时看到的 RK 算法，思路大概就是在匹配字符串时将模式串转换为一个 hash，然后在目标串中动态构造这个 hash，先进行 hash 的匹配，然后再执行字符的匹配。
所以这道题我尝试也来维护一个 hash，对于单词表里的每一个单词（因为不会变），构造的时候计算出 hash。
然后在 query 的过程中，维护后缀长度为 len[i] 的 lastHash[]，其中 len[i] 为第 i 个单词的长度。
执行匹配的过程中先比较 hash，再进行匹配。
（因为导致 TLE 的输入 query 有很多相同的字母，甚至还有交替出现，直接匹配的时候可能会经常在字符串的末尾附近才匹配失败，而用 hash 的话可以首先保证模式串和目标串的组成大体相同，可以说极大的节约了计算时间）
代码
class StreamChecker {
public:
vector<string> &wrds;
vector<int> hash;
vector<int> lastHash;
vector<int> lens;
int len;
string last;
StreamChecker(vector<string>& words) : wrds(words), hash(words.size()), lens(words.size()), lastHash(words.size()) {
for (int i = 0; i < words.size(); ++i) {
lens[i] = words[i].size();
len = max(len, (int)words[i].size());
int h = 0;
for (auto it : words[i]) {
h += it - 'a';
}
hash[i] = h;
}
}
bool query(char letter) {
for (int i = 0; i < wrds.size(); ++i) {
if (last.size() >= lens[i]) {
lastHash[i] -= last[last.size() - lens[i]] - 'a';
}
lastHash[i] += letter - 'a';
}
if (last.size() >= len)
last.erase(last.begin());
last += letter;
for (int i = 0; i < wrds.size(); ++i) {
if (lastHash[i] != hash[i]) continue;
if (last.size() < wrds[i].size()) continue;
if (strcmp(last.c_str() + last.size() - wrds[i].size(), wrds[i].c_str()) == 0) return true;
}
return false;
}
};
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker* obj = new StreamChecker(words);
* bool param_1 = obj->query(letter);
*/