手速跟上了。。脑速跟不上。。
第一题：数组中的字符串匹配
难度简单
题目描述
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
示例 1：
|
1 2 3 4 5 |
输入：words = ["mass","as","hero","superhero"] 输出：["as","hero"] 解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。 ["hero","as"] 也是有效的答案。 |
示例 2：
|
1 2 3 4 |
输入：words = ["leetcode","et","code"] 输出：["et","code"] 解释："et" 和 "code" 都是 "leetcode" 的子字符串。 |
示例 3：
|
1 2 3 |
输入：words = ["blue","green","bu"] 输出：[] |
提示：
1 <= words.length <= 1001 <= words[i].length <= 30words[i]仅包含小写英文字母。- 题目数据 保证 每个
words[i]都是独一无二的。
题目链接
https://leetcode-cn.com/problems/string-matching-in-an-array/
思路:
注意只要是任意其他字符的子串就满足要求。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def stringMatching(self, words: List[str]) -> List[str]: ans = [] for i in range(len(words)): for j in range(len(words)): if i != j and words[i] in words[j]: ans.append(words[i]) break return ans |
第二题：查询带键的排列
难度中等
题目描述
给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：
- 一开始，排列
P=[1,2,3,...,m]。 - 对于当前的
i，请你找出待查项queries[i]在排列P中的位置（下标从 0 开始），然后将其从原位置移动到排列P的起始位置（即下标为 0 处）。注意，queries[i]在P中的位置就是queries[i]的查询结果。
请你以数组形式返回待查数组 queries 的查询结果。
示例 1：
|
1 2 3 4 5 6 7 8 9 |
输入：queries = [3,1,2,1], m = 5 输出：[2,1,2,1] 解释：待查数组 queries 处理如下： 对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。 对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。 对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。 对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。 因此，返回的结果数组为 [2,1,2,1] 。 |
示例 2：
|
1 2 3 |
输入：queries = [4,1,2,2], m = 4 输出：[3,1,2,0] |
示例 3：
|
1 2 3 |
输入：queries = [7,5,5,8,3], m = 8 输出：[6,5,0,7,5] |
提示：
1 <= m <= 10^31 <= queries.length <= m1 <= queries[i] <= m
题目链接
https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/
思路:
模拟题，数据量较小，按题目要求模拟即可。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def processQueries(self, queries: List[int], m: int) -> List[int]: P = list(range(1, m+1)) ans = [] for q in queries: idx = P.index(q) P.pop(idx) P = [q] + P ans.append(idx) return ans |
第三题：HTML 实体解析器
难度中等
题目描述
「HTML 实体解析器」 是一种特殊的解析器，它将 HTML 代码作为输入，并用字符本身替换掉所有这些特殊的字符实体。
HTML 里这些特殊字符和它们对应的字符实体包括：
- 双引号：字符实体为
"，对应的字符是"。 - 单引号：字符实体为
'，对应的字符是'。 - 与符号：字符实体为
&，对应对的字符是&。 - 大于号：字符实体为
>，对应的字符是>。 - 小于号：字符实体为
<，对应的字符是<。 - 斜线号：字符实体为
⁄，对应的字符是/。
给你输入字符串 text ，请你实现一个 HTML 实体解析器，返回解析器解析后的结果。
示例 1：
|
1 2 3 4 |
输入：text = "& is an HTML entity but &ambassador; is not." 输出："& is an HTML entity but &ambassador; is not." 解释：解析器把字符实体 & 用 & 替换 |
示例 2：
|
1 2 3 |
输入：text = "and I quote: "..."" 输出："and I quote: \"...\"" |
示例 3：
|
1 2 3 |
输入：text = "Stay home! Practice on Leetcode :)" 输出："Stay home! Practice on Leetcode :)" |
示例 4：
|
1 2 3 |
输入：text = "x > y && x < y is always false" 输出："x > y && x < y is always false" |
示例 5：
|
1 2 3 |
输入：text = "leetcode.com⁄problemset⁄all" 输出："leetcode.com/problemset/all" |
提示：
1 <= text.length <= 10^5- 字符串可能包含 256 个ASCII 字符中的任意字符。
题目链接
https://leetcode-cn.com/problems/html-entity-parser/
思路:
用replace替换即可。
代码:
|
1 2 3 4 5 6 7 |
class Solution: def entityParser(self, text: str) -> str: text = text.replace('"', '"').replace(''', "'").replace('>','>').replace('<','<').replace('⁄','/') text = text.replace('&', '&') return text |
第四题：给 N x 3 网格图涂色的方案数
难度困难
题目描述
你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
给你网格图的行数 n 。
请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。
示例 1：
|
1 2 3 4 |
输入：n = 1 输出：12 解释：总共有 12 种可行的方法： |
示例 2：
|
1 2 3 |
输入：n = 2 输出：54 |
示例 3：
|
1 2 3 |
输入：n = 3 输出：246 |
示例 4：
|
1 2 3 |
输入：n = 7 输出：106494 |
示例 5：
|
1 2 3 |
输入：n = 5000 输出：30228214 |
提示：
n == grid.lengthgrid[i].length == 31 <= n <= 5000
题目链接
https://leetcode-cn.com/problems/number-of-ways-to-paint-n-x-3-grid/
思路:
方法一：递归搜索，按从上到下，从左到右的顺序搜索，填充和相邻格子不同的颜色并计数。（超时）
方法二：状态压缩dp，将一行看成是一个整体，共有12种可能的状态，下一行的状态和上一行的状态不冲突即可。记录每种状态的种数，统计总数即可。
代码:
方法一：递归搜索（超时）
|
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 37 38 39 |
sys.setrecursionlimit(1000000000) def numOfWays(n: int) -> int: mem = [[0 for _ in range(3)] for _ in range(n)] # n * 3 ans = 0 def dfs(i, j): nonlocal ans if i < 0 or j < 0 or i >= n or j >= 3: return # 下一个位置 if j < 2: x, y = i, j + 1 else: x, y = i + 1, 0 for color in range(1, 4): if i > 0 and mem[i - 1][j] == color: continue if j > 0 and mem[i][j - 1] == color: continue if i < n - 1 and mem[i + 1][j] == color: continue if j < 2 and mem[i][j + 1] == color: continue mem[i][j] = color if i == n - 1 and j == 2: ans += 1 # print(mem) dfs(x, y) mem[i][j] = 0 dfs(0, 0) return ans |
方法二：状态压缩dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution: def numOfWays(self, n: int) -> int: state = ['010', '012', '020', '021', '101', '102', '120', '121','201', '202', '210','212'] dp = [[0 for _ in range(27)] for _ in range(n)] # n * 12 for i in range(12): dp[0][int(state[i], 3)] = 1 for i in range(1, n): for s1 in state: for s2 in state: for k in range(3): if s1[k] == s2[k]: break else: dp[i][int(s2 ,3)] += dp[i-1][int(s1, 3)] return sum(dp[-1]) %1000000007 |
