周赛笔记190


一、检查单词是否为句中其他单词的前缀

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

  • 如果 searchWord 是某一个单词的前缀,则返回句子 sentence 中该单词所对应的下标(下标从 1 开始)。
  • 如果 searchWord 是多个单词的前缀,则返回匹配的第一个单词的下标(最小下标)。
  • 如果 searchWord 不是任何单词的前缀,则返回 -1
    字符串 S 的 「前缀」是 S 的任何前导连续子字符串。
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        for i, s in enumerate(sentence.split()):
            if s.startswith(searchWord):
                return i+1
        return -1

二、定长子串中元音的最大数目

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

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans,tmp=0,0
        for i in range(len(s)):
            if s[i] in 'aeiou': tmp+=1
            if i>=k:
                if s[i-k] in 'aeiou': tmp-=1
            ans=max(ans,tmp)
        return ans   

小结

不能多想。。好菜

三、二叉树中的伪回文路径

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

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        if not root : return 0
        self.ans=0

        def dfs(root,tmp):
            if not root : return 
            helper(root.left,tmp+[root.val])
            helper(root.right,tmp+[root.val])
            tmp.append(root.val)

            if not root.left and not root.right:
                cnt=0
                for i in Counter(tmp).values():
                    if i%2: cnt+=1
                if cnt<2:self.ans+=1

        dfs(root,[])
        return self.ans

四、两个子序列的最大点积

给你两个数组 nums1nums2
请你返回 nums1nums2 中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5][1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m,n=len(nums1),len(nums2)
        dp=[[float('-inf')]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=nums1[i-1]*nums2[j-1]
                dp[i][j]=max(dp[i][j],dp[i][j]+dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
        return dp[m][n]

小结

DP题看的时候一点思路没有。。。被菜昏了


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录