データ構造とアルゴリズム
しょうゆleetcodeについて
面接対策において、LeetCodeの「Top Interview Questions」セクションは非常に役立ちます。
ここでは、実際に多くの企業で出題される可能性が高い問題がリストアップされており、それらを集中的に練習することで効率的に準備を進めることができます。
例えば、AmazonやGoogle、Facebookといった大手テック企業の面接でよく出題される問題に特化した問題集があり、これらを解くことで各企業の面接傾向に沿った対策が可能です。
また、LeetCodeの「Explore」セクションには、アルゴリズムやデータ構造に関するシリーズが用意されており、これを活用することで系統的に学習を進めることができます。
有料プランでは模擬面接機能が強化されており、リアルタイムでの模擬面接を通じて実践的なスキルを磨くことができます。(時間制限あり)
しょうゆorderの意味：
この用語は、数学の分野で使われる「growth order（成長の階級）」や「order of magnitude（桁の規模）」という概念に由来しています。
数学や科学では、「order」は数量の規模や関数の成長率を指すことがあります。
例: "of the order of magnitude 10"（10の規模で）という表現があります。
英語での使われ方の例：
The overall run time complexity should be O(log (m+n)).
・時間計算量（Big-O記法）では、次のようなルールがあります。
定数係数は無視する
O(4n), O(100n), O(0.5n) などはすべて O(n) に簡略化される。
理由: 計算量を評価する際、n が十分大きくなると、定数の影響は無視できるから。
最高次の項のみ残す
O(n + log n) → O(n)
O(n² + n + log n) → O(n²)
しょうゆO(1)（定数時間）
意味: 入力のサイズ（n）が増えても処理時間が変わらない。
O(n)（線形時間）
意味: 入力サイズ（n）に比例して処理時間が増える。
O(n²)（二次時間）
意味: 入力サイズ（n）が増えると、処理時間がその2乗に比例して増える。
O(log n)（対数時間）
意味: 入力サイズが大きくなるにつれて処理時間の増加が緩やか。
よくある場面:
二分探索（Binary Search）: ソート済みデータを半分に分割して探索。
平衡二分木（Balanced Binary Tree）の探索: データ構造の深さが log n に比例。
O(n log n)（線形対数時間）
意味: 入力を1回線形（n）で処理しながら、各ステップで対数時間（log n）の追加操作が必要。
よくある場面:
効率的なソートアルゴリズム:
マージソート（Merge Sort）
クイックソート（Quick Sort、最良・平均の場合）
ヒープ構造の構築:
ヒープソート（Heap Sort）。
O(2ⁿ)（指数時間）
意味: 入力サイズが1増えるたびに処理時間が倍増する（非常に非効率）。
よくある場面:
再帰的な全探索アルゴリズム:
フィボナッチ数列（再帰的な実装）。
全ての部分集合を列挙する。
巡回セールスマン問題（TSP） のブルートフォース解法。
しょうゆ問題70 フィボナッチ数列を用いる
「n 段目までの登り方の総数」は「n−1 段目までの登り方の総数」と「n−2 段目までの登り方の総数」の合計になります。
f(n)=f(n−1)+f(n−2)
それをf(3)からnまで繰り返し計算していく。
しょうゆスタック（Stack） LIFO（Last In, First Out）：後から入れたものが先に出る
キュー（Queue） FIFO（First In, First Out）：先に入れたものが先に出る
しょうゆこの問題は「会議室の予約管理」や「区間スケジューリング問題」と同様で、開始時間と終了時間のイベントをソートし、同時にアクティブな予約の数を管理することで解決できます。
考え方
[[0,15],[0,5],[0,10]] のような入力が与えられた場合、同じ時間に予約が重なったテーブルの最大数を求める。
予約の開始 (start) と終了 (end) を時間イベントとしてリスト化し、同じ時間に何件の予約が重なっているか をカウントする。
各予約で開始時間になれば+1。終了時間になれば-1。
ただし、開始時間と終了時間が重なれば、終了時間の方を先に処理。
それを一つのリストに格納し、時間順にソートし、結果を求める。
しょうゆ用語集
スタック、キュー、リンクリスト、二分木
線形探索や二分探索
しょうゆアルゴリズム解決法の種類:
brute force algorithm (総当たり法） は、可能なすべての選択肢を試して、解を見つけるアルゴリズム です。
そのコードは 線形探索 (O(n)) ではなく、二重ループによる O(n²) の時間計算量 を持つ 二重ループの全探索 (brute-force) です。
Greedy(貪欲法)：
その場での最善の手を選ぶことを繰り返す
DP(Dynamic Programming)(動的計画法):
重複する計算を省略することで効率的に問題を解くアルゴリズム手法 です。
しょうゆ配列のin-placeについて
「2ポインター法」は、2つの異なるインデックス（ポインタ）を使って配列を操作するアルゴリズム です。
特に in-place（その場で処理） する場面でよく使われます。
in-placeとは
その場の内で、そのオブジェクト内で完結する処理で。という意味。
しょうゆスライディングウィンドウ法
ウィンドウ＝枠
配列があり、ウィンドウをスライディングさせながら、解を見つける手法。
しょうゆSort()メソッドを用いた際は、基本的にnlognに計算量がかかるためO(n)では終わらない。
しょうゆO(n) 入力が一つだけの場合に使われる表現。
O(|T|) 入力Tの長さに比例して増える。
絶対値T
しょうゆListのメソッド時間計算量。
List<int> sample = [];
sample[2]
一つの要素にアクセスするだけなのでO(1)
remove()
削除した後に、要素をずらす必要があるので、0(n)
removeLast()
最後の要素を削除するだけなので0(1)