Review list 3

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:return -1
R, C = len(grid), len(grid[0])
dp = [[0]*C for _ in range(R)]
dp[0][0] = grid[0][0]
for i in range(R):
for j in range(C):
if i==0 and j==0:continue
dp[i][j] += min(dp[i-1][j] if i-1>=0 else float('inf'), dp[i][j-1] if j-1>=0 else float('inf')) + grid[i][j]
return dp[-1][-1]
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0] or matrix[-1][-1]<target or matrix[0][0]>target:return False
R, C = len(matrix), len(matrix[0])
l, r =0 , R*C-1
while l<=r:
m = (l+r)//2
i, j =m//C, m%C
if matrix[i][j]==target:return True
elif matrix[i][j]<target:
l = m+1
else:
r = m-1
return False
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
if not board or not board[0]:return -1
R, C = len(board), len(board[0])
T =R*C
def bfs():
Q = collections.deque([(1,0)])
seen = {1}
while Q:
loc, d = Q.popleft()
if loc == T:return d
for k in range(1, 7):
new_loc = loc+k
if new_loc<=T:
i, j = (new_loc-1)//C, (new_loc-1)%C
if i%2==1: j = C-1-j
i = R-1-i
if board[i][j]!=-1:
new_loc = board[i][j]
if new_loc not in seen:
seen.add(new_loc)
Q.append((new_loc, d+1))
return -1
return bfs()

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi