笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 131

https://leetcode.com/contest/weekly-contest-131

Remove Outermost Parentheses

原题地址 https://leetcode.com/contest/weekly-contest-131/problems/remove-outermost-parentheses/

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, whereA and Bare valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example 1:

1
2
3
4
5
Input: "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

1
2
3
4
5
Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

1
2
3
4
5
Input: "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

Note:

  1. S.length <= 10000
  2. S[i] is "(" or ")"
  3. S is a valid parentheses string

一般做括号匹配会用到一个栈,遇到"("压栈,遇到")"弹出,栈的深度表示括号的层级,当栈深度为1时,表示是最外层括号。这里只有一种括号所以用不着用栈,只需要left记录未被匹配的"("数量,遇到最外层括号的时候忽略,然后返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def removeOuterParentheses(self, S):
"""
:type S: str
:rtype: str
"""
left = 0
res = []

for i in S:
if i == '(':
if left:
res.append(i)
left += 1
else:
if left != 1:
res.append(i)
left -= 1
return ''.join(res)

Sum of Root To Leaf Binary Numbers

原题地址 https://leetcode.com/contest/weekly-contest-131/problems/sum-of-root-to-leaf-binary-numbers/

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers.

Example 1:

1
2
3
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:

  1. The number of nodes in the tree is between 1 and 1000.
  2. node.val is 0 or 1.
  3. The answer will not exceed 2^31 - 1.

DFS找到每个到叶结点的路径对应的二进制数,遍历到叶结点时直接把路径代表的数字加到最终结果。

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def sumRootToLeaf(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 0

def dfs(r, acc):
if not r.left and not r.right:
self.res += int(acc + str(r.val), 2)
if r.left:
dfs(r.left, acc + str(r.val))
if r.right:
dfs(r.right, acc + str(r.val))

dfs(root, '')
return self.res

Camelcase Matching

原题地址 https://leetcode.com/contest/weekly-contest-131/problems/camelcase-matching/

A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query. (We may insert each character at any position, and may insert 0 characters.)

Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.

Example 1:

1
2
3
4
5
6
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation:
"FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Example 2:

1
2
3
4
5
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation:
"FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".

Example 3:

1
2
3
4
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation:
"FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".

Note:

  1. 1 <= queries.length <= 100
  2. 1 <= queries[i].length <= 100
  3. 1 <= pattern.length <= 100
  4. All strings consists only of lower and upper case English letters.

双指针遍历pattern和目标串,目标串中与pattern对应位置的字符不同时,如果在目标串中遇到的是小写字母,可以把指针跳到下一个位置,如果不是小写字母,则匹配失败,当遍历完pattern后,目标串剩下的内容如果都是小写字母则可以跳过,如果不是,匹配失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def camelMatch(self, queries, pattern):
"""
:type queries: List[str]
:type pattern: str
:rtype: List[bool]
"""
def is_match(q, p):
i = j = 0
while j < len(p):
if q[i] == p[j]:
i += 1
j += 1
else:
if q[i].islower():
i += 1
else:
return False
if i >= len(q):
return j == len(p)
return q[i:].islower()

return [is_match(q, pattern) for q in queries]

Video Stitching

原题地址 https://leetcode.com/contest/weekly-contest-131/problems/video-stitching/

You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.

Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.

Example 1:

1
2
3
4
5
6
7
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

1
2
3
4
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We can't cover [0,5] with only [0,1] and [0,2].

Example 3:

1
2
3
4
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation:
We can take clips [0,4], [4,7], and [6,9].

Example 4:

1
2
3
4
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation:
Notice you can have extra video after the event ends.

Note:

  1. 1 <= clips.length <= 100
  2. 0 <= clips[i][0], clips[i][1] <= 100
  3. 0 <= T <= 100

题很简单,就是太啰嗦了,既然可以重叠,也不用考虑去剪了,直接找最少需要多少clip来覆盖。

dp[i]表示保证覆盖到第i秒时最少需要多少clip,如果有一个区间为[x,y]的clip,且x<=i,那么dp[i]+1可以作为dp[y]的一个备选。先把区间按照x排序,然后计算每个[x,y]可以续接哪些i,然后更新dp[y]以及iy之间所有dp不超过dp[y],最后检查dp[T]是否还是未被更新的默认值,如果是则返回-1,否则直接返回dp[y]

x1<x2<y2<y1时,可以把[x2,y2]合并到[x1,y1],只考虑[x1,y1],那么在排序时可以直接以(x,-y)排序,把排序后y值小于前面的元素的去掉,可以减少部分工作量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def videoStitching(self, clips, T):
"""
:type clips: List[List[int]]
:type T: int
:rtype: int
"""
n = len(clips)
clips.sort()
dp = [0] + [n + 1] * 100
end = 0

for [x, y] in clips:
if y <= end:
continue
dp[y] = min(dp[x:y]) + 1
for i in range(x + 1, y):
dp[i] = min(dp[i], dp[y])
end = y

if dp[T] < n + 1:
return dp[T]
else:
return -1