211. Design Add and Search Words Data Structure （Medium）
Design Add and Search Words Data Structure
class WordDictionary:
def __init__(self):
self.next = dict()
self.isword= False
def addWord(self, word: str) -> None:
if word:
char = word[0]
rest = word[1:]
if char not in self.next:
self.next[char]=WordDictionary()
self.next[char].addWord(rest)
else:
self.isword=True
def search(self, word: str) -> bool:
if not word:
return self.isword
char = word[0]
rest = word[1:]
if char!='.':
if char not in self.next:
return False
else:
return self.next[char].search(rest)
else:
return any([ node.search(rest) for key,node in self.next.items()])
return True
#MY ANSWER
class WordDictionary:
def __init__(self):
self.isword = False
self.data = collections.defaultdict(WordDictionary)
def addWord(self, word: str) -> None:
if not word:
self.isword = True
return
head = word[0]
rest = word[1:]
if head not in self.data:
self.data[head] = WordDictionary()
self.data[head].addWord(rest)
def search(self, word: str) -> bool:
if not word:
if self.isword:
return True
else:
return False
else:
head = word[0]
rest = word[1:]
if head!='.':
return self.data[head].search(rest)
else:
return any(self.data[key].search(rest) for key in self.data )
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
Trie data structure
212. Word Search II （Hard）
Given an m x n board of characters and a list of strings words, return all words on the board.
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"]
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
#trie + DFS
class Trie:
def __init__(self):
self.next=dict()
self.isword=False
def addwords(self,word):
if word:
char=word[0]
rest=word[1:]
if char not in self.next:
self.next[char]= Trie()
self.next[char].addwords(rest)
else:
self.isword=True
trie = Trie()
for word in words:
trie.addwords(word)
m=len(board)
n=len(board[0])
res = []
def dfs(trie,board,i,j,tmp=''):
if i>=0 and i<m and j>=0 and j<n:
char= board[i][j]
board[i][j]='#'
tmp+=char
if char in trie.next:
if trie.next[char].isword:
res.append(tmp)
trie.next[char].isword=False
trie = trie.next[char]
dfs(trie,board,i+1,j,tmp)
dfs(trie,board,i-1,j,tmp)
dfs(trie,board,i,j+1,tmp)
dfs(trie,board,i,j-1,tmp)
tmp = tmp[:-1]
board[i][j] = char
for i in range(m):
for j in range(n):
if board[i][j] in [word[0] for word in words]:
dfs(trie,board,i,j,'')
return res
#MY ANSWER
class Trie:
def __init__(self):
self.isword = False
self.data = collections.defaultdict(Trie)
def insert(self,word):
if not word:
self.isword = True
return
head = word[0]
rest = word[1:]
if head not in self.data:
self.data[head] = Trie()
self.data[head].insert(rest)
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
t = Trie()
for word in words:
t.insert(word)
res = []
m = len(board)
n = len(board[0])
def dfs(i,j,t,tmp):
if m>i>=0 and n>j>=0 and board[i][j] in t.data:
boardij=board[i][j]
board[i][j] = '#'
tmp+=boardij
t = t.data[boardij]
if t.isword:
res.append(tmp)
t.isword =False
dfs(i+1,j,t,tmp)
dfs(i-1,j,t,tmp)
dfs(i,j-1,t,tmp)
dfs(i,j+1,t,tmp)
board[i][j] = boardij
for i in range(m):
for j in range(n):
dfs(i,j,t,'')
return res
尝试trie+DFS , time limit exceeded. 什么地方没优化到？？ 原来是 发现isword时候 把isword设为False，这样就不会找到重复的word。
213. House Robber II （Medium）
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
class Solution:
def rob(self, nums: List[int]) -> int:
# dp[i] = max(dp[i-2]+nums[i], dp[i-1])
# dp[0] = nums[0]
# dp[1] = max(nums[:2])
#
# now circle constraint
#
# if select 0, -1 and 1 can not be selected
# dp[0] = nums[0] dp[1] = dp[0] ... dp[-1]=dp[-2]
# if not select 0, -1 and 1 can be selected
# dp[0] = 0 dp[1]=nums[1] ... dp[-1]=dp[-2]+nums[-1]
if len(nums)<3:
return max(nums)
#case1) select 0
dp=[0]*len(nums)
dp[0]=nums[0]
dp[1]=nums[0]
for i in range(2,len(nums)):
if i!=len(nums)-1:
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
else:
dp[i]=dp[i-1]
res=max(dp)
#case2)
dp=[0]*len(nums)
dp[0]=0
dp[1]=nums[1]
for i in range(2,len(nums)):
if i!=len(nums)-1:
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
else:
dp[i]=dp[i-2]+nums[-1]
res=max(res,max(dp))
return res
#MY ANSWER
class Solution:
def rob(self, nums: List[int]) -> int:
# dp[0] = nums[0] rob0
# dp[1] = dp[0]
# dp[i] = max(nums[i]+dp[i-2] ,dp[i-1])
#
# dp'[0] = 0 rob1
# dp'[1] = nums[1]
# dp [i] = max(nums[i]+dp[i-2] ,dp[i-1])
if len(nums)<=2: return max(nums)
l = len(nums)
dp = [[0]*l,[0]*l]
dp[0][0] = nums[0]
dp[0][1] = nums[0]
dp[1][1] = nums[1]
for i in range(2,l):
if i!=l-1:
dp[0][i] = max(dp[0][i-2]+nums[i],dp[0][i-1])
dp[1][i] = max(dp[1][i-2]+nums[i],dp[1][i-1])
else:
dp[0][i] = dp[0][i-1]
dp[1][i] = max(dp[1][i-2]+nums[i],dp[1][i-1])
return max(dp[0][-1],dp[1][-1])
因为循环数组，所以，分两种case， 抢劫第一户和不抢劫第一户。
214. Shortest Palindrome （Hard）
You are given a string s. You can convert s to a palindrome by adding characters in front of it.
#MY ANSWER is a bad one
class Solution:
def shortestPalindrome(self, s: str) -> str:
if s == s[::-1]: return s
# tfel + ABC CBA left
res = None
for i in range(1,len(s)//2+1):
if s[:i] == s[i:2*i][::-1]:
#print(1,s[:i],s[i:2*i], s[2*i:])
tmp = s[2*i:][::-1]+s
if res and len(tmp)<len(res):
res = tmp
elif res is None:
res = tmp
if s[:i] == s[i+1:2*i+1][::-1]:
#print(2,s[:i])
tmp = s[2*i+1:][::-1]+s
if res and len(tmp)<len(res):
res = tmp
elif res is None:
res = tmp
return res if res else s[1:][::-1] + s
###
class Solution:
def shortestPalindrome(self, s: str) -> str:
# brute force
l=len(s)
rev = ''.join(s[::-1])
for i in range(l):
if s[:l-i]==rev[i:]:
return rev[:i]+s
return ''
#KMP
class Solution:
def shortestPalindrome(self, s: str) -> str:
# KMP
l=len(s)
rev = ''.join(s[::-1])
s_new = s +'#' + rev
l_new = len(s_new)
f = [0]*l_new
for i in range(1,l_new):
t = f[i-1]
while t>0 and s_new[i]!=s_new[t]:
#can'f find prefix=sufix, t=f[t-1]
t=f[t-1]
if s_new[i]==s_new[t]:
t+=1
f[i]=t
return rev[:l-f[l_new-1]] +s
思路： finding the largest palindrome substring from the beginning. O（n）方法用了KMP的loolup table。 rev[f[l_new-1]:]是形成回文的序列。和 s[:len(s)-f[l_new-1]] 是对应的，那么未形成回文的就是 rev[: f[l_new-1]] ，s+rev[: f[l_new-1]] 为答案。 s_new = s +'#' + rev 因为不加#会引起 2 strings could mix with each ther, producing wrong answer. For example, take the string "aaaa" . Had we not inserted "#" in the middle, the new string would be "aaaaaaaa"。
215. Kth Largest Element in an Array （Medium）
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
from heapq import heapify, heappush, heappop
stack=[]
for i,n in enumerate(nums):
if len(stack)<k:
heappush(stack,n)
else:
tmp=heappop(stack)
if n<tmp:
heappush(stack,tmp)
else:
heappush(stack,n)
return heappop(stack)
###
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)
min heap
第二种解法quicksort， O（n）
Choose a random pivot.
Use a partition algorithm to place the pivot into its perfect position pos in the sorted array, move smaller elements to the left of pivot, and larger or equal ones - to the right.
Compare pos and N - k to choose the side of array to proceed recursively.
216. Combination Sum III （Medium）
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
def bt(start,tmp,target):
if target<0: return
if len(tmp)==k and target==0:
res.append(tmp[:])
for i in range(start,10):
tmp.append(i)
target -= i
bt(i+1,tmp,target)
target+=i
tmp.pop()
bt(1,[],n)
return res
#MY ANSWER
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
nums = [i for i in range(1,10)]
res = []
def bt(tmp,val,start):
if val<0 or len(tmp)>k: return
if len(tmp)==k and val==0:
res.append(tmp[:])
return
for i in range(start,len(nums)):
tmp.append(nums[i])
bt(tmp,val-nums[i],i+1)
tmp.pop()
bt([],n,0)
return res
217. Contains Duplicate (Easy)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
s = set()
for n in nums:
if n in s:
return True
s.add(n)
return False
218. The Skyline Problem (Hard)
from heapq import *
class Solution(object):
def getSkyline(self, buildings):
# add start-building events
# also add end-building events(acts as buildings with 0 height)
# and sort the events in left -> right order
events = [(L, -H, R) for L, R, H in buildings]
events.extend([(R, 0, 0) for _, R, _ in buildings])
events.sort()
# res: result, [x, height]
# live: heap, [-height, ending position]
res = [[0,0]]
live = [(0, float("inf"))]
for pos, negH, R in events:
# 1, pop buildings that are already ended
# 2, if it's the start-building event, make the building alive
# 3, if previous keypoint height != current highest height, edit the result
while pos>= live[0][1]:
heappop(live)
if negH!=0:
#start building event
heappush(live, (negH, R))
if res[-1][1] != -live[0][0]:
res.append( [pos, -live[0][0]])
return res[1:]
#
class Solution:
def getSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]':
"""
Divide-and-conquer algorithm to solve skyline problem,
which is similar with the merge sort algorithm.
"""
n = len(buildings)
# The base cases
if n == 0:
return []
if n == 1:
x_start, x_end, y = buildings[0]
return [[x_start, y], [x_end, 0]]
# If there is more than one building,
# recursively divide the input into two subproblems.
left_skyline = self.getSkyline(buildings[: n // 2])
right_skyline = self.getSkyline(buildings[n // 2 :])
# Merge the results of subproblem together.
return self.merge_skylines(left_skyline, right_skyline)
def merge_skylines(self, left, right):
"""
Merge two skylines together.
"""
def update_output(x, y):
"""
Update the final output with the new element.
"""
# if skyline change is not vertical -
# add the new point
if not output or output[-1][0] != x:
output.append([x, y])
# if skyline change is vertical -
# update the last point
else:
output[-1][1] = y
def append_skyline(p, lst, n, y, curr_y):
"""
Append the rest of the skyline elements with indice (p, n)
to the final output.
"""
while p < n:
x, y = lst[p]
p += 1
if curr_y != y:
update_output(x, y)
curr_y = y
n_l, n_r = len(left), len(right)
p_l = p_r = 0
curr_y = left_y = right_y = 0
output = []
# while we're in the region where both skylines are present
while p_l < n_l and p_r < n_r:
point_l, point_r = left[p_l], right[p_r]
# pick up the smallest x
if point_l[0] < point_r[0]:
x, left_y = point_l
p_l += 1
else:
x, right_y = point_r
p_r += 1
# max height (i.e. y) between both skylines
max_y = max(left_y, right_y)
# if there is a skyline change
if curr_y != max_y:
update_output(x, max_y)
curr_y = max_y
# there is only left skyline
append_skyline(p_l, left, n_l, left_y, curr_y)
# there is only right skyline
append_skyline(p_r, right, n_r, right_y, curr_y)
return output
感觉用stack做， 还是直接看答案了， 思路：事件驱动， events 包括开始建筑和终止建筑，【（L，-H，R），（R，0，0）.。。。】 这样遍历events，live存放【（-height，end pos）】 1, pop buildings that are already ended in live 2，if it's the start-building event, make the building alive， 3，if previous keypoint height != current highest height, edit the result， 思路2，分治法 O(NlogN)
219. Contains Duplicate II （Easy）
## correct way of doing
class Solution:
def containsNearbyDuplicate(self, nums: 'List[int]', k: 'int') -> 'bool':
dic=dict()
for i,n in enumerate(nums):
if n in dic:
if abs(i-dic[n])<=k:
return True
dic[n]=i
return False
two pointer timestap<=k 过期，花的时间太长。。。， 正确方法还是用dict 存 mapping n=> i. 这样当遇到重复的n判断 i-dic【n】距离是否小于k，小于则为True。
220. Contains Duplicate III （Medium）
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if t< 0: return False
dic = dict()
for i,n in enumerate(nums):
#remove outdated
if i-k>=0 and nums[i-k] in dic and dic[nums[i-k]]<i-k:
del dic[nums[i-k]]
#print(i,n,dic)
#check
if any([abs(n-key)<=t and abs(i-val)<=k for key,val in dic.items()]):
#print(i,n)
#print(dic)
return True
#add current
dic[n]=i
return False
#
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
# 0~9 10~19 ..
# buketid 0 1
# what is 9's buket id, 9//(9+1)
# so bucket size = 10
buket = dict()
buket_size = t+1
for i,n in enumerate(nums):
buket_id = n//buket_size
if buket_id in buket or (buket_id-1 in buket and n-buket[buket_id-1]<=t) or(buket_id+1 in buket and buket[buket_id+1]-n<=t):
return True
buket[buket_id] = n
if i>=k:
del buket[nums[i-k]//buket_size]
return False
用过期del dict key方法会time limit exceeded。竟然是用bukets。检查当前buket 和上一个或者下一个buket。 这题应该是个hard。