LeetCode

問題概要 整数で表される小惑星の配列 asteroids が与えられる。各小惑星について： 絶対値：大きさ 符号：方向（正=右、負=左） 全て同じ速度で移動 衝突ルール： 小さい方が爆発 同じ大きさなら両方爆発 同じ方向に移動する小惑星は衝突しない 全ての衝突後の状態を返せ。 失敗した実装 from collections import deque class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for aster in asteroids: if len(stack) <= 0 or (aster <= 0) == (stack[-1] <= 0): stack.append(aster) else: while len(stack) > 0 and (aster <= 0) != (stack[-1] <= 0) and abs(aster) > abs(stack[-1]): stack.pop() if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0): stack.append(aster) elif abs(aster) == abs(stack[-1]): stack.pop() return stack 問題点 同じ条件判定 if len(stack) <= 0 or (stack[-1] <= 0) == (aster <= 0) が2箇所に重複 制御フローが複雑で読みにくい (aster <= 0) != (stack[-1] <= 0) は「符号が異なる」を検出するが、衝突しないケースも含む 最適解 class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for asteroid in asteroids: while stack and asteroid < 0 < stack[-1]: # 右向き vs 左向きの衝突が発生 if abs(stack[-1]) < abs(asteroid): # 右向きが小さい → 爆発して次の右向きとも衝突判定 stack.pop() continue elif abs(stack[-1]) == abs(asteroid): # 同じ大きさ → 両方爆発 stack.pop() break else: # 衝突しなかった or 左向きが勝った stack.append(asteroid) return stack わかったこと 1. ループ条件の本質 asteroid < 0 < stack[-1] これは (asteroid < 0) and (0 < stack[-1]) と同じ。つまり： ...

DFS, BFSがわかりづらかったので、いくつかの記事を見て個人的に感じた疑問や 「こういうコード例が欲しい」という要望を踏まえて生成AIに生成してもらった。 生成された内容を検証し、コードを実際に動かして確認したところ、 自分の理解が深まる良い記事になったので、このまま公開することにした。 はじめに LeetCodeでMedium問題を解いていると、必ず遭遇するのがDFS（深さ優先探索）とBFS（幅優先探索）だ。 「Dは深さ、Bは幅」というのは知っている。でも、なぜスタックとキューを使い分けるのか？その本質を理解している人は意外と少ない。 今回は、入れ子リストの例を使って、DFS/BFSの動作原理とデータ構造の関係を視覚的に解説する。 問題設定：入れ子リストをフラット化する 以下のような入れ子構造のリストがあるとする。 data = [1, [4, 5, [6, 7, 8], 2], 3] これをフラットな配列にしたい。このとき、「どの順番で要素を取り出すか」がDFS/BFSの違いだ。 ツリー構造として可視化する 入れ子リストは、実はツリー構造として表現できる。 root / | \ 1 [] 3 | /|\ \ 4 5 [] 2 | /|\ 6 7 8 この木をどう巡回するかで、DFSとBFSが決まる。 DFS（深さ優先探索）：とにかく深く潜る 動作イメージ 「見つけた枝があれば、まずそこを最後まで探索する」 訪問順序： 1 → [中に入る] → 4 → 5 → [さらに中] → 6 → 7 → 8 → [戻る] → 2 → [戻る] → 3 結果：[1, 4, 5, 6, 7, 8, 2, 3] ...