1706. Where Will the Ball Fall
調皮的龍大把一排彈珠丟到箱子裡，想看有幾個彈珠能掉到底部，因為他真的很調皮
彈珠落下的規則參考 https://assets.leetcode.com/uploads/2019/09/26/ball.jpg
可以想像成箱子的每一格都有一個檔板
都收到說明了吧，給我回傳每個彈珠的最後位置，卡在箱子裡的話就是-1
Example 1:
Input: grid =
[[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
就是上面那張圖
思路:
1.彈珠一開始的位置就是 range(n) 每往下一層會往左或往右一格
維護一個每個彈珠位置的陣列 每層更新他的新位置
如果檔板是\ -> 右邊也是\就會往右 不然就會卡住 或是掉出箱子
如果檔板是/ -> 左邊也是/就會往左 不然就會卡住 或是掉出箱子
2.可以先 iterate n 失敗(位置變成-1)的時候直接 break
可以省一點時間 但複雜度不變
for i in range(m): for j in range(n):
for j in range(n): -> for i in range(m):
if ball[j] == -1: if ball[j] == -1:
continue break
3.
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
ball = list(range(n))
for j in range(n):
for i in range(m):
if ball[j] == -1:
break
if grid[i][ball[j]] == 1:
ball[j] = -1 if ball[j] == n-1 or grid[i][ball[j]+1] ==
-1 else ball[j]+1
elif grid[i][ball[j]] == -1:
ball[j] = -1 if ball[j] == 0 or grid[i][ball[j]-1] == 1
else ball[j]-1
return ball