100 popular questions Flashcards
word-break-ii
https://leetcode.com/problems/word-break-ii/
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
return self.helper(s, wordDict, {})
def helper(self, s, wordDict, memo):
if s in memo: return memo[s]
if not s: return []
res = []
for word in wordDict:
if not s.startswith(word):
continue
if len(word) == len(s):
res.append(word)
else:
resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
for item in resultOfTheRest:
item = word + ' ' + item
res.append(item)
memo[s] = res
return res
minimum-window-substring
https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
def minWindow(s, t):
need = collections.Counter(t) #hash table to store char frequency
missing = len(t) #total number of chars we care
start, end = 0, 0
i = 0
for j, char in enumerate(s, 1): #index j from 1
if need[char] > 0:
missing -= 1
need[char] -= 1
if missing == 0: #match all chars
while i < j and need[s[i]] < 0: #remove chars to find the real start
need[s[i]] += 1
i += 1
need[s[i]] += 1 #make sure the first appearing char satisfies need[char]>0
missing += 1 #we missed this first char, so add missing by 1
if end == 0 or j-i < end-start: #update window
start, end = i, j
i += 1 #update i to start+1 for next window
return s[start:end]word-search-ii https://leetcode.com/problems/word-search-ii Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"]
Output: [“eat”,”oath”]
import collections
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
self.ret = set()
if not board or not words:
return self.ret
self.pf = set()
self.board = board
self.wordSet = set(words)
for word in words:
for i in range(1, len(word)):
self.pf.add(word[:i])
for i in range(len(board)):
for ii in range(len(board[0])):
queue = collections.deque()
queue.append([i, ii, ""])
visited = [[False for _ in range(len(board[0]))] for u in range(len(board))]
self.dfs(i, ii, "", visited)
return self.ret
def dfs(self, i2, ii2, curr, visited):
if 0 <= i2 < len(self.board) and 0 <= ii2 < len(self.board[0]):
if visited[i2][ii2]:
return
visited[i2][ii2] = True
curr += self.board[i2][ii2]
# print(curr)
if curr in self.wordSet:
self.ret.add(curr)
if curr in self.pf:
self.dfs(i2+1, ii2, curr, visited)
self.dfs(i2-1, ii2, curr, visited)
self.dfs(i2, ii2+1, curr, visited)
self.dfs(i2, ii2-1, curr, visited)
visited[i2][ii2] = False
largest-rectangle-in-histogram
https://leetcode.com/problems/largest-rectangle-in-histogram/
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last coordinate of the bar to the left which height h[l] >= h[i]
So if for any i coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
}
The main trick is how to effectively calculate lessFromRight and lessFromLeft arrays. The trivial solution is to use O(n^2) solution and for each i element first find his left/right heighbour in the second inner loop just iterating back or forward:
for (int i = 1; i < height.length; i++) {
int p = i - 1;
while (p >= 0 && height[p] >= height[i]) {
p–;
}
lessFromLeft[i] = p;
}
The only line change shifts this algorithm from O(n^2) to O(n) complexity: we don’t need to rescan each item to the left - we can reuse results of previous calculations and “jump” through indices in quick manner:
while (p >= 0 && height[p] >= height[i]) {
p = lessFromLeft[p];
}
Here is the whole solution:
public static int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
lessFromRight[height.length - 1] = height.length;
lessFromLeft[0] = -1;
for (int i = 1; i < height.length; i++) {
int p = i - 1;
while (p >= 0 && height[p] >= height[i]) {
p = lessFromLeft[p];
}
lessFromLeft[i] = p;
}
for (int i = height.length - 2; i >= 0; i--) {
int p = i + 1;
while (p < height.length && height[p] >= height[i]) {
p = lessFromRight[p];
}
lessFromRight[i] = p;
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
}
return maxArea; }
- Fraction to Recurring Decimal
https: //leetcode.com/problems/fraction-to-recurring-decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Example 1:
Input: numerator = 1, denominator = 2
Output: “0.5”
Example 2:
Input: numerator = 2, denominator = 1
Output: “2”
Example 3:
Input: numerator = 2, denominator = 3
Output: “0.(6)”
class Solution:
# @return a string
def fractionToDecimal(self, numerator, denominator):
res=""
if numerator/denominator<0:
res+="-"
if numerator%denominator==0:
return str(numerator/denominator)
numerator=abs(numerator)
denominator=abs(denominator)
res+=str(numerator/denominator)
res+="."
numerator%=denominator
i=len(res)
table={}
while numerator!=0:
if numerator not in table.keys():
table[numerator]=i
else:
i=table[numerator]
res=res[:i]+"("+res[i:]+")"
return res
numerator=numerator*10
res+=str(numerator/denominator)
numerator%=denominator
i+=1
return res
Idea is to put every remainder into the hash table as a key, and the current length of the result string as the value. When the same remainder shows again, it's circulating from the index of the value in the table.- Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
ret = []
if not nums:
return ret
arr = []
for num in nums[::-1]:
i = self.BinarySearch(arr, num)
arr = arr[:i] + [num] + arr[i:]
ret = [i] + ret
return ret
def BinarySearch(self, arr, num):
if not arr:
return 0
l = 0
h = len(arr)
m = (l+h)//2
while l < h:
m = (l+h)//2
if num <= arr[m]:
h = m
else:
l = m + 1
m += 1
return m
- Serialize and Deserialize Binary Tree
Share
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as “[1,2,3,null,null,4,5]”
class Codec:
def serialize(self, root):
if not root: return ""
q = collections.deque([root])
res = []
while q:
node = q.popleft()
if node:
q.append(node.left)
q.append(node.right)
res.append(str(node.val) if node else '#')
return ','.join(res)
def deserialize (self, data):
if not data: return None
nodes = data.split(',')
root = TreeNode(int(nodes[0]))
q = collections.deque([root])
index = 1
while q:
node = q.popleft()
if nodes[index] is not '#':
node.left = TreeNode(int(nodes[index]))
q.append(node.left)
index += 1
if nodes[index] is not '#':
node.right = TreeNode(int(nodes[index]))
q.append(node.right)
index += 1
return root
Bipartie graph check
https://leetcode.com/problems/is-graph-bipartite
def isBipartite(self, graph):
color = {}
def dfs(pos):
for i in graph[pos]:
if i in color:
if color[i] == color[pos]: return False
else:
color[i] = 1 - color[pos]
if not dfs(i): return False
return True
for i in range(len(graph)):
if i not in color: color[i] = 0
if not dfs(i): return False
return TrueQuick sort
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def partition(left, right, pivot_index):
pivot = nums[pivot_index]
# 1. move pivot to end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
# 2. move all smaller elements to the left
store_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# 3. move pivot to its final place
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def select(left, right, k_smallest):
"""
Returns the k-th smallest element of list within left..right
"""
if left == right: # If the list contains only one element,
return nums[left] # return that element
# select a random pivot_index between
pivot_index = random.randint(left, right)
# find the pivot position in a sorted list
pivot_index = partition(left, right, pivot_index)
# the pivot is in its final sorted position
if k_smallest == pivot_index:
return nums[k_smallest]
# go left
elif k_smallest < pivot_index:
return select(left, pivot_index - 1, k_smallest)
# go right
else:
return select(pivot_index + 1, right, k_smallest)
# kth largest is (n - k)th smallest
return select(0, len(nums) - 1, len(nums) - k)
