Python

本記事では、2値行列（0と1のみで構成される行列）を扱うアルゴリズム問題をPythonで解く方法を解説します。具体的には、行列の各行を左右に反転（リバース）した後、各ビットを反転（0を1に、1を0に変換）する処理を実装します。 問題の概要 2値行列 mat が与えられたとします。まず行列内の各行を選択して行を逆順に並べ替え、その後、行内の各要素について0と1を入れ替えます。 例えば、次のような入力が与えられた場合を考えてみましょう。 110010001 この場合、出力は以下のようになります。 100101011 解法のアプローチ この問題は、以下の手順で解決できます。 行インデックス

プログラミングの定番練習問題の一つに、単語のリストを受け取り、それぞれの行を同じ幅の長方形フレームで囲んで出力するというものがあります。一見シンプルですが、文字幅の揃え方や罫線の配置など、細部まで正確に処理する必要があります。この記事では、Pythonでこの問題を解くための手順と実装例をわかりやすく解説します。たとえば、入力が [hello, world, python, programming, nice] の場合、期待される出力は次のようになります。*************** * hello * * world * * python * * progr

区間（インターバル）のリストと、ある特定の時刻 time が与えられているとします。各区間は [start, end] という構造を持ち、それぞれのプログラマーが作業していた時間帯を表しています。このとき、指定した時刻に実際に作業していたプログラマーの人数を求めるのがこの問題です。例として、入力が interval = [[2, 6], [4, 10], [5, 9], [11, 14]]、time = 5 である場合を考えてみましょう。時刻 5 において作業中の区間は [2, 6]、[4, 10]、[5, 9] の3つであるため、出力は 3 となります。解法のアプローチこの問題は非常にシンプ

問題概要 ある整数 n が与えられたとき、n 以下のすべての素数を昇順に並べたリストを生成することを考えます。なお、1 は素数ではない点に注意が必要です。 例えば、入力が 12 の場合、出力は [2, 3, 5, 7, 11] となります。 解決のアプローチ：エラトステネスの篩 この問題は、古典的なアルゴリズムである「エラトステネスの篩（ふるい）」を使うことで効率的に解けます。手順は以下のとおりです。 サイズ n+1 のブール値リスト sieve を作成し、すべて True で初期化します。 結果を格納するための空のリスト primes を用意します。 i を 2 から n まで順番に処理

問題概要 正の整数からなるリスト nums が与えられたとき、リスト内のすべての数値を割り切ることができる最大の正の整数、すなわち「最大公約数（GCD）」を求めます。 例えば、入力が [14, 28, 70, 56] の場合、これらすべての数を割り切れる最大の数は 14 となるため、出力は 14 になります。 解法のアプローチ この問題は、数学における次の性質を利用すると簡単に解けます。 gcd(a, b, c) = gcd(gcd(a, b), c) つまり、リスト全体の最大公約数は、要素を順番に処理しながらGCDを累積的に計算していくことで求められます。具体的な手順は以下の通りです。

数値のリスト nums が与えられたとき、そのリストを1つ以上のグループに分割できるかどうかを判定する問題を考えます。分割は以下の3つの条件をすべて満たす必要があります。各グループのサイズが2以上であることすべてのグループのサイズが同じであること各グループ内のすべての数値が同じであること例えば、入力が [3, 4, 6, 9, 4, 3, 6, 9] の場合、出力は True になります。このリストは [3, 3]、[4, 4]、[6, 6]、[9, 9] という4つのグループに分割でき、各グループのサイズは2で揃っており、グループ内の要素もすべて同じだからです。解法のアプローチこの問題の鍵と

はじめに本記事では、非負整数 n が与えられたとき、r * r = n を満たす数 r を求め、その結果を最も近い整数へ切り捨てる方法を解説します。重要なポイントは、組み込みの平方根関数（math.sqrt など）を使用せずに実装するという点です。例えば、入力が 1025 の場合、出力は 32 1025 だからです。解法のアプローチ：二分探索この問題は「二分探索（バイナリサーチ）」を使うことで効率的に解けます。探索範囲を半分ずつ絞り込んでいくことで、計算量は O(log n) に抑えられます。アルゴリズムの手順n <= 1 の場合は、そのまま n を返します（0 と 1 の平方根はそれぞ

