讨论/题目交流/🏆 第 190 场力扣周赛/
🏆 第 190 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 检查单词是否为句中其他单词的前缀
4 分 - 定长子串中元音的最大数目
5 分 - 二叉树中的伪回文路径
6 分 - 两个子序列的最大点积

展开讨论
力扣 (LeetCode)发起于 2020-05-24

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

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        for xi, x in enumerate(sentence.split(' ')):
            if x.startswith(searchWord):
                return xi + 1
        return -1

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

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        queue = collections.deque([])
        res = 0
        sum_ = 0
        for x in s:
            if x in list('aeiou'):
                queue.append(1)
                sum_ += 1
            else:
                queue.append(0)
            if len(queue) > k:
                sum_ -= queue.popleft()
            res = max(res, sum_)
        return res

二叉树中的伪回文路径

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        res = 0
        if root is None:
            return res
        seen = set()
        def dfs(root, count):
            if root.val in seen:
                seen.remove(root.val)
            else:
                seen.add(root.val)
            if root.left is None and root.right is None:
                if len(seen) <= 1:
                    count += 1
            if root.left is not None:
                count = dfs(root.left, count)
            if root.right is not None:
                count = dfs(root.right, count)
            if root.val in seen:
                seen.remove(root.val)
            else:
                seen.add(root.val)
            return count
        res = dfs(root, res)
        return res

两个子序列的最大点积

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        dp = [[-float('inf') for _ in range(n+1)] for _ in range(m+1)]
        # dp[i][j] = maxDotProduct(nums1[i:], nums2[j:])
        #          = max(nums1[i]*nums2[j]+max(0, dp[i+1][j+1]),
        #                dp[i+1, j], dp[j+1, j])
        for k in range(1, min(m, n)+1):
            # dp[i][n-k], i = 0, ..., m-k
            for i in reversed(range(m-k+1)):
                dp[i][n-k] = max(nums1[i]*nums2[n-k]+max(0, dp[i+1][n-k+1]),
                                 dp[i+1][n-k], dp[i][n-k+1])
            # dp[m-k][j], j = 0, ..., n-k
            for j in reversed(range(n-k+1)):
                dp[m-k][j] = max(nums1[m-k]*nums2[j]+max(0, dp[m-k+1][j+1]),
                                 dp[m-k+1][j], dp[m-k][j+1])
        return dp[0][0]
1
展开全部 31 讨论