311. Sparse Matrix Multiplication (Medium)
Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
l=len(mat1)
m=len(mat1[0])
n=len(mat2[0])
#1m*mn = ln
res = [[0]*n for _ in range(l)]
for i in range(l):
for j in range(n):
for k in range(m):
res[i][j]+=mat1[i][k]*mat2[k][j]
return res
####
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
def compress_matrix(matrix: List[List[int]]) -> List[List[int]]:
rows, cols = len(matrix), len(matrix[0])
compressed_matrix = [[] for _ in range(rows)]
for row in range(rows):
for col in range(cols):
if matrix[row][col]:
compressed_matrix[row].append([matrix[row][col], col])
return compressed_matrix
m = len(mat1)
k = len(mat1[0])
n = len(mat2[0])
# Store the non-zero values of each matrix.
A = compress_matrix(mat1)
B = compress_matrix(mat2)
ans = [[0] * n for _ in range(m)]
for mat1_row in range(m):
# Iterate on all current 'row' non-zero elements of mat1.
for element1, mat1_col in A[mat1_row]:
# Multiply and add all non-zero elements of mat2
# where the row is equal to col of current element of mat1.
for element2, mat2_col in B[mat1_col]:
ans[mat1_row][mat2_col] += element1 * element2
return ans
因为题目是sparse table 所以更好的做饭是把table 存成hashmap。
312. Burst Balloons
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely
class Solution:
def maxCoins(self, nums: List[int]) -> int:
#ith is the last to burst
nums = [1]+nums+[1]
n=len(nums)
dp=[[0]*n for _ in range(n)]
for left in range(n-2,0,-1):
for right in range(left,n-1):
for i in range(left,right+1):
gain=nums[left-1]*nums[i]*nums[right+1]
remaining=dp[left][i-1]+dp[i+1][right]
dp[left][right]=max(dp[left][right],gain+remaining)
return dp[1][n-2]
#MY ANSWER
class Solution:
def maxCoins(self, nums: List[int]) -> int:
@lru_cache(None)
def dp(i,j):
res = 0
for k in range(i,j+1):
a = nums[k]
b = nums[i-1] if i-1>=0 else 1
c = nums[j+1] if j+1<len(nums) else 1
res = max(res, a*b*c+ dp(i,k-1)+dp(k+1,j))
return res
return dp(0,len(nums)-1)
初次尝试，backtraking 方法会time limit exceeded， 需要更优方法。 答案1） top down dp， ith气球是最后一个burst的，所以left到i-1，i+1到right先burst。 思路是分治法，能拆分为互相不干扰的left，right部分是因为ith定义是最后一个burst，要ith定义是先burst，就会出现left，right部分dependent关系，right部分数值取决于left最右一个气球是否burst。所以定义ith气球最后一个burst是很聪明的解决了分治法左右depenent问题。2）Bottom-Up dp 算 dp【left】【right】必须知道dp【left】【i-1】和dp【i+1】【right】 i在left right之间，所以dp更新路线是从右下角zigzag更新。
313. Super Ugly Number （Medium）
A super ugly number is a positive integer whose prime factors are in the array primes.
Given an integer n and an array of integers primes, return the nth super ugly number.
The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
dp = [0]*n
t = [0]*len(primes)
dp[0]=1
for i in range(1,n):
dp[i]=min(dp[t[ii]]*primes[ii] for ii in range(len(primes)))
for j in range(len(primes)):
if dp[i]==dp[t[j]]*primes[j]:
t[j]+=1
return dp[-1]
# dp = [0] * n
# t2 = t3 = t5 = 0
# dp[0] = 1
# for i in range(1,n):
# dp[i] = min(dp[t2]*2,dp[t3]*3,dp[t5]*5)
# if(dp[i] == dp[t2]*2): t2 += 1
# if(dp[i] == dp[t3]*3): t3 += 1
# if(dp[i] == dp[t5]*5): t5 += 1
# return dp[-1]
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
dp=[1]
res=1
s=set()
for _ in range(n):
while res in s:
res = heapq.heappop(dp)
s.add(res)
for p in primes:
heapq.heappush(dp,res*p)
return res
#ANSWER
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
uglies = [1]
def gen(prime):
for ugly in uglies:
yield ugly * prime
merged = heapq.merge(*map(gen, primes))
while len(uglies) < n:
ugly = next(merged)
if ugly != uglies[-1]:
uglies.append(ugly)
return uglies[-1]
仿照ugly unmber II 写出一个dp的解但time limit excceded。 用heapq还是time limit excceded。 这个题目python不友好， 答案用了generator。
314. Binary Tree Vertical Order Traversal （Medium）
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
dic = dict()
def pre(root,level,hight):
hight+=1
if not root: return
if level not in dic:
dic[level]=[]
dic[level].append((root.val,hight))
pre(root.left,level-1,hight)
pre(root.right,level+1,hight)
pre(root,0,0)
res= [ [val[0] for val in sorted(v,key=lambda x:x[1])] for k,v in sorted(dic.items(),key=lambda x:x[0])]
return res
记录左右移动同时记录上下移动。
315. Count of Smaller Numbers After Self （Hard）
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].
Input: nums = [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.
# 找出 i-1 到 -inf 的cumsum ，而且update 从右往左。
# -OFFSET ~0 ~ OFFSET
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
class ST:
def __init__(self,n):
self.n = n
self.bit = [0]*(2*self.n)
# 1
# 2 3
# 4 5 6 7
# @ 1 2 3 4 5 6 7
#
def update(self,ind):
ind = ind+self.n
self.bit[ind]+=1
while ind>0:
l = ind
r = ind
if ind%2==0:
r+=1
else:
l-=1
if ind//2>0:
self.bit[ind//2] = self.bit[l]+self.bit[r]
ind//=2
def query(self,l,r):
res = 0
l+=self.n
r+=self.n
while l<=r:
if r%2 ==0:
res+=self.bit[r]
r-=1
if l%2==1:
res+=self.bit[l]
l+=1
l//=2
r//=2
return res
OFFSET = 10000
size = 1+ 2*OFFSET
st = ST(size)
res = []
for n in reversed(nums):
n = n+OFFSET
res.append(st.query(0,n-1))
st.update(n)
return res[::-1]
#ANSWER 2
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
class BIT:
def __init__(self,size):
self.size = size
self.bit = [0]*(self.size+1)
def update(self,ind):
while ind<= self.size:
self.bit[ind]+=1
ind += ind&-ind
def query(self,ind):
res =0
while ind>0:
res+=self.bit[ind]
ind -= ind&-ind
return res
OFFSET = 10000
size = 1+ 2*OFFSET
bit = BIT(size)
res = []
for n in reversed(nums):
n = n+OFFSET+1
res.append(bit.query(n-1))
bit.update(n)
return res[::-1]
#ANSWER3
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
def sort(enum):
half = len(enum) // 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
m, n = len(left), len(right)
i = j = 0
while i < m or j < n:
if j == n or i < m and left[i][1] <= right[j][1]:
enum[i+j] = left[i]
smaller[left[i][0]] += j
i += 1
else:
enum[i+j] = right[j]
j += 1
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller
错误以为用stack可以解决~~，答案方法1）Segment Tree 2）Binary index Tree 3)Merge Sort,当选取左边元素，记录 smaller[left[i][0]] += j ； left【i】【0】是左边元素在原始数组种的index， j是right中未被选中元素的index，恰巧是小于左边被选中元素的在右边需要变换位置元素的长度。
316. Remove Duplicate Letters （Medium）
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
# maintain smalleset lexicographical order How?
# find pos - the index of the leftmost letter in our solution
# we create a counter and end the iteration once the suffix doesn't have each unique character
# pos will be the index of the smallest character we encounter before the iteration ends
c=Counter(s)
pos=0
for i in range(len(s)):
if s[i]<s[pos]:
pos=i
c[s[i]]-=1
if c[s[i]]==0:
break
return s[pos]+self.removeDuplicateLetters(s[pos:].replace(s[pos],"")) if s else ''
#ANSWER
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack=[]
seen=set()
last_occurrence = {c:i for i,c in enumerate(s)}
for i,c in enumerate(s):
if c not in seen:
#只有c不在seen中才能试图在stack中加c
while stack and c<stack[-1] and i<last_occurrence[stack[-1]]:
# 如果当前试图加入的c<stack[-1] 而且 c的位置< stack[-1]最后出现位置
# 可以安全移除stack【-1】
val=stack.pop()
seen.discard(val)
seen.add(c)
stack.append(c)
return ''.join(stack)
思路1） 找到第一个qualify的pos，s【i】小于s【pos】需要更新pos成i，当counter s【i】==0时候说明s【i】是当前必须加入结果的字符，然后找下一个字符用recursive方法。
思路2） 见代码 Greedy 方法的应用
317. Shortest Distance from All Buildings （Hard）
You are given an m x n grid grid of values 0, 1, or 2, where:
each 0 marks an empty land that you can pass by freely,
each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.
You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.
Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.
#METHOD 1 BFS from Biulding
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
#Use hit to record how many times a 0 grid has been reached and use distSum to record the sum of distance from all 1 grids to this 0 grid. A powerful pruning is that during the BFS we use count1 to count how many 1 grids we reached. If count1 < buildings then we know not all 1 grids are connected are we can return -1 immediately, which greatly improved speed (beat 100% submissions).
if not grid or not grid[0]: return -1
M, N, buildings = len(grid), len(grid[0]), sum(val for line in grid for val in line if val == 1)
hit, distSum = [[0] * N for i in range(M)], [[0] * N for i in range(M)]
def BFS(start_x, start_y):
visited = [[False] * N for k in range(M)]
visited[start_x][start_y], count1, queue = True, 1, collections.deque([(start_x, start_y, 0)])
while queue:
x, y, dist = queue.popleft()
for i, j in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= i < M and 0 <= j < N and not visited[i][j]:
visited[i][j] = True
if not grid[i][j]:
queue.append((i, j, dist + 1))
hit[i][j] += 1
distSum[i][j] += dist + 1
elif grid[i][j] == 1:
count1 += 1
return count1 == buildings
for x in range(M):
for y in range(N):
if grid[x][y] == 1:
if not BFS(x, y): return -1
return min([distSum[i][j] for i in range(M) for j in range(N) if not grid[i][j] and hit[i][j] == buildings] or [-1])
#METHOD 2 BFS from Empty space
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
M=len(grid)
N=len(grid[0])
totalHouses = sum([v for row in grid for v in row if v==1])
minDistance=float('inf')
def bfs(row,col):
distanceSum=0
housesReached=0
visited =[[False]*N for _ in range(M)]
q=collections.deque()
q.append((row,col))
step=0
while q and housesReached!=totalHouses:
l=len(q)
for _ in range(l):
row,col=q.popleft()
if grid[row][col]==1:
distanceSum+=step
housesReached+=1
continue
for new_row,new_col in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
if M>new_row>=0 and N>new_col>=0:
if not visited[new_row][new_col] and grid[new_row][new_col]!=2:
visited[new_row][new_col]=True
q.append((new_row,new_col))
step+=1
if housesReached!=totalHouses:
for row in range(M):
for col in range(N):
if grid[row][col]==0 and visited[row][col]:
grid[row][col]=2
return float('inf')
return distanceSum
#main
for row in range(M):
for col in range(N):
if grid[row][col]==0:
minDistance=min(minDistance,bfs(row,col))
if minDistance==float('inf'):
return -1
return minDistance
直接看答案了。。。。方法一更好点， 从building处做BFS，保存hits数目。BFS返回count1==#Buildings 这样可以提前截断如果存在不能完全到达所有building情况。
关键是在每一个点都做BFS。不能做一次BFS就出结果。
318. Maximum Product of Word Lengths （Medium）
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
class Solution:
def maxProduct(self, words: List[str]) -> int:
ss = [set() for _ in range(len(words))]
for i,word in enumerate(words):
for w in word:
ss[i].add(w)
res=float('-inf')
for i in range(len(words)-1):
for j in range(i+1,len(words)):
if not ss[i] & ss[j]:
res=max(res,len(words[i])*len(words[j]))
return res if res!=float('-inf') else 0
#ANSWER
from collections import defaultdict
class Solution:
def maxProduct(self, words: List[str]) -> int:
hashmap = defaultdict(int)
bit_number = lambda ch : ord(ch) - ord('a')
for word in words:
bitmask = 0
for ch in word:
# add bit number bit_number in bitmask
bitmask |= 1 << bit_number(ch)
# there could be different words with the same bitmask
# ex. ab and aabb
hashmap[bitmask] = max(hashmap[bitmask], len(word))
max_prod = 0
for x in hashmap:
for y in hashmap:
if x & y == 0:
max_prod = max(max_prod, hashmap[x] * hashmap[y])
return max_prod
答案用了bitmask作为key来优化。思路很好。
319. Bulb Switcher （Medium）
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(math.sqrt(n))
这题比较tricky， 灯泡1到n， 只有灯泡被拨动奇数次才会亮， 比如第i个灯泡，i%round==0时候会被拨动一次， 这样第i个灯泡比如第12个，1，12，2，6，3，4轮时候会被拨到，但是对于完全平方数，比如36个灯泡，1，36，2，18，3，12，4，9，6轮时候会被拨到但为奇数轮。所以找到有多少个完全平方数在1到n之间就可以了。
320. Generalized Abbreviation （Medium）
A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths.
For example, "abcde" can be abbreviated into:
"a3e" ("bcd" turned into "3")
"1bcd1" ("a" and "e" both turned into "1")
"5" ("abcde" turned into "5")
"abcde" (no substrings replaced)
However, these abbreviations are invalid:
"23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
"22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.
Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.
#ANSWER
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
def rec(idx, curr_list):
if idx == L:
res.append(''.join(curr_list))
return
#Abbreviate
if curr_list and curr_list[-1].isdigit():
curr_list[-1] = str(int(curr_list[-1]) + 1)
rec(idx + 1, curr_list)
curr_list[-1] = str(int(curr_list[-1]) - 1)
else:
rec(idx + 1, curr_list + ['1'])
#Not to abbreviate
rec(idx + 1, curr_list + [word[idx]])
L = len(word)
res = []
rec(0, [])
return res
#MY ANSWER
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
if len(word)==1: return ["1",word]
head = word[0]
rest = word[1:]
res = []
for tmp in self.generateAbbreviations(rest):
if tmp[0].isdigit():
i = 0
while i<len(tmp) and tmp[i].isdigit():
i+=1
res.append(str(int(tmp[:i])+1)+tmp[i:])
res.append(head+tmp)
else:
res.append('1'+tmp)
res.append(head+tmp)
return res
这题只能backtracking解，从第一个位置开始逐个击破。