Python

2つの文字列 s と t が与えられたとき、s を k 回以内の移動で t に変換できるかどうかを判定します。i 回目の移動では、次のいずれかの操作を行えます。s 内の任意のインデックス j(1始まり)を選択します。ただし 1 <= j <= len(s) であり、j は過去の移動で一度も選択されていない必要があります。そのうえで、その位置の文字を i 回シフトします。何もせず、そのままにしておきます。ここで「シフトする」とは、その文字をアルファベット順で次の文字に置き換えることを意味します(z の場合は a へ折り返します)。したがって「文字を i 回シフトする」とは、この操作を

問題の概要 「(」と「)」から構成される文字列 s が与えられます。この問題では、括弧文字列がバランスしている状態を次のように定義します。 すべての左括弧「(」に対して、対応する2つの連続した右括弧「))」が存在すること 左括弧「(」は、必ず対応する「))」より前に現れること たとえば「())」や「())(())))」はバランスしていますが、「)()」や「()))」はバランスしていません。このような文字列が与えられたとき、左括弧または右括弧を挿入して文字列全体をバランスさせるために必要な最小の挿入回数を求めます。 入力例と考え方 たとえば入力が s = (()))))) の場合、出力は

問題の概要 2つの正の整数 n と k が与えられたとき、次の規則に従って生成されるバイナリ文字列 Sn の中から、k番目のビットを求めることを考えます。 S1 = 0 i > 1 のとき、Si = Si-1 + 1 + reverse(invert(Si-1)) ここで、reverse(x) は文字列 x を逆順に並べ替えた結果を返し、invert(x) は x のすべてのビットを反転(0と1を入れ替え)させた結果を返します。 この規則によって生成される最初の4つの文字列は以下のとおりです。 S1 = 0 S2 = 011 S3 = 0111001 S4 = 0111001101

問題の概要 配列 nums と値 target が与えられたとします。このとき、各部分配列（サブ配列）の要素の合計が target と等しくなるような、空でない重複しない（オーバーラップしない）部分配列の最大数を求める必要があります。 例として、nums = [3,2,4,5,2,1,5]、target = 6 の場合を考えてみましょう。この場合の出力は 2 になります。これは、合計が 6 となる部分配列 [2,4] と [1,5] の2つが存在するためです。 解法のアプローチ この問題は、累積和（プレフィックスサム）とセットを組み合わせることで、線形時間で効率的に解くことができます。手順は以

問題の概要値 n が与えられたとします。ここで、n 個の要素を持つ配列 nums を考えます。この配列は、すべてのインデックス i に対して arr[i] = (2*i)+1 と定義されます。つまり、[1, 3, 5, 7, ...] という奇数の連なりです。1 回の操作では、0 <= x, y < n を満たす 2 つのインデックス x と y を自由に選び、nums[x] から 1 を引くと同時に nums[y] に 1 を加えることができます。この操作を繰り返して、配列内のすべての要素を同じ値に揃えたいのです。求めるのは、そのために必要な最小の操作回数です。具体例入力が n

問題概要有向非巡回グラフ(DAG)を考えます。グラフにはn個の頂点があり、各ノードには0からn-1までの番号が付けられています。グラフはエッジリストとして表現され、edges[i] = (u, v)はノードuからノードvへ向かう有向エッジを意味します。このとき、そこから出発すればグラフ内のすべてのノードに到達できるような、最小の頂点集合を見つける必要があります(頂点は任意の順序で返して構いません)。例えば、入力が次のような場合を考えてみましょう。この場合、出力は [0, 2, 3] となります。これらの頂点は他のどの頂点からも到達できないため、ここから探索を開始すれば全ノードをカバーできるから

問題の概要次のようなPythonの関数があるとします。def modify(arr, op, index): if op == 0: arr[index] += 1 if op == 1: for i in range(len(arr)): arr[i] *= 2この関数は、op=0 のとき指定されたインデックスの要素を1増やし、op=1 のとき配列内のすべての要素を2倍にします。同じサイズのゼロ配列 [0, 0, ..., 0] を出発点として、目的の配列 nums を作り上げるまでに必要な関数呼び出しの最小回数を求める

