C++

この問題では、2つの二分探索木（BST）が与えられ、両方の木に共通して存在するノードを見つけ出し、その値を出力する必要があります。二分木とは二分木とは、すべてのノードが最大2つの子ノードを持つ特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。さらに二分探索木では、「左の子ノード < 親ノード < 右の子ノード」という大小関係が常に成り立つという性質があります。例上の図のように2つの二分木が与えられた場合、両方の木に存在する同じ値のノードをすべて出力することが求められます。アルゴリズムの考え方この問題は、補助スタックを使用することで効

問題の概要このプログラミング問題では、2つの文字列が与えられます。求められているのは、両方の文字列に共通して含まれる文字をすべて見つけ出し、アルファベット順(辞書順)に出力することです。共通する文字がひとつも存在しない場合は「No common characters」と出力します。なお、ここで扱う文字列は小文字のアルファベットのみで構成されているものとします。入出力例まず、具体的な例で動作を確認してみましょう。Input : string1 : adsfhslf string2 : fsrakf Output : affs解説： 2つの文字列に共通する文字は「a」「f」「s」で

問題概要 この問題では、ユーザーから文字列 str が与えられます。求められているのは、その文字列の中で出現回数が奇数回となっている文字だけを取り出して表示することです。 この問題を解くには、まず文字列内の各文字の出現頻度（合計出現回数）を調べます。そのうえで、頻度が奇数である文字のみを出力すればよいのです。 具体例を使って、この問題をより深く理解していきましょう。 入力 : adatesaas 出力 : dte 解説 − 各文字とその出現回数の対応は以下の表の通りです。 a4d1t1e1s2 出現回数が奇数となっているのは、d、t、e の3文字です。これらを、文字列中で実際に出現した順序のま

この問題では、小文字のみで構成された文字列が与えられ、文字列中に出現する各文字の出現回数を求める必要があります。以下の例で、問題をより詳しく説明します。入力 : jskdk 出力 : j 1 s 1 k 2 d 1説明 − この文字列では、文字 j、s、d はそれぞれ1回、k は2回出現します。したがって、上記のような結果が出力されます。それでは、この問題を解くためのロジックを考えてみましょう。前述のとおり、文字列内の各文字の出現頻度を求める必要があります。一つの論理的なアプローチとして、文字列を走査しながら各文字の出現回数を数えて配列に格納し、その後、文字とその出現頻度を出力する方法がありま

この記事では、ある年を入力として受け取り、その年のカレンダーをコンソールに出力するC++プログラムを紹介します。 年間カレンダーには、1月から12月までのすべての月と、各月の日付が表示されます。ここでは、指定した年のカレンダー全体を出力するプログラムを段階的に作成していきます。 カレンダーを生成するためには、主に次の2つの計算が必要になります。 1. 特定の月の日数を求める まず、各月が何日あるかを正しく把握する必要があります。 31日の月： 1月、3月、5月、7月、8月、10月、12月 30日の月： 4月、6月、9月、11月 2月： 平年は28日、うるう年は29日 うるう年の判定は、「

問題概要この問題では、括弧を含む式が与えられ、その括弧の番号列を出力することが求められます。まず具体例を見て、問題の内容をしっかり理解しましょう。例：入力 : ((()())())出力 : 1233442551解説 ― この式には5組の括弧ペアが含まれており、それぞれの括弧が出現した順序に従って番号を出力しています。問題の内容が把握できたところで、次に解決策を考えていきましょう。解法のアプローチこの問題を効率的に解くには、スタックというデータ構造を活用します。具体的には、左括弧「(」の個数を数えるための変数を1つ用意し、スタックで対応する右括弧「)」の情報を管理します。左括弧が出現するたびに通

この問題では、二分探索木（BST）と2つの値 k1・k2 が与えられ、木の中に存在する k1 から k2 の範囲内にあるすべての値を出力することが求められます。つまり、k1 以上かつ k2 以下の値をすべて、昇順（値が大きくなる順）で出力します。二分探索木（BST）とは二分探索木とは、次の3つの性質を満たす木構造のことです。左部分木に含まれるノードは、すべて親ノードの値より小さい値を持つ右部分木に含まれるノードは、すべて親ノードの値より大きい値を持つ各部分木もまた二分探索木である必要がある。また、重複するノードは存在しない具体例理解を深めるために、具体的な例を見てみましょう。入力：k1 = 1

