0%

LeetCode第181场周赛题解

无聊刷刷leetcode,写写题解。


按既定顺序创建目标数组

看数据范围数组长度才100。

每次插入$O(n)$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> insert(const vector<int>& s, int id, int v) {
vector<int> res;
for(int i = 0; i < id; i++) {
res.push_back(s[i]);
}
res.push_back(v);
for(int i = id; i < int(s.size()); i++) {
res.push_back(s[i]);
}
return res;
}
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
const int n = nums.size();
vector<int> v;
for(int i = 0; i < n; i++) {
v = insert(v, index[i], nums[i]);
}
return v;
}
};

四因数

求一个数的因子个数和因子之和直接暴力时间复杂度$O(\sqrt{n})$。

那么总的复杂度就是$O(\sum\limits_{i=1}^{n}\sqrt{num_i})$。

数据范围告诉我们,这样暴力计算就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
const int n = nums.size();
int res = 0;
for(int i = 0; i < n; i++) {
int sz = 0, sum = 0;
for(int j = 1; j * j <= nums[i]; j++) {
if(j * j == nums[i]) {
sz++;
sum += j;
} else if(nums[i] % j == 0) {
sz += 2;
sum += j;
sum += nums[i] / j;
}
}
if(sz == 4) res += sum;
}
return res;
}
};

检查网格中是否存在有效路径

显然就是一个建图然后dfs的问题。

对于一个点而言,当且仅当这个点的一端和另一个点的一端连接上了,这时这两个点就可以连一条边。

建完图之后就是一个单源点单汇点的询问可达性的问题,直接dfs解决就可以了。

建图代码可以这样简化:令$ok[i][j]$代表第$i$种街道是否可以在$j$方向走出。

然后方向$0$和$1$代表上下,$2$和$3$代表左右,这样方向$x$的对面就是方向$x\oplus 1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

public:
void dfs(int u, vector<bool>& vis, const vector<vector<int>>& edg) {
vis[u] = true;
for(int i = 0; i < int(edg[u].size()); i++) {
const int v = edg[u][i];
if(!vis[v]) {
dfs(v, vis, edg);
}
}
}
bool hasValidPath(vector<vector<int>>& grid) {
const int fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> ok(7, vector<bool>(4, false));
ok[1][2] = ok[1][3] = ok[2][0] = ok[2][1] = ok[3][2] = ok[3][1] = ok[4][3] = ok[4][1] = ok[5][2] = ok[5][0] = ok[6][3] = ok[6][0] = true;
const int n = grid.size(), m = grid[0].size();
vector<vector<int>> edg(n * m);
// id = i * m + j
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
const int id = i * m + j;
for(int k = 0; k < 4; k++) {
const int X = fx[k][0] + i, Y = fx[k][1] + j;
if(X < 0 || X >= n || Y < 0 || Y >= m) continue;
if(ok[grid[i][j]][k] && ok[grid[X][Y]][k ^ 1]) {
edg[id].push_back(X * m + Y);
}
}
}
}
vector<bool> vis(n * m, false);
dfs(0, vis, edg);
return vis[n * m - 1];
}
};

最长快乐前缀

一看这个题就像是kmp的题,但是我不怎么会kmp,于是一下子就想到了哈希。

将所有后缀哈希之后放入set中,然后查找每一个前缀的哈希值是否在这个set里面。

我以为随便找个质数就能过了,结果WA。以为我某些地方写错了,然后排查了好久也排查不出来,最后决定多一个模数。

然后光荣TLE。然后我想既然都哈希了,不如用unordered_set替换set,相信unordered_set能AC,于是他就AC了。

是我acm题做多了吗?为什么$10^5$的数据$O(n\log(n))$都过不了,神奇。

然后看了下别人的做法,有很多正解kmp的,这些人很强。但是有些从后面开始暴力查找,还有从后面开始的哈希的居然比我的快这么多?复杂度一样就优化了常数就能AC?这都行?是我太菜了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
string longestPrefix(string s) {
unordered_set<int> Set1, Set2;
const int n = s.size();
int ca1 = 0, cb1 = 1;
int ca2 = 0, cb2 = 1;
const int MOD1 = 123415379, DEL1 = 15485863, MOD2 = 998244353, DEL2 = 19260817;
for(int i = n - 1; i >= 1; i--) {
ca1 += 1ll * cb1 * (s[i] - 'a' + 885919) % MOD1;
ca2 += 1ll * cb2 * (s[i] - 'a' + 885383) % MOD2;
if(ca1 >= MOD1) ca1 -= MOD1;
if(ca2 >= MOD2) ca2 -= MOD2;
Set1.insert(ca1);
Set2.insert(ca2);
cb1 = 1ll * cb1 * DEL1 % MOD1;
cb2 = 1ll * cb2 * DEL2 % MOD2;
}
int ans = 0;
ca1 = 0;
ca2 = 0;
for(int i = 0; i < n - 1; i++) {
ca1 = 1ll * ca1 * DEL1 % MOD1;
ca2 = 1ll * ca2 * DEL2 % MOD2;
ca1 += s[i] - 'a' + 885919;
ca2 += s[i] - 'a' + 885383;
if(ca1 >= MOD1) ca1 -= MOD1;
if(ca2 >= MOD2) ca2 -= MOD2;
if(Set1.find(ca1) != Set1.end() && Set2.find(ca2) != Set2.end()) ans = i + 1;
}
return s.substr(0, ans);
}
};

为什么测试代码的时候经常会内部错误。。是因为我没充会员吗?

回到开头