Re: [閒聊] 每日LeetCode

看板Marginalman作者fxfxxxfxx (愛麗絲)時間1年前 (2023/01/05 10:58)推噓4(4推 0噓 10→)

留言14則, 5人參與討論串179/719 (看更多)

452. Minimum Number of Arrows to Burst Balloons 今天的題目蠻有水準的，我覺得很值得寫方法很容易想，要證明卻不是很容易給你一堆區間，[x_{start}, x_{end}], ... 要你找出一組 a_1, ..., a_n 使得每個區間都包含至少一個點問所需最少的點的數量直覺上就是要找出最長的不重疊區間序列剩下的是證明這是最佳解首先，很明顯最佳解一定 >= 這個序列的長度因為兩兩都不重疊，一個點最多對應到一個區間答案不可能比這還要好剩下的是去證最佳解 <= 這個序列的長度也就是真的能建構出一組和這個序列一樣長的解老實說我想了一陣子也不知道怎麼證後來發現從我實作最長不重疊區間的演算法來證的話變得很容易先對右端點做排序，接著對每一個新的區間如果加入後不會重疊就加入，否則捨棄我發現如果不斷將點設在加入的區間的最右端因為被捨棄掉代表他包含了某個我們加入的區間的右端點自然而然最後的結果是一組合法的解再根據之前說的，答案不可能比最長不重疊序列好所以最佳解不多不少就是最長不重疊序列至於這個演算法的結果為什麼是最長不重疊區間我們可以證明，考慮完一個新的區間之後的結果都是有最小右端點的最佳解對於一個新的區間，有兩種可能，加入或不加入如果跟原本的解不重疊當然加入一定是當下唯一的最佳解如果重疊的話，因為目前的答案是有最小右端點的最佳解因此所有最佳解都一定和新的點重疊，加入一定不會比較好，可以直接捨棄 class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { using T = pair<int, int>; sort(points.begin(), points.end(), [](const auto& x, const auto& y){ return T{x[1], x[0]} < T{y[1], y[0]}; }); int ans = 0; int64_t prev = numeric_limits<int64_t>::min(); for (auto& p: points) { int st = p[0], ed = p[1]; if (st <= prev) continue; prev = ed; ans += 1; } return ans; } }; 這題還蠻不錯的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672887521.A.6B6.html

→

Jaka

01/05 10:59, 1年前 , 1^F

01/05 10:59, 1^F

推

PyTorch

01/05 10:59, 1年前 , 2^F

01/05 10:59, 2^F

→

Rushia

01/05 12:36, 1年前 , 3^F

01/05 12:36, 3^F