LeetCode 1706. Where Will the Ball Fall
LC75學習計畫。這題的圖例嚇到我了,看起來有夠複雜,還以為是併查集類型,結果不是。
題目
矩陣grid,代表一個m*n的盒子,盒子的頂部和底部都是打開的。
盒子中的每個格子都有一個斜放的板子,可以將球導向左方或是右方:
- 若板子為左上向右下放,則記為1
- 若板子為右上向左下放,則記為-1
我們在盒子每一列的頂部放一個球,球有可能在中途被板子堵住,或是順利掉出盒子外。
回傳長度為n的陣列answer,其中answer[i]代表球從第i列放入後,最後出來的列數。若在中途被堵住,則回傳-1。
解法
球抵達某個格子(r,c)後,只可能發生三種情形:
- 被卡住
- 往左下滾
- 往右下滾
定義dp(r,c):球從(r,c)出發,最後離開盒子的列數。
轉移方程式:若板子為右斜且沒被卡住,則dp(r+1,c+1);若板子為左斜且沒被卡住,則dp(r+1,c-1);否則-1。
base case:當r等於M時,代表順利掉出盒子外,直接回傳當前列數c。
有以下四種情形會被卡住:
- 球往左滾碰到牆壁
- 球往左滾碰到向右的板子
- 球往右滾碰到牆壁
- 球往右滾碰到向左的板子
最後分別對最上方的每一列投入球,加到答案中即可。
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
M,N=len(grid),len(grid[0])
@cache
def dp(r,c):
if r==M:
return c
if grid[r][c]==1:
if c==N-1 or grid[r][c+1]!=1:
return -1
return dp(r+1,c+1)
else:
if c==0 or grid[r][c-1]!=-1:
return -1
return dp(r+1,c-1)
ans=[]
for c in range(N):
ans.append(dp(0,c))
return ans
看到lee神的解法才驚覺,或許右斜、左斜板子分別設為1和-1是有設計過的,否則為何不是1和0呢?是我沒有猜透出題者的心思。
雖然執行時間慢了一些,但是邏輯看起來更清晰易懂。
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
M,N=len(grid),len(grid[0])
@cache
def dp(r,c):
if r==M:
return c
cc=c+grid[r][c]
if cc<0 or cc==N or grid[r][c]!=grid[r][cc]:
return -1
return dp(r+1,cc)
ans=[]
for c in range(N):
ans.append(dp(0,c))
return ans