【每日算法Day 77】LeetCode 第 181 场周赛题解
周赛链接
https:// leetcode-cn.com/contest /weekly-contest-181
LeetCode 5364. 按既定顺序创建目标数组
题目链接
https:// leetcode-cn.com/problem s/create-target-array-in-the-given-order/
题解
c++ vector
自带 insert
函数,直接用就行了。
代码(c++)
class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
int n = nums.size();
vector<int> target;
for (int i = 0; i < n; ++i) {
target.insert(target.begin()+index[i], nums[i]);
}
return target;
}
};
LeetCode 5178. 四因数
题目链接
https:// leetcode-cn.com/problem s/four-divisors/
题解
直接求出每个数因数个数就行了,对于每个数 ,只需要枚举到 就行了,另外如果因子个数已经大于 了,就直接退出。
代码(c++)
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int res = 0;
for (auto x : nums) {
int cnt = 0, sum = 0;
for (int i = 1; i*i <= x; ++i) {
if (i*i == x) {
cnt++;
break;
}
if (x%i == 0) {
cnt += 2;
sum += i + x/i;
}
if (cnt > 4) break;
}
if (cnt == 4) res += sum;
}
return res;
}
};
LeetCode 5366. 检查网格中是否存在有效路径
题目链接
https:// leetcode-cn.com/problem s/check-if-there-is-a-valid-path-in-a-grid/
题解
可以用 bfs 或者 dfs ,我这里采用的是 bfs 。
整体框架和普通的 bfs 完全一模一样,那么问题就在于如何判断两个格子能否相连。在代码中体现为 link
函数,我们给它传了三个参数:, 表示两个格子的街道标号(题面里解释了), 表示两个格子的位置关系(:左右,:右左,:上下,:下上)。
其中 和 都可以通过交换 和 的顺序,来分别转换成 和 。
对于 来说,左右能连接的情况,只有右边有出口的格子()接上左边有入口的格子()。
对于 来说,上下能连接的情况,只有下边有出口的格子()接上上边有入口的格子()。
其他情况全部无法连接。
这样最后 bfs 遍历到了 就能到达终点,否则就无法到达。
代码(c++)
class Solution {
public:
int link(int a, int b, int d) {
if (d == 1 || d == 3) {
d--;
swap(a, b);
}
if (d == 0) return (a==1||a==4||a==6)&&(b==1||b==3||b==5);
if (d == 2) return (a==2||a==3||a==4)&&(b==2||b==5||b==6);
return false;
}
bool hasValidPath(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<vector<int>> vis(n, vector<int>(m, 0));
queue<pair<int, int>> Q;
Q.push({0, 0});
vis[0][0] = 1;
while (!Q.empty()) {
pair<int, int> p = Q.front();
Q.pop();
int x = p.first, y = p.second;
if (x == n-1 && y == m-1) return true;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < m && !vis[nx][ny] && link(grid[x][y], grid[nx][ny], i)) {
vis[nx][ny] = 1;
Q.push({nx, ny});
}
}
}
return false;
}
};
LeetCode 5367. 最长快乐前缀
题目链接
https:// leetcode-cn.com/problem s/longest-happy-prefix/
题解
kmp 模板题,细节就不说了,网上教程漫天铺地都是的。就一个函数,是个模板直接用就行了。最后求出来的 就表示了 到 子串的最长相同前缀后缀的长度,所以答案就是 。
代码(c++)
class Solution {
public:
void getNext(string s, vector<int>& next) {
int n = s.size();
next[0] = 0;
for (int q = 1, k = 0; q < n; ++q) {
while (k > 0 && s[q] != s[k])
k = next[k-1];
if (s[q] == s[k]) k++;
next[q] = k;
}
}
string longestPrefix(string s) {
int n = s.size();
vector<int> next(n);
getNext(s, next);
return s.substr(0, next[n-1]);
}
};
公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。