コレクション操作ユーティリティ

ArraysとCollectionsクラスの主要メソッド：

• asList：リスト変換には戻り値が必要
• copyOfRange：配列の部分コピー

型変換テクニック

// List<Integer> → int[]
public int[] convert(List<Integer> list) {
    return list.stream()
               .mapToInt(Integer::intValue)
               .toArray();
}

Stream API処理フロー:

1. stream()：ListからStream生成
2. mapToInt()：StreamをIntStream変換
3. toArray()：IntStreamを基本型配列に変換

スタックとキュー

相互実装原理

キュー：先頭削除／末尾追加。基本操作：

• peek：先頭参照
• poll：要素削除
• add：要素追加

// インターフェース活用例
Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new LinkedList<>();

インターフェース設計

実装クラス変更時の柔軟性：

Map<String, Integer> dataMap = new HashMap<>();
dataMap.put("apple", 3);

for (Map.Entry<String, Integer> entry : dataMap.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

LinkedListの多機能実装：

• Listインターフェース：順序管理
• Queueインターフェース：FIFO操作
• Dequeインターフェース：両端操作

動的計画法パターン

典型問題分類

実装ポイント

// 完全ナップサック変形例
public int coinCombination(int[] coins, int amount) {
    int[] dpArray = new int[amount + 1];
    Arrays.fill(dpArray, Integer.MAX_VALUE - 1); // オーバーフロー対策
    dpArray[0] = 0;
    
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dpArray[j] = Math.min(dpArray[j], dpArray[j - coin] + 1);
        }
    }
    return dpArray[amount] > amount ? -1 : dpArray[amount];
}

二分木操作

走査テクニック

• DFS：再帰／スタック反復
• BFS：階層順走査

平衡判定実装

public int checkBalance(TreeNode node) {
    if (node == null) return 0;
    
    int leftDepth = checkBalance(node.left);
    int rightDepth = checkBalance(node.right);
    
    if (leftDepth == -1 || rightDepth == -1 || 
        Math.abs(leftDepth - rightDepth) > 1) {
        return -1;
    }
    return Math.max(leftDepth, rightDepth) + 1;
}

検索木操作

// 値削除アルゴリズム
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    }
    return root;
}

文字列処理

KMPアルゴリズム

部分文字列検索の効率化：

public int kmpSearch(String text, String pattern) {
    int[] lps = computeLPS(pattern);
    int i = 0, j = 0;
    
    while (i < text.length()) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        }
        if (j == pattern.length()) return i - j;
        else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    return -1;
}

連結リスト

反転処理

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode current = head;
    int count = 0;
    
    while (count < k) {
        if (current == null) return head;
        current = current.next;
        count++;
    }
    
    ListNode newHead = reverseSegment(head, k);
    head.next = reverseKGroup(current, k);
    return newHead;
}