この問題では、0からnまでの各整数とnをビット単位AND演算（&）したときに得られる値をすべて求め、重複なく出力します。これらの値は、nの2進表現における「1」のビットを組み合わせた部分集合（部分マスク）に相当します。問題の例具体例を見ながら概念を理解しましょう。入力 : N = 4 出力 : 0 4 説明 : 0 & 4 = 0 1 & 4 = 0 2 & 4 = 0 3 & 4 = 0 4 & 4 = 4 入力 : N = 6 出力 : 0, 2, 4, 6N = 6の場合、6は2進数で「110」と表されます。0から6までの各数値と6のANDを取る

この問題では、二分木が与えられ、各レベルに存在するすべてのノードを値の順序(ソート済み)で出力することが求められます。 まず、具体例を見ながら概念を理解していきましょう。 入力 − 出力 − 20 6 15 2 17 32 78 解決のアプローチ この問題を解くには、木の各レベルごとにノードの値をソートした状態で出力する必要があります。そのために、以下のデータ構造を利用します。 queue(キュー):幅優先探索(BFS)のようにノードをたどるために使用 priority_queue × 2つ:1つは「現在のレベル」の値を昇順で保持し、もう1つは「次のレベル」の値を一時的に保持するために使用

はじめに各行が昇順にソートされた行列（2次元配列）が与えられたとします。このとき、すべての行に共通して存在する要素を見つける関数を作成する必要があります。例として、次のような行列を考えてみましょう。この行列の場合、すべての行に共通して現れる要素は 5 となります。解決アプローチ：ハッシュテーブルを活用この問題を解くには、ハッシュテーブル（連想配列）を利用したアプローチが有効です。この手法の大きな利点は、行がソートされていない場合でも同様に適用できるという点です。アルゴリズムの手順以下の手順に従って処理を進めます。ステップ1： まず、1行目の各行の要素（重複を除く）をキーとしてハッシュテーブルを

この記事では、与えられた二分木（バイナリツリー）を2次元平面上に整形して出力する方法について解説します。二分木とは、すべてのノードが最大2つの子ノードを持つ特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。出力イメージまず、具体例を見ながら内容を理解していきましょう。      7    45      1    3  &nbs

はじめに 本記事では、「1つの文字列を別の文字列にコピーすることなく、文字列の配列をソートされた順序で出力する」というC++の問題を解説します。この問題では、ソート処理中に文字列を別の場所へコピーすることが禁止されています。 問題の確認 まず、具体例を見て概念を理解しましょう。 Input : {Delhi, Hyderabad, Indore, Mumbai, Banglore} Output : Banglore, Delhi, Hyderabad, Indore, Mumbai 解説： 文字列は辞書順（レキシコグラフィック順）に並べ替えられます。そのため、「B」で始まる「Banglo

問題の概要文字列Aが与えられたとき、Aを部分列として含む回文文字列Bを見つけることを考えます。ここで部分列とは、元の文字列から一部の文字を削除しても、残りの文字の相対的な順序を変えずに作られる文字列のことです。例えば、文字列「cotst」に対して生成される文字列は「contest」です。また、入力としてA = ab を選んだ場合、生成される文字列は「abba」となり、これは回文になっています。解決のアプローチこの問題の解法は非常にシンプルです。文字列Aを反転し、その反転した文字列をAの後ろに連結してBを構成します。つまり、次の式で表されます。B = A + reverse(A)この方法が常に正

