Python

この記事では、値としてリストを持つ辞書を扱い、そのリストの中身を空にする（クリアする）方法について解説します。アプローチは主に2つあります。ひとつは clear() メソッドを使う方法、もうひとつは辞書内包表記を使って各キーに空のリストを代入する方法です。方法1：ループと clear() メソッドを使うまず、辞書の各キーに対してループ処理を行い、値であるリストに対して clear() メソッドを呼び出します。この方法では元の辞書オブジェクトを保持したまま、リストの中身だけを空にできます。x1 = {Apple : [4,6,9,2], Grape : [7,8,2,1], Orange : [

cmp()関数とはcmp()は、2つの整数を比較するためのPython標準ライブラリの関数です。比較結果は以下の3パターンで返されます。最初の整数が2番目より小さい場合：-1最初の整数が2番目より大きい場合：1両者が等しい場合：0なお、組み込み関数のcmp()はPython 3で廃止されました。そのため本記事では、同じ挙動を再現する独自関数を定義し、その使い方を紹介します。実装は非常にシンプルで、PythonではTrueが1、Falseが0として扱われる性質を利用した「(x > y) - (x < y)」という式で実現できます。サンプルコード次の例では、x>y、x<y、

Pythonでは、文字列として格納された複数のリストを、実際の「リストのリスト」（ネストしたリスト構造）へ変換したい場面があります。例えば、[[0, 1, 2, 3], [Mon, Tue, Wed, Thu]] のような文字列のリストを、各要素が個別のリストになる形に整形するケースです。この記事では、文字列のリストをリストのリストへ変換する代表的な2つの方法を、サンプルコードと実行結果とともにわかりやすく解説します。方法1：strip()とsplit()を組み合わせるstrip()メソッドで文字列の前後にある角括弧 [] を取り除き、その後 split()メソッドでカンマ区切りに分割します。

二分木が与えられたとき、そのジグザグレベル順走査（Zigzag Level Order Traversal）の結果を求める問題を考えます。これは、第1レベルは左から右へ、第2レベルは右から左へ、第3レベルは再び左から右へ……というように、階層ごとに走査の向きを交互に切り替えながらノードを訪問する手法です。 例として、次のような二分木を扱います。 この木に対する走査結果は [[3], [20, 9], [15, 7]] になります。ルートの 3 を含む第1レベル、右から左へ読む第2レベル（20, 9）、そして左から右へ読む第3レベル（15, 7）という具合です。 アルゴリズムの流れ キュー

問題概要 基本的な電卓を実装し、単純な数式の文字列を評価することを考えます。入力となる式の文字列には、負でない整数、+・-・*・/ の演算子、そして空白文字のみが含まれるものとします。また、整数同士の除算では、商の部分(小数点以下を切り捨てた値)のみを使用します。 例えば、入力が 3+2*2 の場合、乗算が先に計算されるため、出力は 7 となります。 解法のアプローチ:スタックを活用する この問題を効率的に解く鍵となるのがスタック(stack)です。ポイントは、*(乗算)と /(除算)が +(加算)や -(減算)よりも演算の優先順位が高いという点です。 スタックを使えば、優先順位の高い演算

はじめに 配列Aが与えられたとき、重複のない数値の集合をシャッフルすることを考えます。例えば、入力が [1,2,3] の場合、シャッフルを実行すると [1,3,2] となり、リセット後に再度シャッフルすると [2,3,1] のようになります。 この問題を解決するために、__init__()、reset()、shuffle() という3つのメソッドを持つクラスを設計します。それぞれの動作は以下の通りです。 アルゴリズムの設計 init（コンストラクタ）の処理 original := 与えられた配列のコピーを保持する temp := 元の配列 nums をそのまま格納する indices :=

問題概要二分木のルートノードが与えられます。各ノードには0から25までの値が格納されており、これらは文字「a」から「z」に対応しています。つまり、0は「a」、1は「b」というように対応付けられています。このとき、木の葉から始まってルートで終わるパスの中で、辞書順（lexicographical order）で最も小さい文字列を見つける必要があります。例えば、次のような木を考えてみましょう。この場合、パスの値の並びは [0, 3, 25] となるため、出力は adz になります。解法のアプローチこの問題はDFS（深さ優先探索）を使って解くことができます。以下の手順で進めます。DFS走査用のメソッ

与えられた先行順走査（プレオーダートラバーサル）に一致する二分探索木を作成することを考えます。例えば、先行順走査が [8,5,1,7,10,12] の場合、出力は [8,5,10,1,7,null,12] となり、構築される木は以下のようになります。アルゴリズムの考え方先行順走査では、最初の要素が必ず根（ルート）になります。また、二分探索木の性質上、あるノードより小さい値は左部分木へ、大きい値は右部分木へ配置されます。この性質を利用し、スタックを使って祖先ノードを管理しながら木を組み立てていくのがポイントです。手順root := 先行順リストの0番目の要素をノードとして作成stack := 空

ベルトコンベア上に、D日以内に港から別の港へ発送しなければならない荷物が流れてくるとします。コンベア上のi番目の荷物の重さは weights[i] で表されます。毎日、このコンベアから船へ荷物を積み込みますが、船の最大積載重量を超えて積むことはできません。ここで求めたいのは、コンベア上のすべての荷物をD日以内に発送し切るために必要な、船の最小積載容量です。たとえば、入力が [3,2,2,4,1,4]、D = 3 の場合、出力は 6 になります。これは、3日間ですべての荷物を発送するには容量6の船が最低限必要だからです。具体的な積み込み方は以下のようになります。1日目：3, 22日目：2, 43

問題の概要ある書店のオーナーが、customers リストの要素数に等しい分数だけ店を開けているとします。毎分 customers[i] 人の客が入店し、その分が終わると全員が退店します。オーナーには機嫌の良い時間帯と悪い時間帯があり、i 分目に不機嫌であれば grumpy[i] = 1、そうでなければ grumpy[i] = 0 と表されます。オーナーが不機嫌な分に入店した客は不満を抱き、機嫌が良い分に入店した客は満足します。ここで、オーナーは「X 分連続で不機嫌にならないようにするテクニック」を知っていますが、このテクニックは一度しか使えません。この条件のもとで、一日を通じて満足できる客の

問題概要 二分木が与えられたとき、あるノードが「不十分(insufficient)」であるとは、そのノードを通るすべてのルートからリーフへのパスのノード値の合計が、与えられた limit よりも厳密に小さいことを意味します。この条件を満たすすべての不十分なノードを同時に削除し、処理後の二分木のルートを返すのが本問題の目的です。 例えば、次のような二分木があり、limit = 1 が与えられたとします。 このとき、不十分なノードを削除した後の出力は以下のようになります。 解法のアプローチ この問題は、再帰(深さ優先探索)を使って効率的に解くことができます。基本的な考え方は、各リーフノードに

文字列 text が与えられたとき、そこに含まれるすべての異なる文字をそれぞれちょうど1回だけ使用する「辞書順最小の部分列」を求めることを考えます。たとえば、入力が "cdadabcc" の場合、答えは "adbc" となります。 解き方のアプローチ この問題はスタックと貪欲法（グリーディ法）を組み合わせることで効率的に解けます。ポイントは「スタックの先頭にある文字より小さい文字が出現し、その先頭の文字が文字列の後方にまだ残っているなら、先頭の文字を取り除いてもよい」という発想です。具体的な手順は以下の通りです。 スタック st、マップ last_o

R行C列の整数で構成される行列Aが与えられます。このとき、左上のセル [0, 0] を出発点とし、右下のセル [R-1, C-1] を終点とする経路の中から、「経路上のセルのうち最小の値」をスコアとしたとき、そのスコアが最大になる経路を見つけます。例えば、ある経路が 8 → 4 → 5 → 9 と辿るとき、経路上の最小値は 4 なので、この経路のスコアは 4 となります。経路は、現在いるセルから上下左右の4方向（北・東・南・西）にある未訪問セルへ移動することで伸ばしていきます。具体例次のようなグリッドを考えてみましょう。545126746オレンジ色で示されたセルが最適な経路です。この経路上の最

問題の概要一連の本があるとしましょう。ここで、i番目の本は厚さ books[i][0]、高さ books[i][1] で表されます。これらの本を、幅が shelf_width の本棚に、与えられた順序どおりに並べていきたいと思います。同じ棚には、厚さの合計が shelf_width 以下になる範囲で複数の本を置けます。それ以上置けなくなったら、新しい段を作成します。このとき、本棚全体の高さは、その段に置いた本の中で最も高い本の高さぶんだけ増加します。すべての本を置き終えるまで、この手順を繰り返します。ただし重要なルールとして、各ステップで本を置く順序は、必ず与えられた本の並び順と同じでなければ

本記事では、二分木から特定のノードを削除した際に生じる「フォレスト（森）」の根を求めるアルゴリズムを、Pythonのコードとともにわかりやすく解説します。問題の概要二分木の根（root）が与えられ、木に含まれる各ノードは一意の値を持っているものとします。ここで、to_delete リストに含まれる値を持つノードをすべて削除すると、木はいくつかの独立した部分木、すなわち「フォレスト」へと分割されます。このとき、残ったフォレストを構成する各木の根を見つけるのが目的です。たとえば、次のような二分木が入力として与えられたとします。このとき to_delete 配列が [3, 5] である場合、値3と5

問題の概要文字列が「(」と「)」のみで構成され、かつ以下のいずれかの性質を満たすとき、その文字列は有効な括弧文字列(VPS: Valid Parentheses String)と呼ばれます。空文字列である、またはAB という形式で表せる(A と B はどちらも VPS)、または(A) という形式で表せる(A は VPS)さらに、任意の VPS である S に対して、ネスト深度 depth(S) を次のように定義します。depth() = 0depth(A + B) = max(depth(A), depth(B))(A と B は VPS)depth(( + A + )) = 1 + dept

問題の概要 正の整数からなる配列 arr が与えられたとき、次の条件をすべて満たす二分木を考えます。 各ノードは、子を 0 個または 2 個持つ。 配列 arr の値は、木の中間順巡回（inorder traversal）における各葉の値に対応する。 各非葉ノードの値は、左部分木と右部分木それぞれにおける最大の葉の値の積と等しい。 考えられるすべての二分木の中から、各非葉ノードの値の合計が最小となるものを見つけるのが目的です。例えば、入力 arr = [6, 2, 4] の場合、出力は 32 になります。この配列からは次の 2 通りの木が構成できます。 上の図では、非葉ノードの値（24

受講すべきコースが合計 numCourses 個あり、それぞれ 0 から numCourses-1 までの番号が付けられているとします。一部のコースには前提条件（先修科目）があり、たとえば「コース 0 を受講するには、まずコース 1 を修了していなければならない」という関係は、ペア [0, 1] として表現されます。ここで、コースの総数と前提条件のペアのリストが与えられたとき、すべてのコースを修了することが可能かどうかを判定します。 たとえば、入力が numCourses = 2、prerequisites = [[1, 0]] の場合、結果は true になります。受講すべきコースは合計 2

問題概要全部で n 個のコース（科目）があり、それぞれ 0 から n-1 までの番号が付けられているとします。一部のコースには先修科目（前提条件）が設定されており、コースの総数と前提条件ペアのリストが与えられたとき、すべてのコースを修了するための履修順序を 1 つ求めるのがこの問題の目的です。正しい順序は複数存在する場合がありますが、そのうちのどれか 1 つが見つかれば十分です。もし前提条件に循環が含まれていて、すべてのコースを修了することが不可能な場合は、空の配列を返します。入出力の例たとえば、入力が 2 と [[1, 0]] の場合、出力は [0, 1] になります。これは、合計 2 つの

整数が入れ子になったリスト（ネストされたリスト）があるとします。このリストを平坦化（フラット化）するためのイテレータを実装する必要があります。各要素は整数、またはリストのいずれかであり、そのリストの要素もまた整数や別のリストである可能性があります。例えば、入力が [[1, 1], 2, [1, 1]] の場合、出力は [1, 1, 2, 1, 1] のようになります。解決のアプローチこの問題を解くためには、以下の手順に従います。初期化処理： コンストラクタでネストされたリストを受け取り、結果を格納するための空のリスト res とインデックス index = 0 を用意し、再帰関数 getVal