※ 引述《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
思路差不多
速度是满快的 但空间就不太行 明天看看解答