C++

問題概要整数型の配列 arr が与えられたとします。ここで、(0 <= i < j <= k < N) を満たす3つのインデックス i、j、k を選ぶことを考えます(N は配列のサイズです)。このとき、a と b の値はそれぞれ次のように定義されます。a = arr[i] XOR arr[i + 1] XOR ... XOR arr[j - 1]b = arr[j] XOR arr[j + 1] XOR ... XOR arr[k]この問題の目的は、a と b が等しくなるようなトリプレット (i, j, k) の総数を求めることです。例として、入力が [2,3,1,6

問題概要 n個の頂点からなる無向木を考えます。頂点には0からn-1までの番号が付けられており、いくつかの頂点にはリンゴが置かれています。木の1つの辺を移動するのに1秒かかるとき、頂点0から出発してすべてのリンゴを集め、再び頂点0に戻るまでに必要な最小時間（秒）を求めてください。 無向木の辺は配列 edges として与えられ、edges[i] = [from_i, to_i] は頂点 from_i と頂点 to_i を結ぶ辺が存在することを表します。さらに、hasApple というブール値の配列も与えられ、hasApple[i] = true の場合は頂点 i にリンゴが存在し、false の

整数 n が与えられたとき、0より大きく1より小さい範囲に存在するすべての簡約済み（既約）分数を、分母が n 以下という条件で求めてリストとして返すことを考えます。分数の出力順序は問われません。例えば、入力が n = 4 の場合、出力は [1/2, 1/3, 1/4, 2/3, 3/4] となります。2/4 は 1/2 に約分できるため、簡約分数としては含まれません。解法のアプローチこの問題は以下の手順で解くことができます。結果を格納する配列 ret を定義します。i を分母として、i = 2 から n まで繰り返します。j を分子として、j = 1 から i - 1 まで繰り返します。c :

問題の概要二分木が与えられたとき、木の中のノードXは、ルートからXへの経路上に、Xより大きい値を持つノードが存在しない場合に「良いノード(good node)」と定義されます。この記事では、二分木に含まれる良いノードの数を求める方法を解説します。例えば、次のような二分木が入力として与えられたとします。この場合、出力は 4 となります。色付きで示されたノードが「良いノード」に該当します。解決アプローチこの問題は、深さ優先探索(DFS)を使うことで効率的に解くことができます。具体的な手順は以下の通りです。DFS関数の定義dfs() 関数を定義します。引数としてノード(node)と現在までの最大値(

本記事では、C++を用いて文中の単語を長さの昇順に並べ替えるアルゴリズムを解説します。 問題の概要 ある文字列が与えられ、この文字列は「文（センテンス）」と呼ばれるものとします。文は次の形式を満たしています。 先頭の文字は必ず大文字である。 各単語は1つの半角スペースで区切られている。 求められるのは、文中のすべての単語を長さが短い順（昇順）に並べ替えた新しい文を作ることです。ここで重要なルールとして、同じ長さの単語がある場合は、元の文中での出現順序を維持する必要があります。これはいわゆる「安定なソート（stable sort）」の考え方です。 最終的に、これらのルールを適用した結果の文字

問題概要 favoriteCompanies という配列があるとします。ここで favoriteCompanies[i] は、i 番目の人のお気に入り企業のリストを表します。この問題では、自分のお気に入り企業リストが他のどのリストの部分集合にもなっていない人を見つけ、そのインデックスをすべて返します。 たとえば、入力が favoriteCompanies = [[TCS, google, facebook], [google, microsoft], [google, facebook], [google], [amazon]] の場合、出力は [0, 1, 4] になります。その理由は次のと

文字列 s と整数 k が与えられたとき、長さがちょうど k である s の部分文字列の中に、母音（a, e, i, o, u）が最大でいくつ含まれるかを求める問題です。例えば、入力が s = abciiidef、k = 3 の場合、出力は 3 になります。これは、部分文字列 iii に母音が3つ含まれているためです。解法アプローチ：スライディングウィンドウ（尺取り法）この問題は「スライディングウィンドウ」と呼ばれる手法を使うことで、文字列全体を一度走査するだけで効率的に解くことができます。各ステップでウィンドウの右端に新しい文字を追加し、左端から古い文字を取り除くことで、毎回母音を数え直す無

問題の概要ノードの値が 1 から 9 の数字である二分木を考えます。根ノードから葉ノードへ向かうあるパスについて、パスに含まれるノード値を並べ替えた結果の少なくとも1つが回文になるとき、そのパスを「擬似回文パス（pseudo-palindromic path）」と呼びます。この問題では、根から葉への擬似回文パスが全部で何本あるかを求めます。具体例例として、次のような二分木が与えられたとします。このとき出力は 2 になります。根ノードから葉ノードへの経路は3本存在します。赤のパスは [2,3,3]、緑のパスは [2,1,1]、そして残りのパスは [2,3,1] です。このうち擬似回文パスになって

二進文字列 s と整数 k が与えられたとき、長さ k のすべてのバイナリコード（合計 2^k 個）が s の部分文字列として含まれているかどうかを判定します。すべて含まれていれば true を、1つでも欠けていれば false を返します。 問題の例 たとえば、入力が S = 00110110、k = 2 の場合、出力は true になります。長さ 2 のバイナリコードは「00」「01」「10」「11」の 4 種類あり、それぞれインデックス 0、1、3、2 の位置に存在するためです。 解法のアプローチ この問題は、スライディングウィンドウの考え方とハッシュセットを組み合わせることで効率的に解

問題概要受講できるコースが全部で n 個あり、各コースには 0 から n-1 までの番号が割り当てられています。一部のコースには直接の前提条件が存在します。たとえば、コース 0 を受講する前にコース 1 を受講しておく必要がある場合、この関係はペア [1,0] として表現されます。ここで、コース数 n、直接の前提条件ペアのリスト、そしてクエリペアのリストが与えられます。各クエリ queries[i] に対して、「コース queries[i][0] はコース queries[i][1] の前提条件であるか」を判定してください。最終的に、すべてのクエリへの回答をブーリアン値のリストとして返します。

問題概要 高さ h、幅 w の長方形のケーキがあるとします。さらに、整数型の配列 horizontalCuts と verticalCuts が与えられます。horizontalCuts[i] はケーキの上端から i 番目の水平カット位置までの距離を、verticalCuts[j] は左端から j 番目の垂直カット位置までの距離を表します。 これらの配列で指定されたすべての位置でカットを実行した後、切り分けられたピースの中で最大の面積を求めるのが目的です。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返してください。 入力例 たとえば、h = 5、w = 4、h

問題概要0 から n-1 までの番号が振られた n 個の都市があるとします。さらに、n-1 本の道路が存在し、任意の2つの都市間を移動する経路はただ一つしかありません。交通省は道路が非常に狭いため、すべての道路を一方向のみ通行可能とする一方通行化を決定しました。道路は配列 connections で表現され、connections[i] = [a, b] は「都市 a から 都市 b へ向かう一方向の道路」を意味します。ここで、首都（都市 0）で大規模なイベントが開催され、多くの人々が首都を目指して移動することになりました。そこで、すべての都市から都市 0 に到達できるように、一部の道路の向き

問題の概要数値の配列 arr と整数 k が与えられているとします。ここで、値 arr[i] が値 arr[j] より「強い(strong)」とは、次の条件を満たすことを指します。|arr[i] − m| > |arr[j] − m|(m は配列の中央値)また、|arr[i] − m| と |arr[j] − m| が等しい場合は、arr[i] > arr[j] であるときに arr[i] の方が強いとみなされます。このルールに基づき、配列の中から最も強い k 個の値をリストとして返すのが本問題の目的です。具体例入力が arr = [1,2,3,4,5]、k = 2 の場合を考えて

問題概要 同義語ペアのリスト synonyms と1つの文 text が与えられます。文中の各単語を、つながりのあるすべての同義語で置き換えた結果として考えられる文をすべて求め、辞書順にソートして返すのが目的です。 たとえば、入力が次のとおりだったとします。 synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]] text = "I am happy today but was sad ye

