配列操作編

二分探索と要素削除

二分探索：境界条件の2つの実装方法に注意。rightの定義、if条件と境界更新ロジックが重要。

	左閉右閉	左閉右開
rightの定義	len(arr) - 1	len(arr)
ループ条件	while left <= right:	while left < right:
境界更新	right = mid - 1	right = mid

class Solution:
    def binary_search(self, arr: List[int], target: int) -> int:
        """
        左閉右閉の実装
        """
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if arr[mid] > target:
                right = mid - 1
            elif arr[mid] < target:
                left = mid + 1
            else:
                return mid
        
        return -1

        """
        左閉右開の実装
        """
        left, right = 0, len(arr)

        while left < right:
            mid = left + (right - left) // 2

            if arr[mid] > target:
                right = mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                return mid
            
        return -1

要素削除：ダブルポインタ手法。高速ポインタが新しい配列の要素を探し、低速ポインタがインデックスを更新。

class Solution:
    def remove_element(self, arr: List[int], val: int) -> int:
        """
        ダブルポインタの実装
        """
        fast = 0
        slow = 0

        while fast < len(arr):
            if arr[fast] != val:
                arr[slow] = arr[fast]
                slow += 1

            fast += 1
        return slow

スライディングウィンドウと特殊配列処理

最小部分配列：スライディングウィンドウ問題。部分配列の合計が目標値以上になったとき、startを後方に移動し、合計からstartの値を引く。

"""
最小スライディングウィンドウのテンプレート
"""
while end < len(arr):
    # [start, end]が条件を満たすか判定
    while 条件を満たす:
        # 結果を更新（while内で更新！）
        result = min(result, end - start + 1)
        start += 1  # ウィンドウを可能な限り小さくする
    end += 1

螺旋行列：面接で頻出！境界条件の処理に「左閉右開」を一貫して使用。

連結リスト編

基本操作と反転

要素削除：仮想ヘッドノードを使用する方法。

リスト設計：連結リストの各種操作を実装。

リスト反転：面接で頻出！ダブルポインタ法、cur = head、pre = Noneとし、ループ内でtemp = cur.nextを保存。

