Re: [閒聊] 每日LeetCode

看板Marginalman作者ZooseWu (動物園公告)時間2年前 (2023/11/08 11:59)推噓4(4推 0噓 2→)

留言6則, 6人參與討論串498/719 (看更多)

2849. Determine if a Cell Is Reachable at a Given Time 在一個無限大的二維網格中你從start(sx,sy)開始每秒移動到鄰近格子如果你能在第t秒的時候待在finish(fx,fy)則回傳true 否則回傳false * 鄰近格子代表相鄰的八格，允許走到已經走過的格子例題: Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6 Output: true 從(2,4)開始[右,右,右,右下,下,右下]可以到達終點(7,7) https://assets.leetcode.com/uploads/2023/08/05/example2.svg Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3 Output: false 最短需要四秒才能到達 https://assets.leetcode.com/uploads/2023/08/05/example1.svg Intuition: 題目不只能走上下左右而是相鄰的八格都能移動所以走的方法很自由重點在於有沒有辦法在時限內到終點 Approach: 這題的起點座標跟終點座標完全不重要重要的是兩個座標之間的水平距離dx以及垂直距離dy。根據題目描述我們移動能選擇鄰近八格這代表我們從起點開始花費四步能走到下圖中所有紫色的格子： https://i.imgur.com/zRGHyqj.png

同理綠色是兩步能到達的位置、青色三步因此我們可以知道走到終點最少需要的步數是dx及dy取大值。但是題目的要求不是有沒有辦法在t步以內走到而是有沒有辦法在第t步時待在目標格子中我們可以透過下面的方法讓我們的步數增加到在第t步的時候待在終點：如果目標步數跟最短步數差一格的話我們可以把往橫一步改成往斜一步再往直回來往斜同理可以換成往橫後再往直讓一步變成兩步像是下圖這樣：https://i.imgur.com/blQYdKt.png

如果差超過兩格的話就來回走動直到結束或只差一步然後用上面的方法到終點例如下圖就是透過上面的方法用不同步數從紅色到藍色的範例路徑： https://i.imgur.com/jnOYkfP.png

所以任何t大於最低所需步數的情況我們都不用考慮只要判斷能不能在時限內到終點就好這題我原本以為到這邊就結束了提交後報錯才發現這個邊界案例dx = dy = 0, t = 1 是唯一沒辦法透過上面的方法去達到終點的狀況 TS Code: function isReachableAtTime (sx: number, sy: number, fx: number, fy: number, t: number): boolean { const [dx, dy] = [Math.abs(fx - sx), Math.abs(fy - sy)] if ((dx + dy) === 0 && t === 1) return false return Math.max(dx, dy) <= t }; C# Code: public class Solution { public bool IsReachableAtTime(int sx, int sy, int fx, int fy, int t) { int dx = Math.Abs(fx - sx), dy = Math.Abs(fy - sy); if ((dx + dy) == 0 && t == 1) return false; return Math.Max(dx, dy) <= t; } } 另外請教LeetCode大師為什麼我寫的文章別人都看不到只有我自己看的到？ https://leetcode.com/Zoosewu/ 是因為沒有買高級會員嗎？ -- Zoosewu Yoututbe顯示PTT推文可以在各個網站追實況或Live時使用預覽圖: https://i.imgur.com/ZhtXdAJ.png

https://i.imgur.com/WqbLNV3.png

完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage 支援的網站: Youtube Twitch Holotools Niji-mado Holodex -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699415969.A.C2B.html ※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/08/2023 11:59:53

推

sustainer123

11/08 12:02, 2年前 , 1^F

11/08 12:02, 1^F

推

SecondRun

11/08 12:07, 2年前 , 2^F

11/08 12:07, 2^F

推

oin1104

11/08 12:21, 2年前 , 3^F

11/08 12:21, 3^F