Python

本記事では、平均O(1)時間で以下の3つの操作をすべてサポートできるデータ構造を、Pythonで実装する方法を解説します。 insert(val) — 要素 val がまだセットに存在しない場合に挿入します。 remove(val) — 要素 val がセットに存在する場合に削除します。 getRandom() — 現在の要素集合からランダムに1つの要素を返します。どの要素も等しい確率で選ばれる必要があります。 アルゴリズムの考え方 ポイントは、辞書（ハッシュマップ）とリスト（動的配列）を組み合わせることです。辞書によって要素の有無をO(1)で判定でき、リストの末尾操作により削除もO(1)

問題の概要ある「壊れた電卓」があるとします。ディスプレイには何らかの数字が表示されていますが、私たちが実行できる操作は次の2つだけです。2倍（Double） … ディスプレイに表示されている数字を2倍にする1減らす（Decrement） … ディスプレイに表示されている数字から1を引く初期状態では、電卓には数字 X が表示されています。ここで、数字 Y を表示させるために必要な最小の操作回数を求めてください。例えば、入力が X = 5、Y = 8 の場合、答えは 2 になります。これは「1減らして4にする」→「2倍して8にする」という2回の操作で目的の値に到達できるためです。解法のアプローチ：

問題概要あるソーシャルグループにN人の異なる人がおり、それぞれ0からN-1までの一意な整数IDが割り当てられているとします。ここにログのリストがあり、各logs[i] = [time, id_A, id_B]には、負でない整数のタイムスタンプと、2人の異なる人物のIDが含まれています。各ログは、2人が友達になった時刻を表しており、AがBと友達であれば、BもAと友達です。人Aが人Bと「知り合い(acquainted)」であるとは、AがBと直接友達であるか、Aが「Bの知り合いである誰か」と友達であることを指します。このとき、すべての人が互いに知り合いになる最も早い時刻を求める必要があります。そのよ

