Re: [閒聊] 每日LeetCode
1503. Last Moment Before All Ants Fall Out of a Plank
在長度n的木棍上有一群螞蟻
螞蟻會以每秒1單位往左或往右走
如果螞蟻遇到對象螞蟻
兩隻螞蟻就會轉頭繼續走
然後螞蟻一旦走到邊緣就會馬上掉下去
求木棍上最後一隻螞蟻掉下去的時間點
範例:
Input: n = 4, left = [4,3], right = [0,1]
Output: 4
直接看圖 https://assets.leetcode.com/uploads/2020/06/17/ants.jpg
在t=4的時候B跟C螞蟻掉下去
First think:
我一直在思考有沒有一個方法
可以有系統的找到最後一隻掉落的螞蟻
以及牠走的路徑
感覺不管是用tree還是DP什麼的都感覺沒辦法
到最後我還是沒有想到一個好方法
然後我就去看提示了
提示:
兩隻螞蟻見面後轉頭跟見面後不轉投的路徑是一樣的
Approach:
看完提示豁然開朗
我太執著幫螞蟻貼編號
然後去研究螞蟻B在哪邊遇到哪隻螞蟻
轉了幾次、最後往哪走
但B跟C相遇之後
C接著會走B的路徑
B接著會走C的路徑
所以把編號拔掉的話
螞蟻B等義於一直往右走到底最後掉下去
這樣的話答案就很簡單了
找最左邊往右走的螞蟻
以及最右邊往左走的螞蟻最長的那隻
TS code:
function getLastMoment (n: number, left: number[], right: number[]): number {
const rightLength = right.map((x) => (n - x))
return Math.max(...left, ...rightLength)
}
這題蠻有趣的
計算非常簡單
但是要思考怎麼簡化複雜的題目
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699072788.A.8B9.html
推
11/04 12:41,
2年前
, 1F
11/04 12:41, 1F
→
11/04 15:02,
2年前
, 2F
11/04 15:02, 2F
→
11/04 19:37,
2年前
, 3F
11/04 19:37, 3F
→
11/04 22:43,
2年前
, 4F
11/04 22:43, 4F
→
11/04 22:43,
2年前
, 5F
11/04 22:43, 5F
討論串 (同標題文章)
完整討論串 (本文為第 487 之 719 篇)：