Python

整数型の配列 nums が与えられます。この配列には常にちょうど1つの最大要素が存在すると仮定します。ここでの課題は、配列内の最大要素が、それ以外のすべての要素の少なくとも2倍の値を持っているかどうかを判定することです。条件を満たす場合は最大要素のインデックスを返し、満たさない場合は -1 を返します。 問題の例 例えば、入力が [3, 6, 1, 0] の場合を考えてみましょう。このとき出力は 1 となります。6が配列内の最大値であり、他のすべての要素（3、1、0）に対して6は2倍以上の大きさだからです。6のインデックスは1であるため、結果として1が返されます。 解法のアプローチ この問

問題概要 単語のリスト words が与えられたとき、文字列 licensePlate に含まれるすべての文字を持つ、リスト内で最も短い単語を見つけます。このような単語は、指定された licensePlate を「完成させる（complete）」単語と呼ばれます。ここでは大文字と小文字は区別せず、必ず答えが存在することが保証されています。また、条件を満たす単語が複数ある場合は、配列の中で最初に出現するものを返します。 ナンバープレートには、同じ文字が複数回出現する場合があります。たとえば licensePlate が「PP」である場合、単語「pile」は P が1つしかないためプレートを完成さ

問題の概要 2つの整数LとRが与えられたとき、範囲[L, R](両端を含む)に含まれる整数の中で、2進表現におけるセットビット(1となっているビット)の個数が素数であるものを数える問題です。 例えば、入力がL = 6、R = 10の場合、出力は4となります。これは、以下の4つの数が条件を満たすためです。 6 → 110(セットビット数:2) 7 → 111(セットビット数:3) 9 → 1001(セットビット数:2) 10 → 1010(セットビット数:2) なお、8は2進表現で1000となり、セットビット数が1(素数ではない)ため対象外です。 解法のアプローチ この問題は、次の手順で解

