109: 文字列の回転

問題リンク: 文字列回転問題

解法:

class StringRotator {
public:
    bool checkRotation(string str1, string str2) {
        int len = str1.length();
        if (len != str2.length()) return false;
        for (int i = 0; i < len; i++) {
            if (str1[i] == str2[0]) {
                int idx1 = i, idx2 = 0;
                bool match = true;
                for (int j = 0; j < len; j++) {
                    if (str1[idx1] != str2[idx2]) {
                        match = false;
                        break;
                    }
                    idx1 = (idx1 + 1) % len;
                    idx2++;
                }
                if (match) return true;
            }
        }
        return false;
    }
};

110: k個のソート済みリストのマージ

問題リンク: kリストマージ問題

解法1: 優先度付きキューによるマージ

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int x) : value(x), next(nullptr) {}
};

class ListMerger {
public:
    class NodeComparator {
    public:
        bool operator()(ListNode* a, ListNode* b) {
            return a->value > b->value;
        }
    };

    ListNode* mergeLists(vector& lists) {
        ListNode dummy(0);
        priority_queue, NodeComparator> queue;
        
        for (auto list : lists) {
            while (list) {
                queue.push(list);
                list = list->next;
            }
        }

        ListNode* current = &dummy;
        while (!queue.empty()) {
            current->next = queue.top();
            queue.pop();
            current = current->next;
        }
        current->next = nullptr;
        return dummy.next;
    }
};

解法3: リストのヘッドを優先度付きキューに追加

ListNode* mergeKLists(vector& lists) {
    ListNode dummy(0);
    priority_queue, NodeComparator> queue;
    
    for (auto list : lists) {
        if (list) queue.push(list);
    }

    ListNode* current = &dummy;
    while (!queue.empty()) {
        ListNode* node = queue.top();
        queue.pop();
        current->next = node;
        current = current->next;
        if (node->next) queue.push(node->next);
    }
    current->next = nullptr;
    return dummy.next;
}

111: スキー

問題リンク: スキー問題

解法: 深さ優先探索＋メモ化

#include <iostream>
#include <vector>
using namespace std;

const int MAX_SIZE = 110;
int grid[MAX_SIZE][MAX_SIZE];
int memo[MAX_SIZE][MAX_SIZE];
int rows, cols;

int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

int dfs(int x, int y) {
    if (memo[x][y] != 0) return memo[x][y];
    
    int maxSteps = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && 
            grid[nx][ny] > grid[x][y]) {
            maxSteps = max(maxSteps, 1 + dfs(nx, ny));
        }
    }
    return memo[x][y] = maxSteps;
}

int main() {
    cin >> rows >> cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> grid[i][j];
        }
    }

    int result = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            result = max(result, dfs(i, j));
        }
    }
    cout << result << endl;
    return 0;
}