Hypercube's LeetCode Weekly Contest 51
- Rank: 197 / 2879
- Score: 18 / 26
- Finish Time: 01:15:53
The testcases of the third problem in this contest are wrong, one of which is [[2,3], [5,2], [1,5], [4,2], [4,1]] and the expected answer is [4,1]. It seems that they forgot “each element pair [u, v] represents that v is a child of u in the tree.”
Baseball Game
You’re now a baseball game point recorder.
Given a list of strings, each string can be one of the 4 following types:
Integer(one round’s score): Directly represents the number of points you get in this round."+"(one round’s score): Represents that the points you get in this round are the sum of the last twovalidround’s points."D"(one round’s score): Represents that the points you get in this round are the doubled data of the lastvalidround’s points."C"(an operation, which isn’t a round’s score): Represents the lastvalidround’s points you get were invalid and should be removed.
Each round’s operation is permanent and could have an impact on the round before and the round after.
You need to return the sum of the points you could get in all the rounds.
Example 1:
Input: ["5", "2", "C", "D", "+"]
Output: 15
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.
Example 2:
Input: ["5", "-2", "4", "C", "D", "9", "+", "+"]
Output: 27
Explanation:
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get -2 points. The sum is: 3.
Round 3: You could get 4 points. The sum is: 7.
Operation 1: The round 3's data is invalid. The sum is: 3.
Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
Round 5: You could get 9 points. The sum is: 8.
Round 6: You could get -4 + 9 = 5 points. The sum is 13.
Round 7: You could get 9 + 5 = 14 points. The sum is 27.
Note:
- The size of the input list will be between 1 and 1000.
- Every integer represented in the list will be between -30000 and 30000.
class Solution:
def calPoints(self, ops):
"""
:type ops: List[str]
:rtype: int
"""
l = [0] * 10
s = 0
for o in ops:
if o == '+':
d = l[-1] + l[-2]
l.append(d)
s += d
elif o == 'C':
s -= l.pop()
elif o == 'D':
d = l[-1] * 2
l.append(d)
s += d
else:
d = int(o)
l.append(d)
s += d
return sNext Closest Time
Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.
You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.
Example 1:
Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.
Example 2:
Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.
class Solution:
def nextClosestTime(self, time):
"""
:type time: str
:rtype: str
"""
nt = int(time[0]), int(time[1]), int(time[3]), int(time[4])
ts = {nt}
ds = set(nt)
for d1 in ds:
if d1 > 2:
continue
for d3 in ds:
if d3 > 5:
continue
for d2 in ds:
if d1*10 + d2 > 23:
continue
for d4 in ds:
ts.add((d1, d2, d3, d4))
ts = list(ts)
ts.sort()
i = ts.index(nt)
if i == len(ts) - 1:
return '%s%s:%s%s' % ts[0]
return '%s%s:%s%s' % ts[i+1]Redundant Connection
We are given a “tree” in the form of a 2D-array, with distinct values for each node.
In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree.
We can remove exactly one redundant pair in this “tree” to make the result a tree.
You need to find and output such a pair. If there are multiple answers for this question, output the one appearing last in the 2D-array. There is always at least one answer.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: Original tree will be like this:
1
/ \
2 - 3
Example 2:
Input: [[1,2], [1,3], [3,1]]
Output: [3,1]
Explanation: Original tree will be like this:
1
/ \\
2 3
Note:
- The size of the input 2D-array will be between 1 and 1000.
- Every integer represented in the 2D-array will be between 1 and 2000.
class Solution:
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
root = {}
tree = {}
for (p, c) in edges:
if c not in root:
root[c] = root.setdefault(p, p)
tree.setdefault(root[p], {p}).add(c)
continue
if c in tree:
if p in tree:
if c != p:
for node in tree[c]:
root[node] = p
tree[p].add(node)
del tree[c]
continue
return (p, c)
if p in root:
if root[p] == c:
return (p, c)
tree.setdefault(root[p], {root[p]})
for node in tree[c]:
root[node] = root[p]
tree[root[p]].add(node)
del tree[c]
continue
tree.setdefault(p, {p})
for node in tree[c]:
root[node] = p
tree[p] = {p}
tree[p].add(node)
del tree[c]
continue
return (p, c)K Empty Slots
There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.
Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.
For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.
Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.
If there isn’t such day, output -1.
Example 1:
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
Example 2:
Input:
flowers: [1,2,3]
k: 1
Output: -1
Note:
- The given array will be in the range [1, 20000].
class Part:
def __init__(self, n, s, d, l, r):
self.n = n
self.s = s
self.d = d
self.l = l
self.r = r
self.lc = None
self.rc = None
if r != n + 1:
s.setdefault(r - d - 1, 0)
s[r - d - 1] += 1
if l:
s.setdefault(d - l - 1, 0)
s[d - l - 1] += 1
def part(self, p):
if p > self.d:
if self.rc:
return self.rc.part(p)
self.rc = Part(self.n, self.s, p, self.d, self.r)
if self.r != self.n + 1:
self.s[self.r - self.d - 1] -= 1
else:
if self.lc:
return self.lc.part(p)
self.lc = Part(self.n, self.s, p, self.l, self.d)
if self.l:
self.s[self.d - self.l - 1] -= 1
class Solution:
def kEmptySlots(self, flowers, k):
"""
:type flowers: List[int]
:type k: int
:rtype: int
"""
n = len(flowers)
if n < 2:
return -1
s = {}
parts = Part(n, s, flowers[0], 0, n+1)
for d in range(1, n):
if k in s and s[k]:
return d
parts.part(flowers[d])
return -1