```html ハッピー数とは？ ある正の整数 n が与えられたとき、それが「ハッピー数（Happy Number）」であるかどうかを判定することを考えます。 ハッピー数とは、任意の正の整数から出発し、その数を「各桁の数字の二乗の合計」で置き換える操作を繰り返したとき、最終的に 1 に到達する数 のことです。1 に到達できず、同じ値の循環に永遠に陥ってしまう場合はハッピー数ではありません。つまり、1 にたどり着ける数だけがハッピー数となります。 例：19 の場合 入力が 19 のとき、この数はハッピー数であるため結果は true になります。実際の計算の流れを見てみましょう。 12 + 92

ある整数 n が与えられたとき、数字の任意の位置に「5」を挿入することで作れる最大の数を求める問題を考えてみましょう。 たとえば、入力が n = 826 の場合、「5」を挿入できる候補は「5826」「8526」「8256」「8265」の4通りあります。この中で最大となるのは 8526 であり、これが出力になります。 解法のアプローチ この問題は、考えられるすべての挿入位置を試すシンプルな全探索で効率的に解くことができます。手順は以下の通りです。 temp: 数値 n を文字列に変換したもの ans: 初期値として負の無限大(float(-inf))を設定 i を 0 から temp の長さま

Pythonでは、数値のリストの中から最も多く出現する要素を見つけ、その出現回数を取得したい場面がよくあります。本記事では、二重ループを使った基本的なアルゴリズムでこの問題を解く方法を解説します。 問題の概要 数値のリスト nums が与えられたとき、最も頻繁に出現する要素の「出現回数」を返します。要素そのものではなく、何回現れたかという回数が答えになります。 例えば、入力が [1,5,8,5,6,3,2,45,7,5,8,7,1,4,6,8,9,10] の場合、数値 5 が3回出現するため、出力は 3 となります。 解法のアプローチ この問題は以下の手順で解くことができます。 最大出現

ソート済みの数値リストが与えられたとき、各要素を2乗した結果を再びソートされた順序で出力することを考えます。入力には負の数や0が含まれる場合もある点に注意が必要です。2乗すると負の数は正の数になるため、単純に2乗するだけでは順序が崩れてしまいます。例えば、入力が [-12, -6, -5, -2, 0, 1, 2, 4, 8, 9, 10, 15, 18, 20, 35, 38, 69] の場合、出力は次のようになります。[0, 1, 4, 4, 16, 25, 36, 64, 81, 100, 144, 225, 324, 400, 1225, 1444, 4761]解決手順この問題は以下の

問題概要文字列 s と2つの整数 i、j（i < j）が与えられているとします。ここで p を、文字列 s を永久に繰り返してできる無限長の文字列と考えます。このとき、p のうちインデックス [i, j) の範囲に該当する部分文字列を求めるのが課題です。たとえば、入力が s = programmer、i = 4、j = 8 の場合、出力は ramm になります。解法のアプローチこの問題は、次の手順で解くことができます。結果を格納するための空文字列 p を用意します。t を i から j - 1 まで順にループさせます。各ループで、s[t % len(s)] に相当する文字を p の末尾に

問題概要数値のリスト nums が与えられたとき、リストをインプレース（元のリストを直接書き換える形）で更新し、すべてのゼロをリストの末尾へ移動することを考えます。その際、ゼロ以外の要素の相対的な順序は変更してはいけません。また、追加で使用できるメモリ領域は O(1) という制約があります。たとえば、入力が [2,0,1,4,0,5,6,4,0,1,7] の場合、出力は [2, 1, 4, 5, 6, 4, 1, 7, 0, 0, 0] となります。アルゴリズムの手順この問題は、2つのポインタ（インデックス）を使うテクニックで効率的に解くことができます。手順は以下のとおりです。L のサイズが

問題概要ある整数 n が与えられたとき、その数を3進数（基数3）で表した文字列を求めることを考えます。例えば、入力が 17 の場合、出力は「122」となります。これは 1×9 + 2×3 + 2×1 = 17 と計算できるためです。なお、Pythonには2進数・8進数・16進数向けの bin()・oct()・hex() といった組み込み関数は存在しますが、3進数に対応する関数はないため、自前で変換処理を実装する必要があります。解法のアプローチこの問題は、次の手順で解くことができます。n が負の場合は符号「-」を記録しておき、n を絶対値に置き換えるn が 3 未満の場合は、そのまま文字列として

文字列インターリーブとは2つの文字列 s と t が与えられたとき、最初の文字列 s の文字から始めて、両者の文字を交互に並べた新しい文字列を作ることを「インターリーブ(交互結合)」と呼びます。片方の文字列が先に尽きた場合は、余った文字をそのまま末尾に追加します。例えば、入力が s = abcd、t = pqrstu の場合、出力は apbqcrdstu となります。アルゴリズムの手順この問題は、以下の手順で解くことができます。結果を格納する変数 res を空文字列として初期化します。インデックス用の変数 i を 0 に設定します。m を s と t の長さのうち小さい方の値とします。i &l

この記事では、Pythonを使って複数の区間（インターバル）の共通部分を見つけるアルゴリズムを解説します。 問題の概要 各要素が [start, end] の形式で表される区間のリストが与えられます。ここで start は区間の開始時刻、end は終了時刻を意味し、両端を含むものとします。このとき、与えられたすべての区間に共通して含まれる区間（交差部分）を求めるのが目的です。 例えば、入力が次のような場合を考えてみましょう。 [[10, 110], [20, 60], [25, 75]] この場合、3つの区間すべてに共通する範囲は [25, 60] となります。なぜなら、最も遅い開始時刻が

逆階乗とは ある数 a が与えられたとき、その階乗が a と等しくなる整数 n(n! = a)を求める問題を「逆階乗」と呼びます。階乗とは、n! = n × (n − 1) × (n − 2) × … × 1 と定義される演算です。該当する整数 n が存在しない場合は −1 を返します。 たとえば、入力が a = 120 の場合、5! = 120 となるため、出力は 5 になります。 解法のアプローチ この問題は、次の手順で解くことができます。 カウンタ i を 0、num を 1 で初期化する 結果を格納するための空リスト L を用意する i が a 未満である間、次の処理を繰り返す

問題概要 数値のリスト nums と整数 k が与えられたとき、リストからちょうど1つの要素を削除することで、残りの要素の平均値がちょうど k と一致するかどうかを判定します。この問題には、次の制約があります。 2 ≤ n ≤ 1,000(n は nums の要素数) nums[i] ≤ 1,000,000、k ≤ 1,000,000 たとえば、入力が [5,3,2,4,6,10]、k = 4 の場合、出力は True になります。10 を削除すると、残りの要素の平均は (5+3+2+4+6)/5 = 4 となり、k と一致するためです。 解法の考え方 この問題は、数学的な性質を利用するこ

この記事では、Pythonを使って「リスト内に k と -k の両方が存在するような、最大の数 k を見つける」問題の解き方を解説します。 問題の概要 数値のリスト nums が与えられたとき、k と -k がどちらもリスト内に存在するような最大の数 k を求めます。該当する要素が存在しない場合は -1 を返します。 たとえば、入力が [-5, 2, 9, -6, 5, -9] の場合、「9」と「-9」が両方存在するため、答えは 9 となります。 解法のアプローチ この問題は、リストを正の数と負の数に分けてソートし、対応するペアを効率的に探すことで解けます。具体的な手順は以下の通りです。 L

ここでは、二次元のバイナリ行列を扱います。この行列は長方形のチェス盤を表しており、0 は空きマス、1 はナイト（騎士）がいるマスを意味します。ナイトは、実際のチェスと同じように、水平方向に2マス・垂直方向に1マス、あるいは垂直方向に2マス・水平方向に1マス移動できます。この問題の目的は、盤上に存在するどれか2つのナイトが互いに攻撃し合っているかどうかを判定することです。例として、次のような入力が与えられた場合を考えます。000000100000010この場合、2つのナイトが互いに攻撃可能な位置にあるため、出力は True になります。解法のアプローチこの問題は、以下の手順で効率的に解くことがで