[閒聊] 每日leetcode 75 - Day9 -2

[yam276 (史萊哲林的優等生)]

735. Asteroid Collision


題目：

一堆小行星沿著 x 軸在飛

方向不同會碰撞

大顆的贏繼續飛

一樣大顆的會互爆

求他們撞完長怎樣


思路：

以前用 C++ 刷過 但好久以前都忘了

用 Vec 當 Stack 功能都有

每次看現在的小行星會不會跟原本 Stack top 的碰撞

撞贏繼續撞 continue

一樣就 pop 前一顆 把這一顆設為 0 然後 break

撞輸就只把這一顆設為 0 然後 break

如果檢定完他不是 0 加入 Stack


這樣能不用處理第一顆 因為一定會加入



Code:

impl Solution {
    pub fn asteroid_collision(asteroids: Vec<i32>) -> Vec<i32> {
        let mut stack = Vec::new();

        for asteroid in asteroids {
            let mut asteroid = asteroid;

            while let Some(&top) = stack.last() {
                if top > 0 && asteroid < 0 {
                    if top < -asteroid {
                        stack.pop();
                        continue;
                    } else if top == -asteroid {
                        stack.pop();
                        asteroid = 0;
                        break;
                    } else {
                        asteroid = 0;
                        break;
                    }
                } else {
                    break;
                }
            }

            if asteroid != 0 {
                stack.push(asteroid);
            }
        }

        stack
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749632196.A.324.html
※ 編輯: yam276 (60.248.143.172 臺灣), 06/11/2025 16:57:10