0. 前言
- 中文版地址:https://leetcode-cn.com/contest/weekly-contest-184/
- 英文版地址:https://leetcode.com/contest/weekly-contest-184/
1. 题解
1.1 5380. 数组中的字符串匹配(1408. String Matching in an Array)
- 中文版题目描述:https://leetcode-cn.com/problems/string-matching-in-an-array/
- 英文版题目描述:https://leetcode.com/problems/string-matching-in-an-array/
- 思路:排序+KMP(貌似也可以不用)
- 数据比较弱,暴力即可
- 注意答案去重,因为一个字符串可能是多个字符串的子串
- 代码如下:
class Solution {
public:
vector<int> getNext(string pattern) {
int len = (int)pattern.length();
vector<int> res(len+1,0);
int j = 0;
for (int i = 1 ; i < len ; i++) {
while (j && pattern[i] != pattern[j]) j = res[j];
if (pattern[i] == pattern[j]) j++;
res[i+1] = j;
}
return res;
}
int searchPosition(string text, string pattern, vector<int>& next) {
int j = 0 , lt = (int)text.length() , lp = (int)pattern.length();
for (int i = 0 ; i < lt ; i++) {
while (j && text[i] != pattern[j]) j = next[j];
if (text[i] == pattern[j]) j++;
if (j == lp) return i-j+1;
}
return -1;
}
bool isSubstr(string pattern, string text, unordered_map<string, vector<int>>& nextmp) {
if (searchPosition(text, pattern, nextmp[pattern]) >= 0) return true;
else return false;
}
vector<string> stringMatching(vector<string>& words) {
sort(words.begin(), words.end(), [](const string& a, const string& b) {
return a.length() < b.length();
});
unordered_map<string, vector<int>> nextmp;
for (auto str : words) {
nextmp[str] = getNext(str);
}
int n = words.size();
vector<string> ans;
unordered_map<string, bool> vis;
for (int i = 0 ; i < n ; i++) {
for (int j = i+1 ; j < n ; j++) {
if (!vis[words[i]] && isSubstr(words[i], words[j], nextmp)) {
ans.push_back(words[i]);
vis[words[i]] = true;
}
}
}
return ans;
}
};
1.2 5381. 查询带键的排列(1409. Queries on a Permutation With Key)
- 中文版题目描述:https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/
- 英文版题目描述:https://leetcode.com/problems/queries-on-a-permutation-with-key/
- 思路:模拟算法
- 代码如下:
class Solution {
public:
vector<int> processQueries(vector<int>& queries, int m) {
vector<int> p = vector<int>(m, 0);
for (int i = 0 ; i < m ; i++) {
p[i] = i + 1;
}
vector<int> ans;
for (auto q : queries) {
for (int i = 0 ; i < m ; i++) {
if (q == p[i]) {
ans.push_back(i);
for (int j = i ; j >= 1 ; j--) {
p[j] = p[j-1];
}
p[0] = q;
}
}
}
return ans;
}
};
1.3 5382. HTML 实体解析器(1410. HTML Entity Parser)
- 中文版题目描述:https://leetcode-cn.com/problems/html-entity-parser/
- 英文版题目描述:https://leetcode.com/problems/html-entity-parser/
- 思路:Java 可以通过库函数一行解决,C++ 通过模拟算法
- 有的朋友说模拟会超时,可能是遍历字符串时,匹配了整个子串,循环指针跳过整个子串吧
- 代码如下:
class Solution {
public:
string entityParser(string text) {
int len = text.length();
string ans = "";
for (int i = 0 ; i < len ; ) {
if (text[i] == '&') {
if (text[i+1] == 'q' && text[i+2] == 'u' && text[i+3] == 'o' && text[i+4] == 't' && text[i+5] == ';') {
ans += '"';
i += 6;
} else if (text[i+1] == 'a' && text[i+2] == 'p' && text[i+3] == 'o' && text[i+4] == 's' && text[i+5] == ';') {
ans += '\'';
i += 6;
} else if (text[i+1] == 'a' && text[i+2] == 'm' && text[i+3] == 'p' && text[i+4] == ';') {
ans += '&';
i += 5;
} else if (text[i+1] == 'g' && text[i+2] == 't' && text[i+3] == ';') {
ans += '>';
i += 4;
} else if (text[i+1] == 'l' && text[i+2] == 't' && text[i+3] == ';') {
ans += '<';
i += 4;
} else if (text[i+1] == 'f' && text[i+2] == 'r' && text[i+3] == 'a' && text[i+4] == 's' && text[i+5] == 'l' && text[i+6] == ';') {
ans += '/';
i += 7;
} else {
ans += '&';
i++;
}
} else {
ans += text[i];
i++;
}
}
return ans;
}
};
1.4 5383. 给 N x 3 网格图涂色的方案数(1411. Number of Ways to Paint N × 3 Grid)
- 中文版题目描述:https://leetcode-cn.com/problems/number-of-ways-to-paint-n-x-3-grid/
- 英文版题目描述:https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/
- 思路:动态规划,找规律
- 第一层,有 12 中情况,分为两大类:6 种 ABC 的情况,6 种 ABA 的情况
- 当前层只与上一层和本层有关
- 当上一层为 ABC 时,当前层会产生 2 种 ABC 和 2 种 ABA
- 当上一层为 ABA 时,当前层会产生 2 种 ABC 和 3 种 ABA
- 设 dp1[i] 表示第 i 层 ABC 的情况,dp2[i] 表示第 i 层 ABA 的情况
- 则有 dp1[i] = dp1[i-1] * 2 + dp2[i-1] * 2,dp2[i] = dp1[i-1] * 2 + dp2[i-1] * 3
- 代码如下:
class Solution {
public:
int numOfWays(int n) {
long long mod = 1000000007;
vector<long long> dp1 = vector<long long>(n, (long long)1);
vector<long long> dp2 = vector<long long>(n, (long long)1);
for (int i = 1 ; i < n ; i++) {
dp1[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)2) % mod;
dp2[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)3) % mod;
}
long long ans = (long long)6 * (dp1[n-1] + dp2[n-1]) % mod;
return (int)ans;
}
};
2. 小结
- 本次考试相对较水,前三题不是模拟就是暴力,第四题找规律即可
- 不要排斥暴力,有的时候也挺好用的,哈哈哈