Python

符号なし整数 n が与えられたとき、その2進表現に含まれる「1」の個数を求めることを考えます。この個数はハミング重み（Hamming Weight）とも呼ばれます。 例えば、数値が 000000101101 の場合、2進表現中の「1」は4つあるため、結果は 4 となります。 解法のアプローチ この問題は、以下の手順で解くことができます。 数値を2進数の文字列に変換する カウンタ変数 count を 0 で初期化する 2進数文字列の各文字 e について処理を行う 文字が「1」であれば、count を 1 増やす 最後に count を返す 実装例 それでは、実際のコードを見て理解を深め

問題の概要 ある町に、それぞれ異なる金額が保管されている家々があります。一人の泥棒が一晩でこれらの家からお金を奪おうと考えています。 しかし、この町にはセキュリティシステムが設置されており、同じ夜に隣接する2軒の家が荒らされると、自動的に警察に通報される仕組みになっています。 この制約のもとで、泥棒が奪える金額の最大値を求めるのが、この問題の目的です。 問題の例 配列が与えられ、インデックス i における A[i] は i 番目の家にある金額を表します。 例えば、次のような配列を考えてみましょう。 A = [2, 7, 10, 3, 1] この場合、答えは 13 になります。1番目の家（2）、

上限値 n が与えられたとき、2からnまでの範囲に存在する素数の個数を数えることを考えます。例えば、n = 10 の場合、結果は 4 となります。これは、10 未満には 2、3、5、7 という4つの素数が存在するためです。 この問題は「エラトステネスの篩（ふるい）」と呼ばれる古典的なアルゴリズムを使うことで、効率的に解くことができます。以下の手順に従って実装していきましょう。 count を 0 で初期化する サイズ n+1 の配列 prime を作成し、すべて False で埋める i = 0 から n まで以下を繰り返す prime[i] が False の場合 count を 1

連結リスト（リンクリスト）が与えられたとき、それを逆順に並べ替えることを考えます。たとえば、リストが 1 → 3 → 5 → 7 の場合、反転後の新しいリストは 7 → 5 → 3 → 1 となります。 解き方のアプローチ この問題は、再帰を使った手順「solve(head, back)」を定義することで解決できます。具体的な流れは以下のとおりです。 リストの反転を再帰的に行う手順 solve(head, back) を定義する head が存在しない場合は、head をそのまま返す temp := head.next として、次のノードを一時的に保存する head.next := back

数値のリストが与えられたとき、そのリストに重複した要素が含まれているかどうかを確認する必要があります。例えば、リストが [1,5,6,2,1,3] の場合、同じ「1」が2つ存在するため結果は True になります。一方、リストが [1,2,3,4] の場合は重複が存在しないため、結果は False となります。解決のアプローチこの問題は、Pythonの set（集合）データ構造の性質を利用することで簡単に解決できます。set は重複しない一意な値のみを保持するという特徴を持っています。一方、リストは重複した値を含むことが可能です。そこで、リストを set に変換すると、重複要素が存在する場合に

二分木の反転とは二分木が与えられたとき、その左右の子ノードを入れ替えて「鏡像」のような木を作ることを二分木の反転（Invert Binary Tree）と呼びます。これはアルゴリズムの学習やコーディング面接でも頻出のトピックです。例えば、次のような二分木があったとします。これを反転すると、すべてのノードの左部分木と右部分木が入れ替わり、以下のような木になります。解き方：再帰的アプローチこの問題は再帰を使うと非常にシンプルに解けます。考え方は以下の3ステップです。ルートが None（null）であれば、そのまま返す（ベースケース）現在のノードの左ポインタと右ポインタを入れ替える左部分木と右部分木

連結リスト（リンクリスト）にいくつかの要素が格納されているとします。ここでの課題は、指定されたノードをリストから削除する関数を作成することです。例えば、リストが 1 → 3 → 5 → 7 → 9 の場合、値 3 を削除すると、結果は 1 → 5 → 7 → 9 になります。削除の基本的な考え方削除したいノードを指すポインタ「node」が与えられている場合、以下の2つの操作を実行することでノードを削除できます。node.val = node.next.val — 次のノードの値を現在のノードにコピーするnode.next = node.next.next — 現在のノードの参照先を、次の次のノ