問題の概要 この記事では、整数の配列が与えられたときに、配列内の他の少なくとも1つの要素で割り切れる数だけを出力する方法を解説します。 まず、具体的な例で問題を確認しましょう。 入力 : 3 12 16 21 出力 : 12 21 解説: 3は配列内で最小の要素のため、他の要素で割り切れる可能性がありません。12は3で割り切れ、16は3で割り切れませんが、21は3で割り切れます。したがって、3と16を除外し、12と21のみを出力します。 単純なアプローチとその課題 最も直感的な方法は、各要素について配列内の他のすべての要素で割り切れるかどうかを順番に確認することです。しかし、この総当たり方式は

ここでは、整数値を持つ n × n の行列 mat が与えられた場合を考えます。すべてのインデックスの組み合わせの中から、mat(c, d) - mat(a, b) の最大値を見つけることが目的です。ただし、条件として c > a かつ d > b を満たす必要があります。 例えば、次のような行列があったとしましょう。 12-1-4-20-8-342138613-4-117-60-410-51 この場合の出力は 18 となります。mat[4][2] - mat[1][0] = 10 - (-8) の組み合わせが最大の差を生むためです。 解法のアプローチ この問題を効率的に解くため

この問題では、数値の配列が与えられ、その要素を昇順と降順を交互に切り替えながら出力する必要があります。出力の順序は、最初の2要素を昇順、次の3要素を降順、さらにその次の4要素を昇順というように、グループごとに昇順・降順が交互に切り替わるルールに従います。具体例を見ながら、問題をより深く理解しましょう。入力 : {1, 4, 0, 2, 7, 9, 3} 出力 : 0 1 9 7 4 2 3解説 − 配列を昇順にソートすると「0 1 2 3 4 7 9」となります。最初の2要素は「0 1」、次に末尾から3要素は「9 7 4」、さらに次の4要素として残りの「2 3」を出力します(残りが2要素し

n個の数値からなる配列があるとします。この中から「2つの要素の和が、もう1つの要素と等しくなる」ような3つの数値(トリプレット)を見つける必要があります。例えば、配列が [5, 32, 1, 7, 10, 50, 19, 21, 2] の場合、出力は 21, 2, 19 となります(2 + 19 = 21)。該当する組み合わせが存在しない場合は、その旨のメッセージを表示します。アルゴリズムの考え方この問題を解決するには、以下の手順に従います。まず、与えられた配列を昇順にソートします。次に、配列の末尾(最大の要素)から順に要素を固定し、その要素と等しくなるような和を持つ2つの数値を探索します。2

はじめに本記事では、二分木（バイナリツリー）が与えられたとき、指定したノードの祖先（ancestor）となるすべてのノードを出力する方法を解説します。二分木とは、各ノードが最大2つの子ノードを持つ特殊な木構造です。したがって、すべてのノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。以下は二分木の一例です。祖先ノードとは二分木におけるあるノードの祖先とは、そのノードより上位の階層に位置し、根からそのノードへの経路上にあるノードを指します。例として、次の図を見てみましょう。この二分木において、値が 3 のノードの祖先は 8 とその上位のノードです。アルゴリズムの考え方この問

問題の概要 星（*）とアルファベットが混在した行列 M が与えられたとします。この中から、周囲に最も多くの星を持つアルファベットを見つける必要があります。例えば、次のような行列を考えてみましょう。 この例では、A と C の周囲にはそれぞれ7つの星があり、これが最大値となっています。ただし、複数の文字で星の数が同じ場合は、辞書順（レキシコグラフィカル順）でより小さい文字が出力されます。A は C よりも辞書順で小さいため、この場合の出力は「A」になります。 解決アプローチ この問題の解き方は非常にシンプルです。以下の手順で処理を進めます。 行列全体を走査し、アルファベットのセルを見つけま

問題の概要この問題では、二分木が与えられ、指定したノードの祖先（ancestor）となるノードをすべて出力することが求められます。二分木とは、各ノードが最大2つの子ノードを持つ特殊な木構造のことです。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。祖先ノードとは二分木におけるあるノードの祖先とは、そのノードより上位のレベルに位置するノードのことを指します。例として、次のような二分木を考えてみましょう。この二分木において、値が 17 のノードの祖先は、27 → 25 → 15 となります。解法のアプローチこの問題を解くには、ルートノードからターゲットノードへ向か