Re: [閒聊] 每日LeetCode

看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間3月前 (2024/02/20 23:38)推噓2(2推 0噓 2→)

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

1642. Furthest Building You Can Reach 前幾天的一開始想都不想直接DFS 當然是TLE 浪費了幾分鐘後來想想應該就greedy 一開始先全用brick 當brick不夠用的時候回頭把用最多brick的那一階換成梯子大概是這樣不過出來速度幾乎墊底捏== 感覺跟大部分人的solution差不多才是我也懶得檢查ㄌ我好爛 int furthestBuilding(vector<int>& heights, int bricks, int ladders) { int idx; priority_queue<int> diffs; for(idx=1; idx<heights.size(); idx++) { if(heights[idx-1] >= heights[idx]) { continue; } else { int diff = (heights[idx] - heights[idx-1]); // using bricks first bricks = bricks - diff; diffs.push(diff); // check if bricks ran out if(bricks < 0) { // use one ladder if(!diffs.empty() && ladders>0) { int max_diff_bricks = diffs.top(); bricks += max_diff_bricks; ladders -= 1; diffs.pop(); } else { // can't reach break; } } } } return idx-1; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.252.52 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708443520.A.88A.html

→

medama

02/20 23:38, 3月前 , 1^F

02/20 23:38, 1^F

推

ILoveErr

02/20 23:39, 3月前 , 2^F

02/20 23:39, 2^F

※ 編輯: DJYOSHITAKA (114.137.252.52 臺灣), 02/20/2024 23:39:29

→

JIWP

02/20 23:45, 3月前 , 3^F