11/15

問題1: 二進数行列の最小反転回数 (3239)

解法はシミュレーションに基づく。

各行の反転回数を計算し、列方向の反転回数も同様に求めます。

int calcRowDiff(const vector& matrix) {
    int count = 0;
    for (const auto& row : matrix) {
        for (size_t i = 0; i < row.size() / 2; ++i) {
            if (row[i] != row[row.size()-1-i]) ++count;
        }
    }
    return count;
}

問題2: 配列要素を含むノードの削除 (3217)

ハッシュテーブルを使用して検索時間をO(1)に最適化します。

ListNode* removeNodes(ListNode* head, const vector<int>& values) {
    unordered_set<int> valueSet(values.begin(), values.end());
    ListNode dummy(0);
    dummy.next = head;
    
    for (ListNode* current = &dummy; current->next;) {
        if (valueSet.count(current->next->val)) {
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    return dummy.next;
}

問題3: 重複要素の削除 (82,83)

ダミーヘッドノードを使用して先頭要素の削除を簡略化します。

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return nullptr;
    
    ListNode* prev = head;
    ListNode* current = head->next;
    
    while (current) {
        if (prev->val == current->val) {
            prev->next = current->next;
        } else {
            prev = current;
        }
        current = current->next;
    }
    return head;
}

問題4: リンクリストのマージ (1669)

2つのリストを指定位置で結合するアルゴリズム。

ListNode* mergeLists(ListNode* list1, int start, int end, ListNode* list2) {
    ListNode* first = list1;
    for (int i = 0; i < start-1; ++i) first = first->next;
    
    ListNode* last = first;
    for (int i = 0; i < end-start+1; ++i) last = last->next;
    
    ListNode* tail = list2;
    while (tail->next) tail = tail->next;
    
    first->next = list2;
    tail->next = last;
    return list1;
}

問題5: グローバル最大値の維持 (2487)

再帰と反転操作の2つのアプローチ。

// 再帰解法
ListNode* removeLesserNodes(ListNode* head) {
    if (!head) return nullptr;
    head->next = removeLesserNodes(head->next);
    return (head->next && head->val < head->next->val) ? head->next : head;
}

// 反転解法
ListNode* removeLesserNodesIter(ListNode* head) {
    auto reverse = [](ListNode* node) {
        ListNode* prev = nullptr;
        while (node) {
            auto next = node->next;
            node->next = prev;
            prev = node;
            node = next;
        }
        return prev;
    };
    
    head = reverse(head);
    for (auto current = head; current->next;) {
        if (current->val > current->next->val) {
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    return reverse(head);
}