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)
}
这题蛮有趣的
计算非常简单
但是要思考怎么简化复杂的题目