无聊刷刷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); 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); } };
|
为什么测试代码的时候经常会内部错误。。是因为我没充会员吗?
回到开头