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