配列の二分探索

昇順に整列された重複のない配列から要素を検索する際、二分探索は効率的な手法です。左閉右閉区間と左閉右開区間の2つのアプローチを解説します。

左閉右閉区間アプローチ

class Solution {
public:
    int binarySearch(const vector<int>& arr, int target) {
        int low = 0;
        int high = arr.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};

左閉右開区間アプローチ

class Solution {
public:
    int binarySearch(const vector<int>& arr, int target) {
        int start = 0;
        int end = arr.size();
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
};

螺旋行列の生成

指定されたサイズの正方形行列を時計回りに1からn²の値で埋める際、境界条件を厳密に管理する必要があります。

class Solution {
public:
    vector<vector<int>> createSpiralMatrix(int size) {
        vector<vector<int>> matrix(size, vector<int>(size, 0));
        int top = 0, left = 0;
        int cycles = size / 2;
        int value = 1;
        int border = 1;
        int mid = size / 2;
        
        while (cycles-- > 0) {
            int x = top, y = left;
            for (y = left; y < size - border; y++) {
                matrix[top][y] = value++;
            }
            for (x = top; x < size - border; x++) {
                matrix[x][y] = value++;
            }
            for (; y > left; y--) {
                matrix[x][y] = value++;
            }
            for (; x > top; x--) {
                matrix[x][y] = value++;
            }
            border++;
            top++;
            left++;
        }
        
        if (size % 2 == 1) {
            matrix[mid][mid] = size * size;
        }
        return matrix;
    }
};

連結リストの要素削除

連結リストから特定の値を持つ要素を削除する際、仮想ヘッドノードを使用する方法とそうでない方法があります。

仮想ヘッドノードを使用する方法

class Solution {
public:
    ListNode* removeValue(ListNode* listHead, int target) {
        ListNode* dummy = new ListNode(0);
        dummy->next = listHead;
        ListNode* curr = dummy;
        while (curr->next != nullptr) {
            if (curr->next->val == target) {
                ListNode* delNode = curr->next;
                curr->next = curr->next->next;
                delete delNode;
            } else {
                curr = curr->next;
            }
        }
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

仮想ヘッドノードを使用しない方法

class Solution {
public:
    ListNode* removeValue(ListNode* head, int target) {
        while (head != nullptr && head->val == target) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
        ListNode* curr = head;
        while (curr != nullptr && curr->next != nullptr) {
            if (curr->next->val == target) {
                ListNode* delNode = curr->next;
                curr->next = curr->next->next;
                delete delNode;
            } else {
                curr = curr->next;
            }
        }
        return head;
    }
};