ジグザグラベル付き二分木とはすべてのノードが2つの子を持つ無限の二分木を考えます。この木では、ノードに行順にラベルが付けられており、奇数行(1行目・3行目・5行目…)は左から右へ、偶数行(2行目・4行目・6行目…)は右から左へとラベルが振られます。そのため、木全体は次のようなジグザグ状の構造になります。このような木において、あるノードのラベルが与えられたとき、ルートからそのノードまでのパス上のラベル一覧を求めるのが本問題です。たとえば入力が label = 14 の場合、出力は [1, 3, 4, 14] となります。解法のアプローチ基本的なアイデアは、「ジグザグのラベル順序に従って配列(tr

問題の概要 二分木のルートが与えられたとき、その木に含まれる任意の部分木の平均値の最大値を求めるのがこの問題の目的です。例として、次のような二分木を考えてみましょう。 この場合の出力は 6 になります。理由は以下の通りです。 ノード5を根とする部分木：(5 + 6 + 1) / 3 = 4 ノード6を根とする部分木：6 / 1 = 6 ノード1を根とする部分木：1 / 1 = 1 これらの中で最も大きいのは6なので、答えは6となります。 解法のアプローチ この問題は後順走査（post-order traversal）による再帰を使うことで効率的に解けます。各ノードについて「その部分木の

根付き二分木が与えられたとき、その最も深い葉ノードの最小共通祖先（LCA: Lowest Common Ancestor）を返す問題を考えてみましょう。この問題を解く前に、以下の定義を確認しておきます。前提となる定義二分木のノードは、子を持たない場合に限り「葉ノード」と呼ばれます。木の根（ルート）の深さは0とし、あるノードの深さがdであるとき、その子ノードの深さはd+1になります。ノード集合Sの最小共通祖先とは、S内のすべてのノードがその部分木に含まれるような、最も深いノードAのことです。たとえば、入力が [1,2,3,4,5] の二分木である場合、出力は [2,4,5] となります。これは、

問題の概要ノードに 0 から n-1 までのラベルが付いた有向グラフを考えます。このグラフでは、各辺は赤または青のいずれかで塗られており、自己ループや平行辺（同じ向きの複数の辺）が存在することもあります。red_edges 内の各 [i, j] はノード i からノード j への赤い有向辺を、blue_edges 内の各 [i, j] は青い有向辺を表します。求めたいのは長さ n の配列 answer です。各 answer[X] には、ノード 0 からノード X までの最短経路のうち、通る辺の色が交互に入れ替わるものの長さを格納します。そのような経路が存在しない場合は -1 を返します。たと

問題概要 1からNまでの番号が付けられたN個の都市があるとします。接続情報connectionsの各要素は[city1, city2, cost]という形式で与えられ、これはcity1とcity2を直接つなぐためのコストを表します。ここで求めたいのは、任意の2つの都市の間に必ず経路が存在する状態（全域木）を作るときの最小コストです。コストは採用した接続のコストの合計であり、すべての都市を接続できない場合は-1を返します。 たとえば、次のようなグラフが与えられたとします。 この場合の出力は6になります。3つの都市をすべてつなぐには2本の接続で十分なので、コストの小さい組み合わせ、すなわち[2

問題の概要 整数の配列 nums が与えられます。ここでいう「1回の操作」とは、任意の要素を1つ選び、その値を1だけ減らすことを指します。 配列 A が「ジグザグ配列」であるとは、以下の条件のいずれか一方を満たすことです。 偶数インデックスの要素が隣接要素より大きいパターン: A[0] > A[1] < A[2] > A[3] < A[4] > ... という形になります。 奇数インデックスの要素が隣接要素より大きいパターン: A[0] < A[1] > A[2] < A[3] > A[4] < ... という形になります。 この

問題概要 二人のプレイヤーが二分木の上でターン制のゲームを行います。二分木の根(root)と、木のノード数nが与えられます。ここでnは奇数であり、各ノードは1からnまでの互いに異なる値を持っています。 まず先手のプレイヤーが1 ≤ x ≤ nを満たす値xを選び、続いて後手のプレイヤーがy ≠ xを満たす値yを選びます。先手は値xのノードを赤色に塗り、後手は値yのノードを青色に塗ります。 その後、先手から始めて交互に手番が進みます。各ターンで、プレイヤーは自分の色(先手なら赤、後手なら青)のノードを1つ選び、その隣接する未着色ノード(左の子・右の子・親のいずれか)を自分の色で塗ります。このような

スナップショット配列とは本記事では、指定されたインターフェースを満たす「スナップショット配列（SnapshotArray）」をPythonで実装する方法を解説します。このデータ構造は、以下の4つの操作をサポートする必要があります。SnapshotArray(int length)：指定された長さで配列状のデータ構造を初期化します。初期状態では、すべての要素が0です。set(index, val)：指定されたインデックスの要素を val に設定します。snap()：現在の配列全体のスナップショットを取得し、snap_id を返します。snap_id は snap() を呼び出した回数から1を引い

問題の概要 0と1のみから構成されるバイナリ配列 data が与えられたとき、配列内のすべての 1 をどこか一箇所に連続して並べる(グループ化する)ために必要な最小スワップ回数を求めます。 例えば、配列が [1,0,1,0,1,0,0,1,1,0,1] の場合、出力は 3 になります。これは [0,0,0,0,0,1,1,1,1,1,1] のように、すべての 1 を隣接させることが可能だからです。 解法のアプローチ この問題は「累積和(プレフィックスサム)」と「スライディングウィンドウ」を組み合わせることで効率的に解くことができます。 基本的な考え方は以下の通りです。まず配列全体に含まれる

d個のサイコロがあり、それぞれのサイコロには1からfまでの数字が書かれた面があるとします。このとき、出た目の合計がターゲットの値と一致するような振り方（全 fd 通りのうち）の数を、10^9 + 7 で割った余りとして求めます。 例えば、d = 2、f = 6、target = 7 の場合、答えは6になります。6面のサイコロ2つを振って合計が7になる組み合わせは、「1+6」「2+5」「3+4」「4+3」「5+2」「6+1」の6通り存在するためです。 解法のアプローチ この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。 m := 10^9 + 7（剰余を取るため

ここでは、次の2つの機能を持つファイルシステムを設計することを考えます。 createPath(path, value) ― 新しいパスを作成し、可能であればそのパスに値を関連付けてTrueを返します。パスがすでに存在する場合や、親パスが存在しない場合にはFalseを返します。 get(path) ― 指定されたパスに関連付けられた値を検索して返します。パスが存在しない場合は-1を返します。 パスの形式は、スラッシュ「/」に続けて1文字以上の小文字の英字が並んだ文字列を1つ以上連結したものです。たとえば「/programming」や「/programming/problems」は有効なパ

問題概要 文字列 s が与えられ、その部分文字列に対して複数のクエリを処理することを考えます。各クエリ queries[i] は [left, right, k] の3つの要素で構成されており、部分文字列 s[left]〜s[right] を自由に並べ替えたうえで、最大 k 個までの文字を任意の小文字アルファベットに置き換えることができます。これらの操作を施した結果、部分文字列が回文にできる場合は true、できない場合は false がクエリの結果となります。最終的に、i 番目のクエリ queries[i] の結果が answer[i] となる配列 answer[] を求めます。 例として、

はじめに文字列 s が与えられたとき、s 内に登場する順序と同じ順序で、すべての単語を垂直方向（縦方向）に読み取る問題を考えてみましょう。結果は文字列のリストとして返され、必要に応じてスペースで埋めます。ただし、末尾のスペースは許可されません。各単語は必ず1つの列だけに配置され、1つの列には1つの単語しか含まれません。例えば、入力文字列が HOW ARE YOU の場合、出力は次のようになります。[HAY, ORO, WEU]これは、各行を左から右へ読むことで元の単語が復元できることを意味します。アルゴリズムの考え方この問題を解くために、以下の手順に従います。s をスペースで区切って文字列のリ

問題の概要空ではない整数型の配列が与えられます。この配列では、ある1つの要素だけが1回出現し、それ以外のすべての要素は3回ずつ出現します。この「たった1回しか現れない要素」を見つけるのが本記事のテーマです。例えば、配列が [2, 2, 3, 2] の場合、出力は 3 となります。解法のアプローチこの問題は、各数値をビット単位に分解して集計することで解決できます。各ビット位置における「1」の出現回数を数え、3で割った余りを取れば、余ったビットがそのまま答えの数値を表します。手順は以下の通りです。配列内の各要素の絶対値の最大値を求め、max_num として保存する。max_bits = int(l

はじめに文字列が与えられたとき、それが有効なIPv4アドレスか、有効なIPv6アドレスか、あるいはどちらでもないかを判定する方法を解説します。IPv4アドレスのルールIPv4アドレスは、ドット区切りの10進表記(ドット・デシマル記法)で表されます。これは0から255までの範囲にある10進数4つをドット(.)で区切った形式で、例えば「192.168.254.1」のようなものです。なお、先頭に余分なゼロが付いたIPv4アドレスは無効とみなされます。たとえば「192.168.254.01」は不正なアドレスです。IPv6アドレスのルールIPv6アドレスは、16ビットを表す4桁の16進数8グループで構成

Pythonにはオブジェクトを比較するための方法として、「==」演算子と「is」演算子の2つがあります。一見似ているように見えますが、この2つはまったく異なる目的で使われるため、その違いを正しく理解することが重要です。 == 演算子とは（値の等価性を比較） 「==」演算子は、2つのオブジェクトの値が等しいかどうかを比較します。つまり、中身のデータが同じであれば、たとえ別々のオブジェクトであってもTrueを返します。 is 演算子とは（同一性を比較） 一方、「is」演算子は、2つのオペランドが同じオブジェクトであるかどうか（同一性）を比較します。メモリ上のIDが一致するかどうかを確認するため

PythonとはPythonは、シンプルな実装と高い可読性を重視して設計されたプログラミング言語です。動的型付けを採用しており、変数の型を事前に宣言する必要がありません。また、C言語のようなポインタという概念を持たないため、初心者でも直感的にコードを書きやすい点が大きな特徴です。BashとはBash(Bourne Again Shell)は、コマンドラインインタプリタの一種で、LinuxやmacOSには標準で搭載されています。その他のOSにもインストールして利用することが可能です。LinuxおよびmacOSにおいては、デフォルトのユーザーシェルとして広く使われています。以下に、PythonとB