LeetCode 第190场周赛

第一题:检查单词是否为句中其他单词的前缀

难度简单

题目描述

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ,其中句子由若干用 单个空格 分隔的单词组成。

请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

  • 如果 searchWord 是某一个单词的前缀,则返回句子 sentence 中该单词所对应的下标(下标从 1 开始)。
  • 如果 searchWord 是多个单词的前缀,则返回匹配的第一个单词的下标(最小下标)。
  • 如果 searchWord 不是任何单词的前缀,则返回 -1

字符串 S 的 「前缀」是 S 的任何前导连续子字符串。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= sentence.length <= 100
  • 1 <= searchWord.length <= 10
  • sentence 由小写英文字母和空格组成。
  • searchWord 由小写英文字母组成。
  • 前缀就是紧密附着于词根的语素,中间不能插入其它成分,并且它的位置是固定的——-位于词根之前。(引用自 前缀_百度百科

题目链接

https://leetcode-cn.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/

思路:

  暴力遍历即可。

代码:

第二题:定长子串中元音的最大数目

难度中等

题目描述

给你字符串 s 和整数 k

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为(a, e, i, o, u)。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • 1 <= k <= s.length

题目链接

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

思路:

  固定长度的滑动窗口计数。

代码:

第三题:二叉树中的伪回文路径

难度中等

题目描述

给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

示例 1:

示例 2:

示例 3:

提示:

  • 给定二叉树的节点数目在 110^5 之间。
  • 节点值在 19 之间。

题目链接

https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

思路:

  先遍历一遍树,记录所有从根节点到叶子结点的路径,然后寻找伪回文路径。

代码:

第四题:两个子序列的最大点积

难度困难

题目描述

给你两个数组 nums1nums2

请你返回 nums1nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5][1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

示例 1:

示例 2:

示例 3:

提示:

  • 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])

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注