問題概要コインの山が 3×n 個あり、それぞれ異なる枚数のコインが入っています。ここで、3人のプレイヤーが次のルールでゲームを行います。各ステップで、プレイヤー1は任意の3つの山を選びます。選ばれた3つの山の中から、プレイヤー2は最もコイン数の多い山を取ります。続いて、プレイヤー1は2番目にコイン数の多い山を取ります。最後に残った山はプレイヤー3のものになります。この手順を、すべての山がなくなるまで繰り返します。各山のコイン数を格納した整数配列 piles（piles[i] は i 番目の山のコイン数）が与えられたとき、プレイヤー1が獲得できるコインの最大数を求めるのが本問題です。具体例pil

問題概要1からnまでの数字の順列(パーミュテーション)を格納した配列 arr と、初期状態ですべてのビットが0に設定された長さnの2進数文字列があるとします。各ステップ i(1からnまで、2進数文字列と arr の両方でインデックスは1始まり)において、位置 arr[i] のビットが1に設定されていきます。さらに別の値 m が与えられ、「サイズmの1のグループ」が存在する最後のステップを求める必要があります。ここで「1のグループ」とは、左右どちらの方向にも拡張できない連続した「1」の部分文字列を指します。つまり、ちょうど長さmの1のグループが存在する最後のステップを見つけ、そのようなグループが

二分木が与えられ、さらに特定のノード「u」へのポインタも渡されたとします。このとき、u のすぐ右側に位置するノード(必ず同じ階層に存在する)を見つける必要があります。対象のノードは葉ノードの場合もあれば、内部ノードの場合もあります。 例として、次のような二分木が入力されたとしましょう。 ここで u = 6 とすると、出力は 8 になります。ノード 6 の右隣にはノード 8 が存在するため、値 8 が返されるというわけです。 解決のためのアプローチ この問題は、両端キュー(deque)を使った幅優先探索(BFS)、いわゆるレベル順走査によって解くことができます。手順は以下の通りです。 ルー

問題の概要 2つの式木（expression tree）が与えられ、それぞれが同じ値に評価されるかどうかを判定するプログラムを作成します。式木はリスト形式で与えられ、2つの式木の評価結果が一致していれば True を、一致していなければ False を返します。 例えば、下図のような2つの式木が与えられた場合を考えてみましょう。 このとき出力は True となります。2つの式木が同じ値に評価されるためです。 解決のためのステップ この問題は、深さ優先探索（DFS）を使って各木を走査し、葉ノードの値を出現回数として記録したうえで、その辞書同士を比較することで解けます。手順は以下のとおりです。

はじめに本記事では、式木（Expression Tree）の後順巡回（後置記法・逆ポーランド記法）の結果が与えられたとき、そこから式木を復元（構築）し、さらにその式を評価して計算結果を求めるプログラムをPythonで実装します。最終的には、構築した式木の根（ルート）と、木全体を評価した値を返します。問題例次のような後置記法のトークン列が入力として与えられたとします。[1, 2, -, 3, 4, +, *]この列から式木を構築して評価すると、中間記法では (1 - 2) * (3 + 4) に相当し、計算結果は -7 になります。アルゴリズムの流れまず、子の接続位置を表す定数を定義しておきます

問題の概要 この記事では、連結リストで表現された2つの多項式を加算するPythonプログラムを紹介します。 2つの多項式が与えられ、それらの和を求めることを考えます。多項式は連結リストとして表現し、多項式の各項は連結リストの1つのノードに対応させます。各ノードには「係数」「次数（べき指数）」、そして「次のノードへの参照（ポインタ）」を持たせます。最終的なゴールは、2つの多項式の和を表す新しい連結リストを返すことです。 たとえば、入力が以下の画像のような2つの多項式だった場合を見てみましょう。 1x^1 + 1x^2 = 0 と 2x^1 + 3x^0 = 0 この場合、出力は次のようになりま