アナグラムとは？アナグラムとは、ある文字列やパターンの文字を並べ替えて作られるすべての組み合わせのことを指します。このパターン検索アルゴリズムは少し特殊で、完全に一致するパターンだけでなく、テキスト中に含まれる指定パターンのあらゆる並べ替えを検索します。例えば、「ANAGRAM」と「NAAGARM」は同じ文字で構成されているためアナグラムですが、「cat」と「fat」は文字が異なるためアナグラムではありません。解決のアプローチこの問題を解くには、以下の手順が有効です。1. 文字列を文字のリストに変換する2. リストをソートする3. ソート後の2つのリストが一致すれば、それらはアナグラムであると

問題の概要0からnまでの連続する整数で構成されたリストがあり、そのうち1つの数値だけが欠落しているとします。このとき、欠けている数値をできるだけ効率的に求めることが課題となります。例えば、A = [0, 1, 2, 3, 4, 5, 7, 8, 9] というリストの場合、欠落している数値は 6 です。二分探索を使った解法この問題は、二分探索（バイナリサーチ）のアプローチを用いることで、O(log n) の時間計算量で効率的に解くことができます。アルゴリズムの手順リストを昇順にソートするhigh をリストAの長さ、low を 0 として初期化するlow < high である間、以下の処理を

