※ 引述《yam276 (史萊哲林的優等生)》之銘言：
: ※ 引述《oin1104 (是oin的說)》之銘言：
: : 題目：
: : 給你一串氣球陣列
: : 用垂直x軸的箭射破他們
: : 擦到邊就可以了
: 先用右邊界整理
: 然後開始射飛鏢
: 在邊界外代表要多射一支
: Code:
: impl Solution {
: pub fn find_min_arrow_shots(mut points: Vec<Vec<i32>>) -> i32 {
: points.sort_unstable_by_key(|k| k[1]);
: let mut result = 1;
: let mut arrow_pos = points[0][1];
: for i in 1..points.len() {
: if points[i][0] > arrow_pos {
: result += 1;
: arrow_pos = points[i][1];
: }
: }
: result
: }
: }
: 別人跟鬼一樣的的FP魔術詠唱：
: impl Solution {
: pub fn find_min_arrow_shots(mut points: Vec<Vec<i32>>) -> i32 {
: points.sort_unstable_by_key(|b| b[1]);
: points.iter().skip(1).fold((1, points[0][1]), |(rez, right), b|
: if right < b[0] {
: (rez + 1, b[1])
: } else {
: (rez, right)
: }
: ).0
: }
: }
Python Code:
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key = lambda x: x[1])
res = 0
cur = 0
for x in points:
if cur == 0:
cur = x[1]
res += 1
else:
if x[0] > cur:
res += 1
cur = x[1]
return res
思路差不多
速度是滿快的 但空間就不太行 明天看看解答