Leetcode周赛 Weekly Contest 131

1021.Remove Outermost Parentheses

题目看了很久才读懂，这道题比较简单，就是统计一下左括号个数left和右括号个数，然后相等则加入res结果之中。

    def removeOuterParentheses(self, S: str) -> str:
        i = left = right = 0
        res = ""
        while i < len(S):
            if S[i] == '(':
                left += 1
            j = i 
            while left > right and j < len(S):
                j += 1
                if S[j] == '(':
                    left += 1
                else:
                    right += 1
            if left == right:
                res += S[i+1:j]
                i = j + 1
                left = right = 0
        return res

1022. Sum of Root To Leaf Binary Numbers

sum tree的题首先就想到回溯dfs解决。

    def sumRootToLeaf(self, root: TreeNode) -> int:
        res = []
        self.dfs(res, root, 0)
        result = 0
        return sum(res) % (10**9 + 7)
    
    def dfs(self, res, root, tmp):
        if not root:
            return 
        tmp = (tmp<<1) + root.val
        if not root.left and not root.right:
            res.append(tmp % (10**9 + 7))
        else: 
            self.dfs(res, root.left, tmp)
            self.dfs(res, root.right, tmp)

1023. Camelcase Matching

仍然是字符串处理的题，用i,j存入匹配s和pattern的位数，完了做个判断即可。

    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        res = []
        for s in queries:
            res.append(self.ispattern(s, pattern))
        return res
    
    def ispattern(self, s1, p):
        if len(s1) < len(p):
            return False
        i = j = 0
        while i < len(s1):
            if s1[i] == p[j]:
                i += 1
                j += 1
                if j == len(p):
                    break
                else:
                    continue
            elif s1[i] not in "abcdefghijklmnopqrstuvwxyz":
                return False
            i += 1
        while i < len(s1):
            if s1[i] not in "abcdefghijklmnopqrstuvwxyz":
                return False
            i += 1 
        if j == len(p):
            return True
        else:
            return False

1024. Camelcase Matching

bfs方法。

    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        if not clips:
            return -1
        clips.sort(key =lambda x:(x[0],-x[1]))        
        if clips[0][0] != 0:
            return -1
        queue = [(clips[0],1)]
        visited = [False for _ in range(len(clips))]
        visited[0] = True
        while queue:
            c, depth = queue.pop(0)
            if c[1] >= T:
                return depth
            for i in range(len(clips)):
                if clips[i][1] < c[1]:
                    continue
                elif clips[i][1] > c[1] and clips[i][0] <= c[1] and not visited[i]:
                    visited[i] = True
                    queue.append( ([c[0],clips[i][1]], depth + 1))
        return -1

贪心的方法

    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        #先排序，贪心更新首尾
        clips.sort(key =lambda x:(x[0],-x[1]))
        start = -1
        end = res = 0
        for i,j in clips:
            if i > end or end >= T:
                break
            elif start < i <= end: 
                res += 1
                start = end
            end = max(end,j) #i在start前面
        return res if end >= T else -1

只做了前三道，图搜索的题还可以再多做做，平时注意多阅读英文的题目。