単語のリストが与えられ、それぞれの単語は各文字のモールス符号を連結したものとして表現できるとします。例えば、「cba」という単語は「-.-..--...」と書けます。これは「-.-.」+「-...」+「.-」を順に連結したものです。このような連結結果を「単語の変換(transform)」と呼びます。国際モールス符号では、アルファベットの各文字がドット(.)とダッシュ(-)の列に標準的にマッピングされています。たとえば「a」は「.-」、「b」は「-...」、「c」は「-.-.」のように対応します。英語アルファベット26文字すべての対応表は次のとおりです。[.-,-...,-.-.,-..,.,.

問題の概要 文字列 S が与えられたとき、その文字を左から右へ順番に行へ書き込んでいくことを考えます。各行の最大幅は 100 単位で、ある文字を書き込んだ結果、行の幅が 100 単位を超えてしまう場合は、その文字は次の行に書き込まれます。さらに、配列 widths も与えられており、widths[0] は「a」の幅、widths[1] は「b」の幅、といった具合に各アルファベットの幅が格納されています。 この問題では、次の 2 つの問いに答える必要があります。 文字列 S の少なくとも 1 文字が書き込まれている行は何行あるか？ 最後の行で使用されている幅は何単位か？ 答えは、長さ 2

平面上に与えられた点のリストの中から、任意の3点を選んで作ることができる三角形のうち、最も大きな面積を持つものを求める問題です。例えば、入力が [[0,0],[0,1],[1,0],[0,2],[2,0]] の場合、出力は 2 となります。解法のアプローチこの問題は、すべての3点の組み合わせについて三角形の面積を計算し、その最大値を求めることで解けます。手順は以下の通りです。結果を格納する変数 res を 0 で初期化する点のリストのサイズを N とする三重ループで、i、j、k の3つのインデックスの組み合わせをすべて列挙する（i < j < k）各組み合わせに対して、3点の座標

小文字の英字のみで構成される文字列 S を考えます。このような文字列では、同じ文字が連続して現れる部分が「グループ」を形成します。たとえば、S = abbxxxxzyy の場合、グループは a、bb、xxxx、z、yy の5つに分けられます。このうち、3文字以上で構成されるグループを「大きなグループ(large group)」と定義します。 本記事では、文字列中に存在するすべての大きなグループについて、その開始位置と終了位置を求めるアルゴリズムを解説します。 たとえば、入力が abcdddeeeeaabbbcd の場合、出力は [[3,5],[6,9],[12,14]] となります。これは、イ

問題の概要2値行列 A が与えられたとします。これは画像を表現しており、次の2つの操作を行った結果の画像を返すことが目的です。水平方向への反転： 画像の各行を逆順に並べ替えるビット反転： 0 をすべて 1 に、1 をすべて 0 に置き換える入力例110101000この場合、出力は次のようになります。出力例100010111例えば最初の行「1, 1, 0」は、逆順にすると「0, 1, 1」になり、さらにビット反転すると「1, 0, 0」となります。解法のアルゴリズムこの問題は、以下の手順で解くことができます。結果を格納するための新しいリスト result を用意する行列 A の各行 i について

長方形のオーバーラップとはここでは、長方形をリスト [x1, y1, x2, y2] として表します。このとき、(x1, y1) は長方形の左下の角の座標、(x2, y2) は右上の角の座標を意味します。2つの長方形が「オーバーラップ（重なり）している」とは、それらの共通部分（交差領域）の面積が正であることを指します。したがって、角や辺だけが接しているような場合（面積がゼロになる接触）は、重なっているとはみなされません。問題の定義2つの軸に平行な長方形（axis-aligned rectangles）が与えられたとき、それらが互いに重なっているかどうかを判定します。たとえば、入力が R1 =

問題の概要小文字だけで構成された2つの文字列 A と B が与えられたとします。このとき、A の中から2文字を選んで入れ替える（スワップする）操作をちょうど1回行うことで、A を B と一致させることができるかどうかを判定するのが「バディ文字列（Buddy Strings）」問題です。例えば、入力が A = ba、B = ab の場合、先頭の2文字を入れ替えるだけで両者は一致するため、出力は True になります。解法のアプローチこの問題は、以下の手順に沿って判定することで効率的に解けます。A と B の長さが異なる場合は False を返します。そもそも文字数が違えば、どんなスワップを行って

レモネードスタンドの釣り銭問題とは？ レモネードスタンドを想像してみてください。レモネード1杯の価格は5ドルで、客は列に並んで順番に1杯ずつ購入していきます。 各客が支払いに使えるのは、5ドル札・10ドル札・20ドル札のいずれかです。店側はすべての客に対して正確な釣り銭を用意し、実質的に客が5ドルを支払う形にしなければなりません。しかも、開店時点では手元に釣り銭が1枚もない状態から始まります。 この記事では、「すべての客に正しく釣り銭を渡すことができるか？」を判定するアルゴリズムを、Pythonで実装しながら解説します。 入力例と出力例 たとえば、支払いの順序が [5, 5, 5, 10,

この記事では、正の整数 N が与えられたとき、その2進数表現の中で隣り合う2つの「1」の間の距離として最も長いもの（バイナリギャップ）を求めるアルゴリズムを、Pythonのコード例とともにわかりやすく解説します。 問題の概要 正の整数 N の2進数表現において、連続して出現する2つの「1」の間の距離のうち最大のものを求めます。ここでいう「距離」とは、2つの「1」の位置（インデックス）の差のことです。もし「1」が2つ以上存在しない場合は、0 を返します。 具体例：入力が 22 の場合 22 を2進数に変換すると 10110 となります。この中には3つの「1」があり、「1」が連続するペアは2組

無限に広がるグリッド上に、原点 (0, 0) からスタートして北向きに立っているロボットがあるとします。このロボットは、次の3種類のコマンドを受け取ることができます。-2：左に90度回転する-1：右に90度回転する1〜9：指定された数だけ前方へ移動するまた、グリッド上には障害物となるマスが存在します。障害物の位置は配列 obstacles で与えられ、i番目の障害物は座標 (obstacles[i][0], obstacles[i][1]) にあるとします。ロボットが障害物のあるマスに進もうとした場合、そのマスには入れず、直前のマスにとどまります。このとき、ロボットが原点から取りうる最大のユー

問題の概要 N × N のグリッドが与えられ、そこに x・y・z 軸に平行な 1 × 1 × 1 の立方体を配置することを考えます。グリッドの各要素 v = grid[i][j] は、セル (i, j) の上に v 個の立方体を縦に積み重ねた「塔」を表しています。 この立体を、上面(xy平面)、正面(yz平面)、側面(zx平面)の3方向から見たときの投影面積をそれぞれ求め、その合計を計算するのがこの問題の目的です。 入力例と出力例 たとえば、入力が [[1,2],[3,4]] の場合を考えてみましょう。 この場合、出力は 17 となります。 解法のアプローチ 3つの投影面積は、それぞれ次

```html 問題の概要 N×Nのグリッドを用意し、その中に1×1×1の立方体をいくつか配置することを考えます。grid[i][j] の値 v は、セル (i, j) の上に v 個の立方体が積み重なった「塔」が存在することを表します。このとき、全体としてできあがる3D形状の総表面積を求めるのが目的です。 たとえば、入力が [[1,2],[3,4]] の場合、出力は 34 になります。 解法のアプローチ 表面積は、次の3つの要素に分解して考えると整理しやすくなります。 上下の面(z方向):立方体が1つでも置かれているセルには、必ず上面と底面が1つずつ現れます。したがって、この成分は「非ゼ

問題概要文字列の配列 A が与えられます。文字列 S に対する「1回の操作」とは、S の偶数番目(0始まり)のインデックスにある2文字同士を入れ替える、または奇数番目のインデックスにある2文字同士を入れ替えることを意味します。任意の回数だけ操作を繰り返した結果、S が T と一致させられる場合、2つの文字列 S と T は「特別に同等(special-equivalent)」であると定義されます。たとえば、S = zzxy と T = xyzz は特別に同等です。S[0] と S[2] を入れ替えて xzzy とし、続けて S[1] と S[3] を入れ替えることで xyzz を作れるためです

問題概要整数からなる配列 A が与えられます。各要素 A[i] に対して、範囲 [-K, K] 内の任意の値 x を選び、それを A[i] に加算することができます。この操作をすべての要素に適用した結果として得られる新しい配列を B とします。このとき、B の最大値と最小値の差が取りうる最小値を求めてください。例えば、入力が A = [0, 10]、K = 2 の場合を考えてみましょう。操作後の配列を B = [2, 8] とすることができ、最大値 8 と最小値 2 の差は 6 となるため、出力は 6 になります。アプローチこの問題は実は非常にシンプルです。ポイントは次の通りです。最大値をでき

問題の概要「RecentCounter」というクラスを作成し、直近のリクエストをカウントすることを考えます。このクラスには ping(t) というメソッドが1つだけあります。引数 t はミリ秒単位の時刻を表し、このメソッドは「t の3000ミリ秒前から現在まで」に発生した ping の回数を返します。つまり、時刻が [t - 3000, t] の範囲内にある ping はすべてカウント対象となり、現在の ping も含まれます。また、ping が呼び出されるたびに、t は必ず前回より厳密に大きい値になると保証されています。例えば、ping を4回、ping(1)、ping(100)、ping(

問題の概要 ログの配列が与えられているとします。配列内の各エントリは、スペースで区切られた単語からなる文字列です。各ログの最初の単語は英数字で構成される識別子（ID）であり、その後には以下のいずれかの種類の文字列が続きます。 ID以降の各単語が小文字の英字のみで構成されている ID以降の各単語が数字のみで構成されている 前者を「文字ログ（letter-log）」、後者を「数字ログ（digit-log）」と呼びます。なお、各ログにはIDの後に必ず1つ以上の単語が存在することが保証されています。 並べ替えのルール 求められるのは、次の条件に従ってログを並べ替え、最終的な順序を返すことです。

整数の配列 A が与えられたとき、それが有効な山型配列（Valid Mountain Array）であるかどうかを判定する問題を考えてみましょう。配列 A が山型配列であるためには、次の条件をすべて満たす必要があります。山型配列の定義配列 A の長さは 3 以上であることあるインデックス i が存在し、以下の2つの条件を満たすことA[0] < A[1] < ... < A[i-1] < A[i]（山頂まで単調増加）A[i] > A[i+1] > ... > A[A.length - 1]（山頂から単調減少）つまり、配列が一度も増加せずに減少するだけ、あ