推 SecondRun: 滿好玩的 11/04 12:41
→ Rushia: 我覺得這題好難ㄛ 11/04 15:02
→ ZooseWu: 我覺得思路真的超難 我想了半小時真的想不到去看提示 11/04 19:37
→ NTHUlagka: 這題某次周賽有出過一次 當時吃過虧 今天看到這題類似 11/04 22:43
→ NTHUlagka: 題就直接想到 被搞過一次真的就忘不了 11/04 22:43
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