讨论/题目交流/🏆 第 184 场力扣周赛/
🏆 第 184 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组中的字符串匹配
4 分 - 查询带键的排列
5 分 - HTML 实体解析器
7 分 - 给 N x 3 网格图涂色的方案数

展开讨论

12点发题解。

这次是 手 速 场, 好 简 单

12点发题解。

这次是 手 速 场, 好 简 单

T1. 数组中的字符串匹配
读懂题意即可。 数据范围很小。 依次判断每个字符串 i 是不是另一个字符串 j 的子串即可。

时间复杂度 O(n2L2)O(n^2L^2)
空间复杂度 O(nL)O(nL)

T2. 查询带键的排列
同样是读懂题意即可。 只需要注意index是从0开始, 而值是从1开始就行。
每次找到对应的数然后将其挪到首位, 然后其前面的每个数依次往后挪一位即可。

时间复杂度 O(nm)O(nm)
空间复杂度 O(n)O(n)

T3. HTML 实体解析器
这道题比想象的简单。 所有需要解析的都是以 ‘&’ 开头的字符。 每次只需要判断 '&' 后面至多6个字符是否满足需要解析的字符串即可。 对于C++和Python来说, 内置函数Replace非常好用。

时间复杂度 O(L)O(L)
空间复杂度 O(L)O(L)

T3. 给 N x 3 网格图涂色的方案数
这道题解法很多。 抛砖引玉, 先说一个不是最优但是能AC本题的方法。

首先我们知道, 如果我们填好了前n - 1行, 则第n行的涂色方法只和它本身和 n - 1行相关。 其他行的涂色方式不会影响到本行。

因此, 定义以下函数。

f(n,status)f(n, status) 代表前n行在第n行涂色状态为status的情况下的涂色总方案数。

其中status的定义则为 按照Red = 0, Green = 1, Blue = 2将第n行依次改写为数字后所得数的三进制值。 即如果第n行涂色方法为(R, G, B), 则其对应值为(012)3=(5)10(012)_3 = (5)_{10}. 因此转移可以写作如下。

f(n,status)=f(n1,prevstatus)noConflict(prevstatus,status)f(n, status) = \sum {f(n-1, prev_status) | noConflict (prev_status, status)}.

即该状态可以由所有与其不产生冲突的上一行状态转移。

最后的结果 ans = f(n,status)0status<27\sum f(n, status) | 0 \leq status < 27

时间复杂度 O(nkm2m2)O(n k ^ {m ^ 2} m^2)

其中k为颜色数, m为列数
在本题数据m = k = 3, n = 5000的情况下来看, 极限数据大概在3.21073.2 * 10^7范围下, 勉强可以过。 稍微增大一点就比较困难了。

空间复杂度 O(nkm2)O(nk^{m^2})

展开全部 46 讨论