4 Leetcode問題の解説

LC-7：整数反転#

思路
- 負数は追加の判断が不要で、ロジックは一貫している
- 主に判断するのは (* 10 操作) のオーバーフローの状況で、2 つの方法がある
  - ⭐どちらも巧妙
  - 方法 1：long long を使って反転した数字を保存し、最後に int に変換してオーバーフローを判断
  - 方法 2：反転する際に、毎回 1 桁加えるときにオーバーフローを判断
    - INT_MAX と比較：【すでに INT_MAX/10 を超えている】または【INT_MAX/10 と等しく、加える数が > 7】
    - INT_MIN と比較：【すでに INT_MIN/10 未満】または【INT_MIN/10 と等しく、加える数が <-8】
コード
- 方法 1：long long を使用

class Solution {
public:
    int reverse(int x) {
        // 個人的な解答
        // 負号を考慮する必要はない
        long long t = 0;
        while (x) {
            t = t * 10 + x % 10;
            x /= 10;
        }
        // 結果がintの範囲内にあるか判断
        return int(t) == t ? t : 0;
    }
};

- 方法 2：桁を加えるときに判断

class Solution {
public:
    int reverse(int x) {
        // 公式解答
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;  // 毎回加える1の位の数、事前に計算してオーバーフローを判断
            x /= 10;
            // 最大値INT_MAXに対応
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            // 最小値INT_MINに対応
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

- - 加える 1 の位の数 pop を事前に計算

LC-9：回文数#

思路
- 回文数は必ずオーバーフローしない、なぜならそれは自分自身と等しいから
- ⭐半分の数字を反転する
  - オーバーフローを考慮する必要はない
  - しかし奇数桁の状況を考慮することを忘れないでください！
- 初期段階で【負数】および【0 で終わる正の数】を排除できる
- PS：文字列に変換する方法
  - C++ の string クラスを使用し、to_string () を組み合わせることができる
  - 二重ポインタで前後を比較すればよい

string  str = to_string(x);

コード

class Solution {
public:
    bool isPalindrome(int x) {
        // 【負数】および【0で終わる正の数】は直接除外
        if (x < 0 || x % 10 == 0 && x != 0) return false;
        int rev = 0;
        // 半分だけ反転し、オーバーフローの問題を考慮する必要はない
        while (rev < x) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        // 奇数桁の状況を考慮することを忘れないでください
        return rev == x || rev / 10 == x;
    }
};

LC-13：ローマ数字を整数に変換#

思路
- 加法と減法が関与しているので、switch...case... を使用すればよい
- 文字列を順に走査し、特殊な文字に対してはさらに判断を加えればよい
コード

class Solution {
public:
    int romanToInt(string s) {
        int ans = 0;
        // 左から右へ順に走査
        for (int i = 0; i < s.size(); i++) {
            // 判断する状況が多いため、switch...case...を使用
            switch (s[i]) {
                // まずは素朴な状況を考慮
                case 'V' :
                    ans += 5;
                    break;
                case 'L' :
                    ans += 50;
                    break;
                case 'D' :
                    ans += 500;
                    break;
                case 'M' :
                    ans += 1000;
                    break;
                case 'I' :
                    // i + 1がオーバーフローするか？しない、文字列の末尾に'\0'がある
                    if (s[i + 1] == 'V') {
                        ans += 4;
                        i++;  // 手動で1回多く加える
                    } else if (s[i + 1] == 'X') {
                        ans += 9;
                        i++;
                    } else {
                        ans += 1;
                    }
                    break;  // breakを忘れないでください
                case 'X' :
                    if (s[i + 1] == 'L') {
                        ans += 40;
                        i++;
                    } else if (s[i + 1] == 'C') {
                        ans += 90;
                        i++;
                    } else {
                        ans += 10;
                    }
                    break;
                case 'C' :
                    if (s[i + 1] == 'D') {
                        ans += 400;
                        i++;
                    } else if (s[i + 1] == 'M') {
                        ans += 900;
                        i++;
                    } else {
                        ans += 100;
                    }
                    break;
            }
        }
        return ans;
    }
};

- i + 1 がオーバーフローするか？しない、文字列の末尾に '\0' がある

LC-14：最長共通接頭辞#

思路
- 現在の共通接頭辞を次の文字列と比較し、共通接頭辞を更新
  - 初期の共通接頭辞は最初の文字列
  - 途中で空になった場合は、すぐに空を返す
  - すべての文字列を走査するまで続ける
  - 一度の比較後の共通接頭辞を保存する変数が必要
コード

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";  // 慣例として、まず空を判断
        string ans = strs[0];  // 答えを最初の文字列で初期化
        // 2番目の文字列から走査を開始
        for (int i = 1; i < strs.size(); i++) {
            string t = ans;  // 現在の共通接頭辞tを保存し、ansをそのまま走査に使用してはいけない！
            ans = "";  // 比較後の共通接頭辞を記録
            // 長さが【走査する文字列の長さ】と【現在の共通接頭辞】の長さより小さい
            for (int j = 0; j < strs[i].size() && j < t.size(); j++) {
                if (strs[i][j] == t[j]) {
                    ans += t[j];
                } else {
                    break;
                }
            }
            if (ans == "") {
                break;
            }
        }
        return ans;
    }
};