二分木と、その中の2つの特定ノード x と y が与えられたとします。このとき、2つのノードの最小共通祖先（Lowest Common Ancestor：LCA）を二分木から見つけ出す必要があります。二分木における最小共通祖先とは、ノード x とノード y の両方の子孫となるノードの中で、最も深い位置にあるノードのことです。なお、あるノード自身も自分自身の子孫として扱える点に注意してください。求めたノードを出力として返します。具体例例えば、次のような二分木が与えられたとします。ここで x = 2、y = 4 とした場合、出力は 3 になります。ノード 2 とノード 4 の両方が子孫となっている

二分木と、その中の2つの特定のノード x・y が与えられたとします。このとき、2つのノードの最小共通祖先(Lowest Common Ancestor:LCA)を二分木の中から見つける必要があります。二分木における最小共通祖先とは、ノード x と y の両方が子孫となる最も深いノードのことです。なお、あるノードは自分自身の子孫でもあるとみなされる点に注意してください。該当するノードを見つけ、結果として返します。今回扱うツリーのノード構造は以下のとおりです。TreeNode: data: <整数> left: <TreeNode へのポインタ> righ

誤った二分木とは？ ここでは、ある種の欠陥を持つ二分木を扱います。具体的には、あるノードの右子ポインタが、同じ階層にある別のノードを誤って指してしまっている状態です。この問題を修正するには、誤ったポインタを持つノードを特定し、そのノードとその子孫を木から取り除きます。ただし、誤って指されていたノード自体は木に残します。最後に、修正後の二分木のルートノードを返します。 例として、次のような木が与えられた場合を考えてみましょう。 図のように、ノード4とノード6の間に不正なリンクが張られており、ノード4の右子ポインタがノード6を指しています。 この場合、修正後の木を中順走査（inorder tr

二分木と、その葉(リーフ)に位置する1つのノードが与えられたとしましょう。ここでの課題は、その葉ノードを二分木の新しいルート(根)ノードへと変更することです。この操作は、次の2つのルールに従って行います。 左の子の移動: ノードに左の子が存在する場合、その子は右側へ移動します。 親の移動: ノードの親は、そのノードの左の子になります。この処理の過程で、元の親ノードからそのノードへのリンクは切断(null)されるため、親ノードは子を1つだけ持つ状態になります。 今回扱うツリーのノード構造は以下の通りです。 TreeNode: data: <整数> left: &

はじめに 二分木が与えられたとき、その中に含まれる複数のノードすべての最小共通祖先（Lowest Common Ancestor：LCA）を求めたい場面はよくあります。二分木における最小共通祖先とは、指定されたノード x1, x2, x3, …, xn のすべてを子孫にもつノードの中で、最も深い位置にあるノードのことです。なお、あるノード自身も自分自身の子孫とみなせる点に注意してください。 本記事では、木のルートノードと、祖先を求めたいノードのリストを入力として受け取り、該当するノードを返すプログラムをPythonで実装します。 問題の例 たとえば、次のような二分木を考えてみましょう。 こ

文字列が与えられたとき、その中から「偶数の長さを持ち、中央以外では同じ文字が2つ連続して現れない」という条件を満たす回文部分列を見つけ、その長さを出力することを考えます。たとえば、入力が s = efeffe の場合、出力は 4 になります。これは、条件を満たす偶数長の回文部分列として「effe」（長さ4）のみが存在するためです。解法のアプローチこの問題は、動的計画法（DP）を用いて効率的に解くことができます。手順は以下のとおりです。n を文字列 s の長さとします。dp を n × n の二次元配列として初期化します。各要素は「(長さ, 文字)」というペアで、初期値は (0, ) です。i

PandasとMatplotlibを組み合わせると、DataFrameのデータをもとに複数の線グラフを簡単に描画できます。この記事では、3つの異なる数式（y=x^3、y=x^2、y=mx）のデータを1つのグラフに重ねて表示する手順を解説します。実装の手順図（figure）のサイズを設定し、サブプロット間および周囲の余白（パディング）を調整します。PandasのDataFrameクラスを使って、「equation」「x」「y」の3列からなる2次元の表形式データを作成します。pivot()メソッドを使い、xをインデックス、equationを列、yを値としてデータを再形成します。これにより、各数式ご