leetcode-010

Alpha

Burst Balloons
Valid Palindrome
Subdomain Visit Count
Min Stack
Lowest Common Ancestor of a Binary Tree

Most Common Word
Summary Ranges
Sliding Window Maximum
Design Hit Counter
Jump Game II

Beta

EQ-1

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 312. Burst Balloons

class Solution:
def maxCoins(self, nums: List[int]) -> int:
if not nums:
return 0

nums = [1] + [num for num in nums if num > 0] + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]

for width in range(2, n):
for left in range(n - width):
right = left + width
border_product = nums[left] * nums[right]
max_val = 0

for mid in range(left + 1, right):
val = dp[left][mid] + nums[mid] * border_product + dp[mid][right]
if val > max_val:
max_val = val

dp[left][right] = max_val

return dp[0][n - 1]


class Solution:
from functools import lru_cache
def maxCoins(self, nums: List[int]) -> int:
# reframe the problem
nums = [1] + nums + [1]

# cache this
@lru_cache(None)
def dp(left, right):
# no more balloons can be added
if left + 1 == right: return 0
# add each balloon on the interval and return the maximum score
return max(nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right) for i in range(left+1, right))

# find the maximum number of coins obtained from adding all balloons from (0, len(nums) - 1)
return dp(0, len(nums)-1)

EQ-2

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 125. Valid Palindrome

class Solution:
def isPalindrome(self, s: str) -> bool:
s = re.sub('\W+', '', s).lower()
#re.sub(r'[^a-zA-Z0-9]+','',s).lower()
if s == s[::-1]: return True
return False


class Solution1:
def isPalindrome(self, s):
l, r = 0, len(s)-1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l <r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l +=1; r -= 1
return True

EQ-3

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

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
26
27
# 811. Subdomain Visit Count

class Solution:
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
counter = collections.Counter()
for cpd in cpdomains:
count, *domains = cpd.replace(" ",".").split(".")
for i in range(len(domains)):
counter[".".join(domains[i:])] += int(count)
return [" ".join((str(v), k)) for k, v in counter.items()]


class Solution1:
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
domain_names = {}
for i in cpdomains:
count, domains = i.split(' ')
count = int(count)
domains = domains.split('.')
while len(domains):
d = '.'.join(domains)
if d in domain_names:
domain_names[d] += count
else:
domain_names[d] = count
domains.pop(0)
return [f"{count} {domain}" for domain, count in domain_names.items()]

EQ-4

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.
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
26
27
28
29
30
31
32
33
34
35
# 155. Min Stack

class MinStack:

def __init__(self):
self.stack = []
self.min = []

def push(self, x: int) -> None:
self.stack.append(x)
if len(self.min) == 0:
self.min.append(x)
else:
if x < self.min[-1]:
self.min.append(x)
else:
self.min.append(self.min[-1])

def pop(self) -> None:
self.stack.pop()
self.min.pop()

def top(self) -> int:
return self.stack[-1]

def getMin(self) -> int:
return self.min[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

EQ-5

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

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
26
27
28
29
30
31
# 236. Lowest Common Ancestor of a Binary Tree

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root: return None
if root == p or root == q: return root

left = right = None
if root.left:
left = self.lowestCommonAncestor(root.left, p, q)
if root.right:
right = self.lowestCommonAncestor(root.right, p, q)

if left and right: return root
if not left: return right
return left

class Solution1:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root in (None, p, q):
return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right

EQ-6

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.
Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

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
26
# 819. Most Common Word

class Solution:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
banned = set(banned)
paragraph = paragraph.translate(str.maketrans("!?',;.", " ")).lower()
counter = collections.defaultdict(int)

max_count = 0
max_word = None
for word in paragraph.split():
if word not in banned:
counter[word] += 1
if counter[word] > max_count:
max_count = counter[word]
max_word = word

return max_word


class Solution1:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
banSet = set(banned)
words = re.findall(r"\w+", paragraph.lower())
cnt = collections.Counter(word for word in words if word not in banSet)
return cnt.most_common(1)[0][0]

EQ-7

Given a sorted integer array without duplicates, return the summary of its ranges.
Input: [0,1,2,4,5,7] Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

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
26
27
28
29
30
# 228. Summary Ranges

class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
ranges, r = [], []
for n in nums:
if n-1 not in r:
r = []
ranges += r,
r[1:] = n,
return ['->'.join(map(str, r)) for r in ranges]


class Solution2:
def summaryRanges(self, nums: List[int]) -> List[str]:
if len(nums) <2:
return [str(i) for i in nums]
start = prev = nums[0]
result = []
for i in range(1,len(nums)+1):
if i == len(nums) or nums[i] != nums[i-1]+1:
if start != prev:
result.append(str(start)+"->"+str(prev))
else:
result.append(str(start))
if i != len(nums):
start = prev = nums[i]
else:
prev = nums[i]
return result

EQ-8

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
# 239. Sliding Window Maximum

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
l = []
if len(nums) == 0: return []

l = nums[0:k]
m = max(l)
result = []
result.append(m)

for i in range(k, len(nums)):
if nums[i-k] == m:
m = max(nums[i-k+1:i+1])
elif m < nums[i]:
m = nums[i]

result.append(m)

return result


class Solution1:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

d = collections.deque()
out = []
for i, n in enumerate(nums):
while d and nums[d[-1]] < n:
d.pop()
d += i,
if d[0] == i - k:
d.popleft()
if i >= k - 1:
out += nums[d[0]],

return out

EQ-9

Design a hit counter which counts the number of hits received in the past 5 minutes.
Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.
It is possible that several hits arrive roughly at the same time.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 362. Design Hit Counter

class HitCounter:
def __init__(self):
self.series = []

def hit(self, timestamp: int) -> None:
self.series.append(timestamp)

def getHits(self, timestamp: int) -> int:
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
"""

oldest = timestamp - 300
while oldest >= 0 and len(self.series) > 0:
if self.series[0] <= oldest:
self.series.pop(0)
else:
break
return len(self.series)


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)



from collections import deque
class HitCounter1(object):
def __init__(self):
"""
Initialize your data structure here.
"""

self.counter = deque()

def hit(self, timestamp):
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: void
"""

self.counter.append(timestamp)

def getHits(self, timestamp):
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: int
"""

while self.counter and timestamp -self.counter[0] >= 300:
self.counter.popleft()
return len(self.counter)

EQ-10

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

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
26
# 45. Jump Game II

class Solution:
def jump(self, nums: List[int]) -> int:
jumps, currFarthest, currEnd = 0, 0, 0

for i in range(len(nums)-1):
currFarthest = max(currFarthest, i + nums[i])

if i == currEnd:
currEnd = currFarthest
jumps += 1

return jumps


class Solution1:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1: return 0
l, r = 0, nums[0]
times = 1
while r < len(nums) - 1:
times += 1
nxt = max(i + nums[i] for i in range(l, r + 1))
l, r = r, nxt
return times

Sigma

Feb 10, 2020
La Jolla, CA

Omega

https://leetcode.com/