- まず空の配列を判断
- 前回の共通接頭辞を保存する新しい変数が必要

LC-26：ソートされた配列から重複を削除#

思路
- ソート済みで、原地で修正
- 二重ポインタ
  - 値を保存するポインタ + 配列を走査するポインタ
  - 2 つのポインタの値
    - 異なる場合、前のポインタに値を保存し、2 つのポインタを一緒に進める
    - 同じ場合、後のポインタだけを進める
コード

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        // 保存ポインタp、速いポインタi
        int p = 1;  // 0番目の数は必ず存在
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1]) {
                nums[p] = nums[i];
                p++;
                // nums[p++] = nums[i];
            }
        }
        return p;
    }
};

- 二重ポインタ～

LC-27：要素を削除#

思路
- LC-26 問題に似ており、さらに簡単
- 同様に 2 つのポインタ
  - 等しい場合は速いポインタを進める
  - 等しくない場合は保存ポインタに値を保存し、一緒に進める
コード

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0) return 0;
        int p = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[p++] = nums[i];  // 等しくないときは値を保存
            }
        }
        return p;
    }
};

LC-35：挿入位置を検索#

思路
- ソート済み
- 目標値のインデックスを見つけるか、順序に従った挿入位置を見つける
- 0000011111111 特殊な二分探索！
コード

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 特殊な状況：目標値が最大数より大きい
        if (nums[nums.size() - 1] < target) {
            return nums.size();
        }
        // 特殊な二分探索：000001111111
        int l = 0, r = nums.size() - 1;
        while (l != r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
};

- 特殊な状況を考慮することを忘れないでください：0000000000、事前に判断

LC-38：外観数列#

思路
- 前の項に基づいて次の項を求める
  - カウンターをカウントし、初期値は 1、リセットすることを忘れないでください
  - 連続している文字の数を判断し、前の文字と現在の文字が等しいかどうかを判断
コード

