問題1: フラッドフィルを用いた領域の囲い込み

二次元グリッドが与えられ、各セルは'X'または'O'で構成されます。境界に接続されていない'O'の領域を特定し、それらを'X'に変換する必要があります。境界に隣接する'O'は変換せずに保持します。

アプローチ: 深さ優先探索(DFS)を活用し、境界上の'O'から接続された領域を一時マークで識別します。その後、マークされていない内部の'O'を'X'に変換し、一時マークを元の'O'に戻します。

class Solution {
public:
    void solve(vector<vector<char>>& grid) {
        if(grid.empty()) return;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<pair<int, int>> directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        
        for(int r = 0; r < rows; r++) {
            markRegion(grid, r, 0, directions);
            markRegion(grid, r, cols-1, directions);
        }
        for(int c = 0; c < cols; c++) {
            markRegion(grid, 0, c, directions);
            markRegion(grid, rows-1, c, directions);
        }
        
        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                if(grid[r][c] == 'O') grid[r][c] = 'X';
                else if(grid[r][c] == 'T') grid[r][c] = 'O';
            }
        }
    }
    
    void markRegion(vector<vector<char>>& grid, int r, int c, vector<pair<int, int>>& dirs) {
        if(r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] != 'O') 
            return;
        grid[r][c] = 'T';
        for(auto& d : dirs) {
            int nr = r + d.first;
            int nc = c + d.second;
            markRegion(grid, nr, nc, dirs);
        }
    }
};

問題2: 最長連続数値シーケンスの探索

整数配列が与えられた時、隣接する数値が連続する最長シーケンスの長さを求めます。計算量はO(n)である必要があります。

アプローチ: ハッシュセットを使用して効率的な検索を実現します。各数値について、前後の連続する数値が存在するかどうかをチェックし、最長シーケンスを追跡します。

class SequenceFinder {
public:
    int findLongestSequence(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxSequence = 1;
        
        for(int num : nums) {
            if(numSet.find(num) == numSet.end()) continue;
            
            int left = num;
            while(numSet.find(left-1) != numSet.end()) {
                numSet.erase(left-1);
                left--;
            }
            
            int right = num;
            while(numSet.find(right+1) != numSet.end()) {
                numSet.erase(right+1);
                right++;
            }
            
            maxSequence = max(maxSequence, right - left + 1);
        }
        return maxSequence;
    }
};