class Solution:
    def reverse_list(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
            
        return prev

高度な操作

ノードのペア交換：仮想ヘッドノード法。2つの一時ノードを記録する必要あり。

末尾からN番目の削除：ダブルポインタの古典的アプローチ。

交点検出：まず各リストの長さを計算し、末尾を揃えて交点を探索。

サイクル検出：ダブルポインタ法。速いポインタは2ステップ、遅いポインタは1ステップ進める。サイクルの開始点を特定するには、出会った点とヘッドから同速で進める。

ハッシュテーブル編

基礎問題

有効なアナグラム：要素数が少ない場合は配列を使用。まず文字列sを走査し各文字の出現回数を記録、次にtを走査して減算。

配列の交差：テストではsetを直接使用。面接では配列を使用し、共通要素を比較。

幸福数：平方和が以前に出現したかどうかを判断。

2数の和：テストでは力任せ法。面接ではハッシュテーブルを使用。

応用問題

4数の和Ⅱ：4つの数を2組に分け、最初の2数の和の可能性を計算し、後の2数の和の反数が最初の2数の和のmapに存在するかを確認。

ランサムノート：242.有効なアナグラムと同様の考え方。

3数の和：まず配列をソート。3つのポインタi、left=i+1、right=len(arr)-1を使用。重複排除に注意。

4数の和：3数の和にさらに1層のループを追加。枝刈りと重複排除に注意。

文字列編

基礎操作

文字列反転：ダブルポインタ法、reversed()、スライス、s.reverse()など複数の方法。

部分文字列反転：スライディングウィンドウ法。2kステップごとに進み、最初のk文字のみを反転。

数字置換：isdigit()で数字かどうかを判断。

高度な処理

単語反転：まず余分な空白を削除し、文字列全体を反転し、最後に各単語を反転。

文字列検索：テストでは直接findを使用。面接ではKMPアルゴリズムを実装。

繰り返し部分文字列：テストではfindや力任せ法。面接ではKMP。

スタックとキュー編

基本実装

スタックによるキュー：2つのスタックを使用。1つは入力用、1つは出力用。

キューによるスタック：1つのキューを使用してスタックを実装。

有効な括弧：左括弧に遭遇したら対応する右括弧をスタックに追加。同じ括弧に遭遇したらpop、異なる場合はfalse。最後にスタックが空なら有効。

隣接重複削除：要素をスタックに追加し、同じ要素に遭遇したらpop。最終的にスタック内の要素を返す。

応用問題

逆ポーランド記法：スタックの応用。演算子に遭遇したら計算し、結果をスタックにプッシュ。演算順序に注意（num2 演算子 num1）。

スライディングウィンドウ最大値：方法1：力任せ法（O(n × k)）。方法2：単調キューを使用。最大値になる可能性のある要素のみを維持。

高頻度要素：方法1：ソート。方法2：最小ヒープを使用し、小さい要素をpopしていき、k個の要素を残す。

二分木編

基礎概念と走査

二分木の基本：完全二分木、完全二分木、二分探索木、平衡二分探索木。

再帰的三部作： 1. 再帰関数のパラメータと戻り値を決定 2. 終了条件を決定 3. 単一レベルの再帰ロジックを決定

"""
再帰法のテンプレート、走査順序は自由に調整可能
"""
def dfs(node):
    if node is None:
        return
    
    result.append(node.val)  # 中間順
    dfs(node.left)          # 左部分木
    dfs(node.right)         # 右部分木

レベル順走査：

"""
レベル順走査のテンプレート
"""
def level_order(self, root: Optional[TreeNode]) -> List[List[int]]:
    queue = collections.deque()
    result = []

    if root is not None:
        queue.append(root)

    while queue:
        level_size = len(queue)
        level_values = []

        for i in range(level_size):
            current = queue.popleft()
            level_values.append(current.val)

            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        result.append(level_values)
    return result

木の特性と応用

木の反転：中間順走査は2つのバックトラックノードが同じになるため注意。中間順走査は避けるべき。

対称木：後順走査を使用。左右の部分木が等しいかを判断。

最大深さ：深さを求めるには前順走査、高さを求めるには後順走査。最大深さは高さを求めることと同じ。

最小深さ：高さを求めるため、同じく後順走査を使用。

バックトラッキング編

基本概念

バックトラッキング三部作： 1. 再帰関数のパラメータと戻り値を決定 2. 再帰終了条件を決定 3. 単一レベルの再帰ロジックを決定

注意：上でどのように再帰するか、下で対応するバックトラックを行う。

典型問題

組み合わせ：枝刈り操作は通常forループの範囲で行う。

組み合わせ総和：枝刈り操作は以前のforループの変更とは異なり、条件を追加する必要がある。

電話番号の文字組み合わせ：まずmapでマッピング。文字列はappendできないため、+=で連結。

部分集合：組み合わせと比較し、部分集合は各レベルの再帰結果を結果セットに追加する点が異なる。

貪欲法編

基礎問題

クッキーの配布：局所最適条件に注意。対応するループの走査を変更。

揺動数列：場合分けして議論。

最大部分配列：最小値の初期化は result = float("-inf")。

応用問題

株式売買：最大利益 = 連続する2日間の正の差値の合計。

ジャンプゲーム：終点に到達できるか = 最大カバレッジ範囲が終点をカバーできるか。

ガソリン補給：総走行距離が総ガソリン量以上なら一周可能。

動的計画法編

基礎概念

動的計画法五部作： 1. DP配列と添え字の意味を決定 2. 漸化式を決定 3. DP配列の初期化方法を決定 4. 走査順序を決定 5. DP配列を例示して導出

典型問題

フィボナッチ数列：最も基本的なDP問題。

階段の上り方：フィボナッチ数列と本質的に同じ問題。

0-1ナップサック問題：

"""
二次元ナップサック問題の漸化式
"""
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

"""
一次元ナップサック問題の漸化式
"""
dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
# 走査順序：逆順

完全ナップサック問題：0-1ナップサックとの違いは、バックパックの走査順序を正順に変更する点のみ。

単調スタック編

基本概念

単調スタック問題のコードテンプレート：

"""
単調スタックのテンプレート（単調増加）
"""
stack = []
result = [0] * len(nums)

for i in range(len(nums)):
    # 現在の要素がスタックトップより大きい場合
    while stack and nums[i] > nums[stack[-1]]:
        # スタックから要素をポップし、結果を記録
        index = stack.pop()
        result[index] = i - index
    # 現在のインデックスをスタックにプッシュ
    stack.append(i)

典型問題

毎日の温度：純粋な単調スタック問題。

次のより大きい要素：インデックスの検索が必要。

雨水を受け取る：左右の柱の高さと幅を見つけることが鍵。

グラフ理論編

基礎概念

深さ優先探索（DFS）三部作： 1. 再帰関数とパラメータを決定 2. 終了条件を決定 3. 現在のノードから出発する経路を処理（forループで隣接ノードを走査）

幅優先探索（BFS）三部作： 1. 始点をキューに追加 2. キューが空でない間、キューの先頭要素を取り出す 3. 先頭要素を展開（未訪問の隣接ノードをキューに追加）

典型問題

島の数：DFSとBFSの両方で解決可能。

最小全域木：

• Primアルゴリズム：頂点を維持。最小全域木に最も近い頂点を選択し、追加。
• Kruskalアルゴリズム：辺を維持。辺の重みでソートし、Union-Findでサイクルを検出しながら辺を追加。

最短経路：

• Dijkstraアルゴリズム：非負の重みを持つグラフの単一始点最短経路問題。
• Bellman-Fordアルゴリズム：負の重みを持つグラフにも対応可能。
• Floyd-Warshallアルゴリズム：全頂点間の最短経路問題。