class Solution {
public:
    string ans[5] = {"", "1"};  // 第0項は無視、第1項は"1"
    // ↑2つの文字列を交互に保存するだけ
    void func(int s1, int s2) {
        ans[s2] = "";
        int cnt = 1;  // カウント：現在の文字が連続している回数
        // cntは初期値1、2番目の文字から開始
        for (int i = 1; i < ans[s1].size(); i++) {
            if (ans[s1][i - 1] == ans[s1][i]) {
                cnt++;
            } else {
                ans[s2] += cnt + '0';  // 数字を文字に変換！
                ans[s2] += ans[s1][i - 1];  // cnt個の文字
                cnt = 1;
            }
        }
        // 注意：最後のラウンドはまだ出力されていない
        ans[s2] += cnt + '0';
        ans[s2] += ans[s1][ans[s1].size() - 1];  // 最後の文字
    }
    void swap(int *a, int *b) {
        // 交換の書き方をマスターする
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    // 問題が与えられた関数
    string countAndSay(int n) {
        int a = 1, b = 0;  // 文字列番号を交換するために使用
        for (int i = 2; i <= n; i++) {
            func(a, b);  // 前の文字列ans[a]に基づいて次のans[b]を求める
            swap(&a, &b);
        }
        return ans[a];
    }
};

- 2 つの文字列を交互に記録することができます
- 数字を文字に変換することを忘れないでください
- 最後のラウンドを個別に出力することに注意

LC-53：最大部分配列の和#

思路
- ans [x] = x で終わる最大連続和
- ans[x] = max(ans[x - 1] + num[x], num[x])
- 配列は必要なく、2 つの変数だけで済む
  - 前回の最大 ans
  - 現在の最大 now
コード

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, now = 0;  // nums[0]をINT_MINの代わりに直接使用することもできる
        for (int i = 0; i < nums.size(); i++) {
            now = max(now + nums[i], nums[i]);  // 重要、現在到達可能な最大値
            ans = max(ans, now); // 現在の最大値を更新
        }
        return ans;
    }
};

- ans と now を適切に処理してください！

LC-66：1 を加える#

思路
- 大きな数の加算よりも簡単で、反転する必要はない
  - 後ろから前に進んで繰り上がりの状況を判断するだけ
  - 最高位の繰り上がりの状況を処理することに注意し、vector の insert メソッドを使用
コード

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        digits[digits.size() - 1]++;
        // 加算後の各桁の繰り上がりを処理するだけ
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] == 10) {
                digits[i] = 0;
                // 最高位の繰り上がりを特別に処理するelse
                if (i != 0) {
                    digits[i - 1]++;
                } else {
                    digits.insert(digits.begin(), 1);  // O(N)
                    // insert、digit.begin()
                }
            } else {
                break;
            }
        }
        return digits;
    }
};

- insert
  - O(N)
  - 参考std::vector::insert
- digit.begin()
  - 現在の vector コンテナの最初の要素のイテレータを返す
  - 参考vector コンテナ begin () と end () 関数、front () と back () の使い方-CSDN

LC-69：x の平方根#

思路
- 整数の二分探索
  - 例えば：8 の平方根を求める
  - 0 - 8 を走査：0123456789
  - 目標は 2 を得ること
  - したがって、1110000000 の状況に対応
コード