すべての右側のノードが「兄弟を持つ葉ノード」であるか「空」であるような二分木が与えられます。この木を上下逆さまに反転し、元の右側のノードが左の葉ノードになるような新しい木へと変換します。最後に、新しい木のルートノードを返す必要があります。 問題の例 入力が [1,2,3,4,5] の場合、 出力は [4,5,2,#,#,3,1] という構造を持つ二分木のルートになります。 解法のアプローチ この問題は、再帰的な処理によって解くことができます。木を走査しながら各ノードの左右のポインタを付け替えていく手法を用います。以下の手順で進めます。 solve() 関数を定義します。この関数は nod

文字列 s が与えられたとき、異なる文字が最大2種類まで含まれる最長の部分文字列 t の長さを求める問題を考えてみましょう。例えば、入力が eceba の場合、出力は 3 になります。これは条件を満たす最長の部分文字列が ece であり、その長さが 3 だからです。この問題はスライディングウィンドウ（尺取り法）を使うことで効率的に解けます。各文字の出現回数をハッシュマップで管理し、異なる文字の種類数が2を超えたら左端から縮めていくというアプローチです。解法の手順関数 lengthOfLongestSubstringKDistinct() を定義します。引数として文字列 s と許容する異なる文字

問題の概要2つの文字列 s と t が与えられたとき、両者が「1回の編集距離(ワン・エディット・ディスタンス)」の関係にあるかどうかを判定します。ここでいう1回の編集距離とは、次の3種類の操作をちょうど1回だけ適用することで、一方の文字列からもう一方の文字列を作れることを意味します。s に1文字を挿入して t を得るs から1文字を削除して t を得るs の1文字を別の文字に置き換えて t を得るたとえば、入力が s = ab、t = acb の場合を見てみましょう。ab の2文字目に c を挿入すれば acb になるため、このケースの出力は True(真)となります。解法のアプローチこの問題

問題の概要 ソート済みの整数配列 nums が与えられ、その要素は閉区間 [lower, upper] の範囲内に収まっているものとします。このとき、指定された範囲の中で配列に含まれていない「欠落している範囲」をすべて求めるのが本問題です。 たとえば、nums = [0, 1, 3, 50, 75]、lower = 0、upper = 99 という入力が与えられた場合、出力は [2, 4->49, 51->74, 76->99] となります。 解法のアプローチ この問題は、範囲の下限から上限へと順番に走査しながら、配列の要素と突き合わせていくことで解けます。具体的な手順は以

1つの文字型配列（文字列）が入力として与えられたとき、その文字列を「単語ごと」に反転する問題を考えてみましょう。ここでの反転とは、単語同士の出現順序を逆にする操作を指します。例えば、入力が [t,h,e, ,m,a,n, ,i,s, ,n,i,c,e]（the man is nice）である場合、出力は [n,i,c,e, ,i,s, ,m,a,n, ,t,h,e]（nice is man the）となります。解法のアプローチこの問題は、以下の手順に従って解くことができます。まず、配列 s 全体を反転します。変数 j を 0 で初期化します。n に配列 s のサイズを代入します。i を 0 か

問題の概要 コンストラクタで単語のリストを受け取るクラスを考えます。このクラスには、2つの単語 word1 と word2 を引数に取り、リスト内における両者の最短距離を返すメソッドが備わっています。重要なのは、このメソッドが異なる引数の組み合わせで何度も繰り返し呼び出されるという点です。そのため、呼び出しごとにリスト全体を毎回走査するのではなく、事前処理によって高速な照会を実現する設計が求められます。 たとえば、words = [practice, makes, perfect, skill, makes] というリストがあるとします。 word1 = skill、word2 = pract