第一题：检查单词是否为句中其他单词的前缀
难度简单
题目描述
给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。
请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
- 如果
searchWord是某一个单词的前缀，则返回句子sentence中该单词所对应的下标（下标从 1 开始）。 - 如果
searchWord是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。 - 如果
searchWord不是任何单词的前缀，则返回 -1 。
字符串 S 的 「前缀」是 S 的任何前导连续子字符串。
示例 1：
|
1 2 3 4 |
输入：sentence = "i love eating burger", searchWord = "burg" 输出：4 解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。 |
示例 2：
|
1 2 3 4 |
输入：sentence = "this problem is an easy problem", searchWord = "pro" 输出：2 解释："pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，但是应该返回最小下标 2 。 |
示例 3：
|
1 2 3 4 |
输入：sentence = "i am tired", searchWord = "you" 输出：-1 解释："you" 不是句子中任何单词的前缀。 |
示例 4：
|
1 2 3 |
输入：sentence = "i use triple pillow", searchWord = "pill" 输出：4 |
示例 5：
|
1 2 3 |
输入：sentence = "hello from the other side", searchWord = "they" 输出：-1 |
提示：
1 <= sentence.length <= 1001 <= searchWord.length <= 10sentence由小写英文字母和空格组成。searchWord由小写英文字母组成。- 前缀就是紧密附着于词根的语素，中间不能插入其它成分，并且它的位置是固定的——-位于词根之前。（引用自 前缀_百度百科 ）
题目链接
https://leetcode-cn.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/
思路:
暴力遍历即可。
代码:
|
1 2 3 4 5 6 7 8 9 |
class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: words = sentence.split() for i, word in enumerate(words): if word.startswith(searchWord): return i + 1 return -1 |
第二题：定长子串中元音的最大数目
难度中等
题目描述
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
|
1 2 3 4 |
输入：s = "abciiidef", k = 3 输出：3 解释：子字符串 "iii" 包含 3 个元音字母。 |
示例 2：
|
1 2 3 4 |
输入：s = "aeiou", k = 2 输出：2 解释：任意长度为 2 的子字符串都包含 2 个元音字母。 |
示例 3：
|
1 2 3 4 |
输入：s = "leetcode", k = 3 输出：2 解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。 |
示例 4：
|
1 2 3 4 |
输入：s = "rhythms", k = 4 输出：0 解释：字符串 s 中不含任何元音字母。 |
示例 5：
|
1 2 3 |
输入：s = "tryhard", k = 4 输出：1 |
提示：
1 <= s.length <= 10^5s由小写英文字母组成1 <= k <= s.length
题目链接
https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/
思路:
固定长度的滑动窗口计数。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution: def maxVowels(self, s: str, k: int) -> int: left = 0 wnd = 0 ans = 0 yuan = 'aeiou' for right, char in enumerate(s): if char in yuan: wnd += 1 if right - left + 1 == k: # 窗口内的数量正好为k ans = max(ans, wnd) if s[left] in yuan: wnd -= 1 # 减掉一个 left += 1 return ans |
第三题：二叉树中的伪回文路径
难度中等
题目描述
给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
示例 1：
|
1 2 3 4 5 |
输入：root = [2,3,1,3,1,null,1] 输出：2 解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。 在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。 |
示例 2：
|
1 2 3 4 5 |
输入：root = [2,1,1,1,3,null,null,null,null,null,1] 输出：1 解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。 这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。 |
示例 3：
|
1 2 3 |
输入：root = [9] 输出：1 |
提示：
- 给定二叉树的节点数目在
1到10^5之间。 - 节点值在
1到9之间。
题目链接
https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/
思路:
先遍历一遍树，记录所有从根节点到叶子结点的路径，然后寻找伪回文路径。
代码:
|
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 |
class Solution: def pseudoPalindromicPaths (self, root: TreeNode) -> int: def persudo_huwen(nums): c = Counter(nums) count = 0 for i in c.values(): if i % 2 == 1: count += 1 if count >= 2: return False return True path = [] ans = 0 def dfs(node): nonlocal ans if not node: return if not node.left and not node.right: # 叶子结点 if persudo_huwen(path+[node.val]): ans += 1 return path.append(node.val) dfs(node.left) dfs(node.right) path.pop() dfs(root) return ans |
第四题：两个子序列的最大点积
难度困难
题目描述
给你两个数组 nums1 和 nums2 。
请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。
示例 1：
|
1 2 3 4 5 |
输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6] 输出：18 解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。 它们的点积为 (2*3 + (-2)*(-6)) = 18 。 |
示例 2：
|
1 2 3 4 5 |
输入：nums1 = [3,-2], nums2 = [2,-6,7] 输出：21 解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。 它们的点积为 (3*7) = 21 。 |
示例 3：
|
1 2 3 4 5 |
输入：nums1 = [-1,-1], nums2 = [1,1] 输出：-1 解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。 它们的点积为 -1 。 |
提示：
1 <= nums1.length, nums2.length <= 500-1000 <= nums1[i], nums2[i] <= 100
题目链接
https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/
思路:
动态规划。dp[i][j]表示使用nums1[:i]和nums2[:j]能够得到的最大点积。状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + nums1[i-1] * nums2[j-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 |
class Solution: def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int: # dp[i][j]表示nums1[:i]和nums2[:j] # if nums1 == [5,-4,-3] and nums2 == [-4,-3,0,-4,2]: # return 28 if not list(filter(lambda x: x>=0, nums1)) and not list(filter(lambda x: x<=0, nums2)): return max(nums1) * min(nums2) if not list(filter(lambda x: x>=0, nums2)) and not list(filter(lambda x: x<=0, nums1)): return min(nums1) * max(nums2) l1 = len(nums1) l2 = len(nums2) dp = [[0 for _ in range(l2 + 1)] for _ in range(l1+1)] dp[0][0] = 0 ans = 0 for i in range(1, l1+1): for j in range(1, l2+1): dp[i][j] = max(dp[i][j], dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ,dp[i-1][j-1] + nums1[i-1] * nums2[j-1]) ans = max(ans, dp[i][j]) # print(dp) return ans |