class Solution {
public:
    int mySqrt(int x) {
        // 111110000
        long long l = 0, r = x;
        while (l != r) {
            // long longを定義
            long long mid = (l + r + 1) / 2;
            if (mid * mid <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

- mid * mid がオーバーフローする可能性があるため、long long 型を統一して定義

LC-70：階段を登る#

思路
- すなわちフィボナッチ数列
- 2 つの方法：再帰 + メモ化；逐次
- 拡張：大きな整数型があるかもしれない；一度に多くの段を登ることができる
コード

class Solution {
public:
    int ans[50] = {0, 1, 2};
    int climbStairs(int n) {
        // 関数の戻り値はintであり、n=46のとき、結果はオーバーフローする
        // 方法1：再帰 + メモ化
        if (ans[n]) {
            return ans[n];
        }
        // ans[n]を保存することを忘れないでください
        return ans[n] = climbStairs(n - 1) + climbStairs(n - 2);
        // 方法2：逐次
        for (int i = 3; i <= n; i++) {
            ans[i] = ans[i - 1] + ans[i - 2];
        }
        return ans[n];
    }
};

- 問題の意図により、関数の戻り値は int 型であるため、n は最大で 45 まで、n = 46 のときはオーバーフローする

LC-88：2 つのソートされた配列をマージ#

思路
- nums1 には十分なスペースがあり、余分なスペースは nums2 の長さに等しい
- 後ろから前に走査して 2 つの配列を保存し、大きいものを nums1 に後ろから保存
  - ❌前から後ろに走査すると上書きされるため、処理が必要
コード

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // nums1のスペースが大きい
        for (int i = m + n - 1; i >= 0; i--) {
            // 後ろから前に保存
            if (m == 0 || n!= 0 && nums2[n - 1] > nums1[m - 1]) {
                // nums2の要素を保存
                nums1[i] = nums2[n - 1];
                n--;
            } else {
                // nums1の要素を保存
                nums1[i] = nums1[m - 1];
                m--;
            }
        }
    }
};

- 判断条件を厳密にすることを忘れないでください！
- nums2 の要素を後ろに保存する
  - nums1 がすでに走査されている、すなわち m = 0
  - または
  - nums2 の対応する値が nums1 より大きく、【nums2 がまだ走査されていない！】👈必ず判断すること
    - すなわち n!= 0 && nums2 [n - 1] > nums1 [m - 1]
- そうでなければ、nums1 の要素を後ろに保存

LC-118：パスカルの三角形#

思路
- 各位の値は上左 + 上の値に等しい
- 提供されたサンプルでは vector を使用して実装されており、配列の補 0 の方法を使用できない！
  - その後、vector の具体的な詳細に注意
コード

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //vector は配列のように0を残すことができないため、各行の左右の境界を事前に処理する必要がある
        vector<vector<int> > ans;  // 古い標準では<int>の後に空白がある
        // 特判
        if (numRows == 0) {
            return ans;
        }
        // 最初の行
        ans.push_back({1});
        // 2行目はi = 1に対応
        for (int i = 1; i < numRows; i++) {
            vector<int> v;  // この行を保存するための一時的なvectorを定義
            v.push_back(1);  // 左の境界
            // 第i行は両端の1を除いてi - 1個の要素がある
            for (int j = 1; j < i; j++) {
                v.push_back(ans[i - 1][j - 1] +ans[i - 1][j]);
            }
            v.push_back(1);  // 右の境界
            ans.push_back(v);
        }
        return ans;
    }
};

- vector の方法：push_back

LC-121：株式の売買の最適なタイミング Ⅰ#

思路
1 回だけ売買する
- 走査
  - 現在の最小値を更新：最初の数で初期化
  - 答えを更新：【一時的な答え】と【現在の値 - 現在の最小値】を比較
    - 答えは初期値 0
  - 答えを出力
コード

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            // 特判が必要、そうでないと下の初期化時にprices[0]が存在しないためエラーが発生する
            return 0;
        }
        int ans = 0, mmin = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            ans = max(ans, prices[i] - mmin);
            mmin = min(mmin, prices[i]);
        }
        return ans;
    }
};

- 答え ans の初期値は 0、現在の最小値 mmin の初期値は最初の数 prices [0]
  - 2 つの m を使用して C++ の min () 関数と名前が重複しないようにする
  - 特判が必要、prices に値がない可能性がある
  - vector.size()

LC-122：株式の売買の最適なタイミング Ⅱ#

思路
- 任意の回数売買できる
- 2 日ごとに考慮し、隣接する 2 日間だけを見て利益を得られるかどうかを判断
コード

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 数個の2日間に分ける
        // 特判を加えても加えなくてもよい
        int ans = 0;
        for (int i = 1; i < prices.size(); i++) {
            // 現在のこの日が前の日より株価が高い限り
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
};

- 特判は加えても加えなくてもよい、prices.size () がすでにループを制限している

LC-136：1 回だけ現れる数字#

思路
- 精髄：ビットごとの排他的論理和
  - 0 ^ x = x
  - x ^ x = 0
コード

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i]; 
        }
        return ans;
    }
};

追加知識点#

プレフィックス和#

区間和を迅速に求める
- プレフィックス和配列 sum
- 区間 [x, y] の和：sum [y] - sum [x - 1]
- 配列は 0 の位置を多く開けて、①に対応する sum [1 - 1] に値がないのを避ける
追加の配列を維持し、複数回の問い合わせによる時間の浪費を避ける

考察点#

ヒント#

コースの速記#

自作：67、119 (参考 118)、125