異端開発室

LeetCodeの代表的なアルゴリズム問題とそのC++による実装をまとめました。文字列、配列、連結リスト、動的計画法などのトピックを取り上げ、アルゴリズム面接準備や日頃の練習に役立ちます。 目次 文字列処理 配列問題 連結リスト操作 動的計画法 木の走査 1. 文字列処理 1.1 二進数の部分文字列を数える（Count Binary Substrings） 問題説明：与えられた文字列において ...

回文部分文字列のカウント この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s ...

2815. 配列内の最大ペア和 二重ループで全探索する。 class Solution { public: int maxSum(vector<int>& nums) { auto getMaxDigit = [](int val) { int maxD = 0; while (val) { if (val % 10 > maxD) maxD = val % 10; val /= 10; } return maxD; } ...

問題の概要 二分探索木（BST）が有効であるかどうかを判定するには、各ノードが以下の条件を満たしているかを確認する必要があります。 ノードの左部分木に含まれるすべての値は、そのノードの値より厳密に小さい。 ノードの右部分木に含まれるすべての値は、そのノードの値より厳密に大きい。 左右の部分木もそれぞれ二分探索木でなければならない。 これを効率的にチェ ...

2つの数の合計が特定の値になる場合 配列がソートされている場合、双指針法を用いて効率的に解決できます。左端と右端から開始し、合計値を比較してポインタを移動します。 public class SumSolution { public static int[] findTwoSum(int[] arr, int target) { int start = 0; int end = arr.length - 1; while (start < end) { ...

二分木の基礎理論 二分木は各ノードの子ノード数が最大2の木構造です。主要な形態として完全二分木と完全二分木が存在します。データ格納方式には配列を用いた順序格納とポインタを用いたリンク方式があります。走査方法は以下の通りです： 先行走査（深さ優先） 中間走査（深さ優先） 後行走査（深さ優先） 階層走査（幅優先） class BinaryNode: def __init__(self ...

問題概要 LeetCodeの問題593では、2次元平面上の4点の座標が与えられ、それらが正方形を形成するかどうかを判定する必要がある。入力される点の順序は任意である。 解法の考え方 ベクトル演算を利用することで効率的に解決できる。基準点を1つ選び、他の3点へのベクトルを計算する。これらのベクトルを長さの昇順に並べ替え、\(\boldsymbol{v}_0, \boldsymbol{v}_1, \bolds ...

アルゴリズムの効率性を最大化するためのビット演算の体系的な解説。状態圧縮やマスク操作、空間複雑度O(1)の最適化手法を、大手企業の実際問題を通じて学習します。 一、ビット演算子の基本操作 演算名 記号 動作 応用例 論理積 &amp; 共に1のときのみ1 フラグの抽出 論理和 | いずれか1なら1 設定値の統合 排他的論理和 ^ 異なるビットが1 重複値の除去 ...

StringBuilder APIの基本操作 主要なStringBuilderメソッド append(String str)：文字列を末尾に追加します。 insert(int offset, String str)：指定位置に文字列を挿入します。 delete(int start, int end)：指定範囲の文字を削除します。 deleteCharAt(int index)：指定位置の文字を削除します。 reverse()：文字列を反転します。 toString()：StringBuilderをStringに ...

単調スタックの基本概念 単調スタック（Monotonic Stack）は、スタック内の要素が常に単調増加、または単調減少の順序を保つように維持するデータ構造です。この特性を利用することで、配列内の各要素に対して「左側または右側で最も近い、より大きい（または小さい）要素」を効率的に探索することができます。 典型的な応用としては、以下の 4 つのパターンがあります。 ...