数値を格納する配列を考えてみましょう。この配列には、ゼロ以外の値とゼロの値が混在しています。ここでの課題は、他の数値の相対的な順序を変えずに、すべてのゼロを配列の右端（末尾）へ移動させることです。 例えば、配列が [0, 1, 5, 0, 3, 8, 0, 0, 9] の場合、処理後の最終的な配列は [1, 5, 3, 8, 9, 0, 0, 0, 0] となります。 解決手順 この問題は、次の手順で解くことができます。 挿入位置を記録するためのインデックス index を 0 で初期化します。 i = 0 から配列 A の長さまで繰り返します。 A[i] != 0 の場合： A[in

ある整数 n が与えられたとき、その数が 3 の累乗（べき乗）であるかどうかを判定する問題を考えてみましょう。例えば、n = 27 は 3 の累乗なので結果は true、一方 n = 15 は 3 の累乗ではないため false となります。この記事では、対数（ログ）を活用したシンプルで効率的な判定方法を解説します。解法のアプローチ：対数を使うこの問題は、以下の手順で解くことができます。常用対数（log10）を利用して判定を行う[log10(n) ÷ log10(3)] の計算結果の小数部分が 0（つまり結果が整数）であれば、n は 3 の累乗であると判定できるこの方法が成り立つ理由は、対数の

文字の配列が与えられたとき、追加のメモリ領域を使用せずに文字列を逆順に反転することを考えます。たとえば、入力が [H, E, L, L, O] である場合、期待される出力は [O, L, L, E, H] となります。 解法のアプローチ この問題は「Two Pointers（ツーポインタ）」と呼ばれる定番のテクニックで効率的に解けます。考え方はシンプルで、配列の両端から中央に向かって文字を交換していくだけです。 手順 2つのポインタを用意します：start = 0、end = 文字列の長さ - 1 s[start] と s[end] の文字を入れ替えます start を1つ増やし、end を

問題概要 2つの整数 a と b が与えられたとき、その合計を求めることを考えます。ただし、+ や - のような算術演算子は使用できません。例えば、a = 5、b = 7 の場合、答えは 12 になります。 解決のアプローチ：ビット演算を活用する この問題は、ビット単位の論理演算子を組み合わせることで解決できます。ポイントは次の3つです。 XOR（^：排他的論理和） … 桁上がりを考慮しない「部分和」を計算します。 AND（&：論理積） … 桁上がりが発生する位置を検出します。 左シフト（<< 1） … 検出した桁上がりを1つ上の位へ移動させます。 アルゴリズムの手

文字列が与えられたとき、その中で最初に一度だけ出現する文字（ユニークな文字）を見つける問題を考えてみましょう。 例えば、文字列が people の場合、出現回数が1回である最初の文字は o です。この場合、そのインデックスである 2 を返します。もし該当する文字が文字列中に存在しない場合は、-1 を返します。 解法のアプローチ この問題は、以下の手順で効率的に解くことができます。 頻度マップ（辞書）を作成する 文字列内の各文字 c について処理を行う： c が頻度マップに存在しない場合は、キーとして追加し値を 1 に設定する すでに存在する場合は、そのカウントを +1 する 作成した頻

FizzBuzzは、プログラミング学習の定番問題として広く知られている古典的なアルゴリズム課題です。この記事では、Pythonを使ってFizzBuzz問題をどのように解けばよいのか、考え方から実装方法まで丁寧に解説します。 FizzBuzzのルールとは？ まず、数値 n が与えられたとします。1から n までのすべての数値を文字列として出力する必要がありますが、その際には以下の制約条件が適用されます。 数値が3で割り切れる場合は、数値の代わりに「Fizz」と表示する 数値が5で割り切れる場合は、数値の代わりに「Buzz」と表示する 数値が3と5の両方で割り切れる（つまり15で割り切れる）場合

ハミング距離とは2つの整数が与えられたとき、それらの「ハミング距離」を求めることを考えます。ハミング距離とは、2つの数値を2進数で表したときに、ビットが異なる位置の個数のことです。例として、7と15という2つの整数を見てみましょう。これらを2進数で表すと、それぞれ「0111」と「1111」になります。最上位ビット（MSb）だけが異なるため、この場合のハミング距離は1となります。解法のアプローチこの問題は、以下の手順で解くことができます。i を31から0まで1ずつ減らしながら繰り返します。b1 = x を i ビット右シフトした値と1のAND（最下位ビットの取り出し）b2 = y を i ビット

連結リストのサイクル検出とは連結リスト（Linked List）の中にサイクル（循環）が存在するかどうかを判定する問題を考えてみましょう。この問題では、サイクルの有無を表現するために整数値のポインタ pos を使用します。pos は、リストの末尾ノードが接続されている位置を示します。つまり、pos = -1 の場合はサイクルが存在しないことを意味します。例えば、連結リストが [5, 3, 2, 0, -4, 7] で pos = 1 の場合、末尾ノード（7）が2番目のノード（3）に接続されているため、サイクルが存在することになります。解法のアプローチ：ハッシュセットを使う最もシンプルな方法は、

この記事では、push（要素の追加）、pop（要素の削除）、top（先頭要素の参照）、さらにgetMin（最小値の取得）をすべて定数時間 O(1) で実行できる特殊なスタック「最小スタック（Min Stack）」の実装方法を解説します。実装する関数は push(x)、pop()、top()、getMin() の4つです。 実装の考え方 通常のスタックでは最小値を求めるのに全要素を走査する必要がありますが、ここでは「現在の最小値（min）」を変数として保持し、pop時に正しく復元できるよう工夫することで、どの操作もO(1)で実現します。手順は以下の通りです。 スタックを初期化するとき、min

ここでは、2つの連結リスト（リンクリスト）AとBが与えられ、それぞれにいくつかの要素が含まれている状況を考えます。このとき、両方のリストが交差しているノードへの参照を返す必要があります。例として、次のような入力を扱います。intersectionVal = 8A = [4, 1, 8, 4, 5]B = [5, 0, 1, 8, 4, 5]skipA = 2skipB = 3skipAとskipBは、それぞれリストAから2要素、リストBから3要素をスキップして交差ノードに到達することを示しています。つまり、両リストは値「8」を持つノードで合流します。解法のアプローチこの問題は、ハッシュマップ（

はじめにプログラミングにおいて、符号なし整数（unsigned int）のビット列を反転させる処理は、ビット演算の基礎を学ぶうえで非常に良い題材です。本記事では、32ビット符号なし整数のビットをすべて逆順に並べ替えるアルゴリズムを、C++のコード例とともにわかりやすく解説します。たとえば、次のような32ビットの2進数表現を持つ数値 x を考えてみましょう。00000000000000000000001001110100このビット列を反転（リバース）すると、結果は以下のようになります。00101110010000000000000000000000タスクは、この反転後のビット列が表す実際の数値を