異端開発室

動的プログラミング問題へのアプローチ 動的プログラミング問題を解決するための5つのステップ： DP配列（DPテーブル）とそのインデックスの意味を定義する 漸化式を決定する DP配列の初期化方法を決定する（配列オーバーフローに注意） 計算順序を決定する DP配列の具体例を導出する フィボナッチ数 フィボナッチ数列（通常 F(n) で表される）は、0 と 1 から始まり、そ ...

問題 2612. 最小反転操作回数 整数 n と、範囲 [0, n - 1] 内の整数 p が与えられます。これらは、長さが n でインデックスが 0 から始まる配列 arr を表します。この配列では、インデックス p の位置だけが 1 で、他のすべての要素は 0 です。 同時に、整数配列 banned も与えられます。この配列には、配列内のいくつかの位置が含まれています。banned の第 i 個 ...

本日の課題 LeetCode 203. リンクリスト要素の削除 LeetCode 707. リンクリストの設計 LeetCode 206. リンクリストの反転 基本概念の整理 ノードの追加処理では、新しいノード（current.next）を先に処理し、古いノード（previous.next）を後から処理します。 ノードの削除では、現在のノードを削除するには、その前のノードを知る必要があります。そのため、currentとp ...

スライディングウィンドウ入門 「連鎖・部分文字列・配列の問題は、まず双方向ポインタを考えよ。 双方向ポインタ三兄弟、それぞれに魅力あり。 速いポインタと遅いポインタは魔法使い、連結リスト操作に敵なし。 マージソートで中点を探し、連結リストの循環を判定。 左右ポインタが最も一般的、配列の両端から中央へ。 反転配列にはこれを頼れ、二分探索は弟分。 スライ ...

問題の説明： '(' と ')' のみからなる文字列が与えられます。最長の有効な（形式が正しく連続している）括弧部分文字列の長さを見つけてください。 例 1： 入力：s = "(()" 出力：2 説明：最長の有効な括弧部分文字列は "()" です 例 2： 入力：s = ")()())" 出力：4 説明：最長の有効な括弧部分文字列は "()()" です 例 3： 入 ...

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) { ...