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.
class Solution: def maxCoins(self, nums: List[int]) -> int: if not nums: return0
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): forleft 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
returndp[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 ifleft + 1 == right:return0 # add each balloon on the interval andreturn the maximum score returnmax(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) returndp(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.
classSolution: defisPalindrome(self, s: str) -> bool: s = re.sub('\W+', '', s).lower() #re.sub(r'[^a-zA-Z0-9]+','',s).lower() if s == s[::-1]: returnTrue returnFalse
classSolution1: defisPalindrome(self, s): l, r = 0, len(s)-1 while l < r: while l < r andnot s[l].isalnum(): l += 1 while l <r andnot s[r].isalnum(): r -= 1 if s[l].lower() != s[r].lower(): returnFalse l +=1; r -= 1 returnTrue
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.
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)) fork, 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('.') whilelen(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.
# 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]
# Definition fora 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 == por 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)
ifleftand right:return root if not left:returnright returnleft
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 ifleftandrightelseleftorright
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.
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.
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]: iflen(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.
d = collections.deque() out = [] fori, n in enumerate(nums): whiled and nums[d[-1]] < n: d.pop() d+= i, ifd[0] == i - k: d.popleft() ifi >= k - 1: out+= nums[d[0]],
returnout
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.
defgetHits(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 >= 0and 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 classHitCounter1(object): def__init__(self): """ Initialize your data structure here. """ self.counter = deque()
defhit(self, timestamp): """ Record a hit. @param timestamp - The current timestamp (in seconds granularity). :type timestamp: int :rtype: void """ self.counter.append(timestamp)
defgetHits(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.
for i in range(len(nums)-1): currFarthest = max(currFarthest, i + nums[i])
if i == currEnd: currEnd = currFarthest jumps += 1
returnjumps
class Solution1: def jump(self, nums: List[int]) -> int: iflen(nums) <= 1: return0 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