LeetCode 第184场周赛

手速跟上了。。脑速跟不上。。

第一题:数组中的字符串匹配

难度简单

题目描述

给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] 仅包含小写英文字母。
  • 题目数据 保证 每个 words[i] 都是独一无二的。

题目链接

https://leetcode-cn.com/problems/string-matching-in-an-array/

思路:

  注意只要是任意其他字符的子串就满足要求。

代码:

第二题:查询带键的排列

难度中等

题目描述

给你一个待查数组 queries ,数组中的元素为 1m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i](从 i=0i=queries.length-1):

  • 一开始,排列 P=[1,2,3,...,m]
  • 对于当前的 i ,请你找出待查项 queries[i] 在排列 P 中的位置(下标从 0 开始),然后将其从原位置移动到排列 P 的起始位置(即下标为 0 处)。注意, queries[i]P 中的位置就是 queries[i] 的查询结果。

请你以数组形式返回待查数组 queries 的查询结果。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

题目链接

https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/

思路:

  模拟题,数据量较小,按题目要求模拟即可。

代码:

第三题:HTML 实体解析器

难度中等

题目描述

「HTML 实体解析器」 是一种特殊的解析器,它将 HTML 代码作为输入,并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括:

  • 双引号:字符实体为 &quot; ,对应的字符是 "
  • 单引号:字符实体为 &apos; ,对应的字符是 '
  • 与符号:字符实体为 &amp; ,对应对的字符是 &
  • 大于号:字符实体为 &gt; ,对应的字符是 >
  • 小于号:字符实体为 &lt; ,对应的字符是 <
  • 斜线号:字符实体为 &frasl; ,对应的字符是 /

给你输入字符串 text ,请你实现一个 HTML 实体解析器,返回解析器解析后的结果。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= text.length <= 10^5
  • 字符串可能包含 256 个ASCII 字符中的任意字符。

题目链接

https://leetcode-cn.com/problems/html-entity-parser/

思路:

  用replace替换即可。

代码:

第四题:给 N x 3 网格图涂色的方案数

难度困难

题目描述

你有一个 n x 3 的网格图 grid ,你需要用 红,黄,绿 三种颜色之一给每一个格子上色,且确保相邻格子颜色不同(也就是有相同水平边或者垂直边的格子颜色不同)。

给你网格图的行数 n

请你返回给 grid 涂色的方案数。由于答案可能会非常大,请你返回答案对 10^9 + 7 取余的结果。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • n == grid.length
  • grid[i].length == 3
  • 1 <= n <= 5000

题目链接

https://leetcode-cn.com/problems/number-of-ways-to-paint-n-x-3-grid/

思路:

  方法一:递归搜索,按从上到下,从左到右的顺序搜索,填充和相邻格子不同的颜色并计数。(超时)

  方法二:状态压缩dp,将一行看成是一个整体,共有12种可能的状态,下一行的状态和上一行的状态不冲突即可。记录每种状态的种数,统计总数即可。

代码:

  方法一:递归搜索(超时)

  方法二:状态压缩dp