Re: [閒聊] 每日LeetCode已回收
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
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667276312.A.E35.html
推
11/01 12:24,
3年前
, 1F
11/01 12:24, 1F
推
11/01 14:14,
3年前
, 2F
11/01 14:14, 2F
推
11/01 20:49,
3年前
, 3F
11/01 20:49, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 77 之 719 篇)：