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

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

image.png

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

展开讨论

A: 数组中的字符串匹配

注意到数组的长度只有 100,可以逐一枚举数组内的字符串,当它是其他串的子串时可以作为答案。

B: 查询带键的排列

注意到 m 只有 1000,操作次数(queries.length)也只有 1000,直接暴力模拟这个过程即可:

  1. 扫描数组确定数字所在下标
  2. 删除该数字
  3. 将该数字插入数组的头部

这种操作场景,用 deque 比 vector 性能更好。

C: HTML 实体解析器

  1. 能被替换的字符串都是以 '&' 开头的
  2. 顺序扫描原串 text,遇到非 '&' 直接保留
  3. 遇到是 '&' 则判断后面连续的 4 ~ 7 个字符组成的子串是否为需要替换的字符串(最短的是 ">" 最长的是 "⁄" 长度分别为 4 和 7)
  4. 替换完后,扫描 text 的指针直接跳跃到替换后的字符下标;因此该指针不会回溯移动

D: 给 N x 3 网格图涂色的方案数

要确定一行的颜色,受两个因素影响:该行的相邻格子的颜色,上一行的配色。可见这是个递推关系。

每个格子能填 3 种颜色,因此一共有 27 种方案,以状态压缩的方式,用整数 [0, 26] 表示每种配色。但其中只有 12 种是合法的,即 Example 1 里面的 12 种。因此我们可以先把 12 种配色保存下来。

还要考虑上一行的配色对本行配色的影响。当上一行的配色确定后,本行可选的配色也可以确定。也把这个限制关系保存下来。

确定状态方程:

  1. dp[row][col] 表示合法构造了前 row 行且第 row 的配色为 col 的总方案数
  2. dp[row][col] = sum(dp[row-1][col_1]),其中 col 和 col_1 是不冲突的两种配色
  3. 最终答案 result = sum(dp[n-1][col]),col 来自那合法的 12 种方案

关注微信公众号查看代码

关注微信公众号 不爱睡觉的大猪,查看完成代码吧!
tmp.jpg

10
展开全部 46 讨论