プログラミング

配列の反転は次のことを示します。配列をソートされた形式に変換するために必要な変更の数。配列がすでにソートされている場合は、0回の反転が必要です。別の場合、配列が反転されていると、反転の数が最大になります。 この問題を解決するために、マージソートのアプローチに従って時間の複雑さを軽減し、分割統治アルゴリズムで作成します。 入力と出力 Input: A sequence of numbers. (1, 5, 6, 4, 20). Output: The number of inversions required to arrange the numbers into ascending orde

中央値は中央値です。つまり、中央値は順序付きリストの中央値です。累積パーセンテージ50％に相当します。 2つの配列のサイズは同じである必要があります。最初に、2つの別々の配列の中央値を見つけ、次に別々の中央値を比較して、2つのリストの実際の中央値を取得します。 入力と出力 Input: Two sorted array are given. Array 1: {1, 2, 3, 6, 7} Array 2: {4, 6, 8, 10, 11} Output: The median from two array. Here the median value is 6. Merge the gi

2つの頂点の間に2つの頂点が互いに素なパスが存在する場合、無向グラフは2重連結グラフと呼ばれます。つまり、任意の2つの頂点の間にサイクルがあると言えます。 グラフGは、接続されていて、グラフに関節点や切断点が存在しない場合、2重連結グラフであると言えます。 この問題を解決するために、DFSトラバーサルを使用します。 DFSを使用して、アーティキュレーションポイントが存在するかどうかを確認します。また、すべての頂点がDFSによってアクセスされているかどうかを確認します。アクセスされていない場合は、グラフが接続されていないと言えます。 入力と出力 Input: The adjacency

幅優先探索（BFS）トラバーサルはアルゴリズムであり、特定のグラフのすべてのノードにアクセスするために使用されます。このトラバーサルアルゴリズムでは、1つのノードが選択され、隣接するすべてのノードが1つずつ訪問されます。隣接するすべての頂点を完了すると、さらに移動して別の頂点をチェックし、隣接する頂点を再度チェックします。 このアルゴリズムを実装するには、キューデータ構造を使用する必要があります。隣接するすべての頂点が完了すると、隣接するすべての頂点がキューに追加され、1つのアイテムがキューから削除され、その頂点を再び通過し始めます。 グラフでは、サイクルが発生することがあるため、配

無向グラフのエッジは、それを削除するか、グラフを切断するか、グラフのさまざまなコンポーネントを作成する場合にのみ、ブリッジと呼ばれます。 実際のアプローチでは、ブリッジの接続が切断されたときにネットワーク内にいくつかのブリッジが存在すると、ネットワーク全体が切断される可能性があります。 入力と出力 Input: The adjacency matrix of the graph. 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 Output: Bridges in given graph: Bridge 3--4 Bridge

この問題では、無向グラフが1つ与えられ、グラフがツリーであるかどうかを確認する必要があります。木の基準を確認するだけで簡単に見つけることができます。ツリーにはサイクルが含まれないため、グラフにサイクルがある場合、それはツリーではありません。 別のアプローチを使用して確認できます。グラフが接続されていて、V-1エッジがある場合は、ツリーである可能性があります。ここで、Vはグラフ内の頂点の数です。 入力と出力 Input: The adjacency matrix. 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 Output: The

グラフの接続性を確認するために、トラバーサルアルゴリズムを使用してすべてのノードをトラバースしようとします。トラバーサルの完了後、アクセスされていないノードがある場合、グラフは接続されていません。 有向グラフの場合、接続を確認するためにすべてのノードからトラバースを開始します。 1つのエッジに外側のエッジのみがあり、内側のエッジがない場合があるため、ノードは他の開始ノードからアクセスされません。 この場合、トラバーサルアルゴリズムは再帰的なDFSトラバーサルです。 入力と出力 Input: Adjacency matrix of a graph    0 1 0

深さ優先探索（DFS）は、グラフ走査アルゴリズムです。このアルゴリズムでは、開始頂点が1つ与えられ、隣接する頂点が見つかると、最初にその隣接する頂点に移動し、同じ方法でトラバースを試みます。 可能な限り深さ全体を移動し、その後、バックトラックして前の頂点に到達し、新しいパスを見つけます。 DFSを反復的に実装するには、スタックデータ構造を使用する必要があります。再帰的に実行する場合は、外部スタックは必要ありません。再帰呼び出しの内部スタックで実行できます。 入力と出力 入力：グラフの隣接行列。 ABCDEFA 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 1

この問題では、無向グラフが表示されます。 m色もご用意しております。問題は、グラフの2つの隣接する頂点が同じ色にならないように、m個の異なる色のノードを割り当てることができるかどうかを見つけることです。解決策が存在する場合は、どの頂点にどの色が割り当てられているかを表示します。 頂点0から始めて、色を1つずつ異なるノードに割り当てようとします。ただし、割り当てる前に、色が安全かどうかを確認する必要があります。隣接する頂点に同じ色が含まれているかどうかにかかわらず、色は安全ではありません。 入力と出力 Input: The adjacency matrix of a graph G(V, E)

この問題は、チェス盤でN人の女王の配置を見つけて、女王がボード上の他の女王を攻撃できないようにすることです。 チェスの女王は、水平、垂直、水平、斜めの方法であらゆる方向に攻撃できます。 バイナリマトリックスは、クイーンが他のクイーンを攻撃できないNクイーンの位置を表示するために使用されます。 入力と出力 Input: The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.) Output: The matrix that represents in which

この問題では、サイズN x Nの迷路があります。送信元と宛先の場所は、それぞれ左上のセルと右下のセルです。一部のセルは移動に有効であり、一部のセルはブロックされています。 1匹のラットが開始頂点から目的頂点に移動し始めた場合、パスを完了する方法があることを見つける必要があります。可能であれば、ラットの正しいパスをマークします。 迷路はバイナリマトリックスを使用して与えられ、1でマークされています。これは有効なパスです。それ以外の場合は、ブロックされたセルの場合は0です。 注： ラットは、右または下の2つの方向にしか移動できません。 入力と出力 Input: This algorithm w

crypt-arithmeticの問題では、数字を割り当てるためにいくつかの文字が使用されます。算術演算を正しく実行するために、10個の異なる文字が0から9までの桁値を保持しているように。 2つの単語が与えられ、別の単語がそれらの2つの単語の足し算の答えを与えられます。 例として、「BASE」と「BALL」の2つの単語を言うと、結果は「GAMES」になります。ここで、BASEとBALLをそれらの記号の数字で追加しようとすると、答えGAMESが得られます。 注＆minuns; 最大10文字である必要があります。そうでない場合、解決できません。 入力と出力 Input: This algor

この問題では、いくつかの整数要素を持つ特定のセットがあります。また、別の値も提供されます。合計が指定された合計値と同じである、指定されたセットのサブセットを見つける必要があります。 ここでは、アイテムが無効な場合に有効なサブセットを選択するためにバックトラックアプローチが使用されます。バックトラックして前のサブセットを取得し、別の要素を追加してソリューションを取得します。 入力と出力 Input: This algorithm takes a set of numbers, and a sum value. The Set: {10, 7, 5, 18, 12, 20, 15} The su

このセクションでは、数独と呼ばれる有名な数独の問題を解決しようとします。数独は9x9の数字グリッドであり、グリッド全体も3x3のボックスに分割されています。数独を解決するためのルールがいくつかあります。 この問題を解決するには、1から9までの数字を使用する必要があります。 1行、1列、または1つの3x3ボックスで1桁を繰り返すことはできません。 バックトラッキングアルゴリズムを使用して、数独の問題を解決しようとします。一部のセルが数字で埋められると、それが有効かどうかをチェックします。無効な場合は、他の番号をチェックします。すべての数字が1から9までチェックされ、有効な数字が見つからない

チェスでは、騎士が特別な方法でジャンプできることを私たちは知っています。水平方向に2マス、垂直方向に1マス、または垂直方向に2マス、水平方向に1マス移動できるため、完全な移動は英語の文字「L」のようになります。 この問題では、空のチェス盤があり、騎士は板の任意の場所から開始します。私たちのタスクは、騎士が板のすべての正方形を訪問できるかどうかを確認することです。すべての広場を訪れることができたら、出発点からその場所に到達するために必要な数のジャンプを配置します。 この問題には複数の解決策がありますが、考えられる解決策を1つ見つけようとします。 入力と出力 Input:   T

この問題では、整数のセットが与えられます。2つのサブセットの合計の差ができるだけ小さくなるように、整数を2つの部分に分割する必要があります。したがって、私たちの目標は、ほぼ等しい強さの2つのグループを分割して、綱引きゲームに参加することです。 サブセットnのサイズが偶数の場合はn/2に分割する必要がありますが、nの値が奇数の場合、1つのサブセットのサイズは（n-1）/ 2であり、別のサブセットのサイズは（ n + 1）/2。 入力と出力 Input: A set of different weights. {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4

この問題の入力では、1つの文がスペースなしで与えられ、別の辞書にもいくつかの有効な英語の単語が提供されます。個々の辞書の単語で文を分割するための可能な方法を見つける必要があります。 有効な単語が見つかったら、文字列の左側から検索して有効な単語を検索し、その文字列の次の部分の単語を検索します。 入力と出力 Input: A set of valid words as dictionary, and a string where different words are placed without spaces. Dictionary: {mobile, sam, sung, man, mang

この問題では、1つの正の整数文字列が与えられます。数字のk回を別の場所に交換することにより、値が最大になる順列を見つける必要があります。 この問題を解決するには、数字を選択し、それに続く数字と1つずつ入れ替えて、最大数を見つけます。このプロセスをk回繰り返します。以前の値より大きくない数値が見つかった場合は、古い値に戻って再度確認するため、ここではバックトラッキング戦略が機能しています。 入力と出力 Input: A number of multiple digits. The input is: 129814999 Output: The maximum value from these

有限オートマトンを構築することで、テキストのパターン検索を簡単に実行できます。最初に、有限オートマトンの遷移表を作成するために2D配列を埋める必要があります。テーブルが作成されると、検索手順は簡単です。オートマトンの最初の状態から開始して、最終状態に到達すると、パターンが文字列内にあることを意味します。 有限オートマトン構築の場合、時間計算量はO（M * K）、Mはパターン長、Kはさまざまな文字の数です。メインパターン検索の複雑さはO（n）です。 入力と出力 Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern &l

Kasaiのアルゴリズムは、接尾辞配列から最長共通プレフィックス（LCP）配列を取得するために使用されます。最初に接尾辞配列が見つかります。その後、葛西のアルゴリズムは接尾辞配列リストを取得してLCPを検索します。 LCP配列の場合、O（m log n）を取ります。ここで、mはパターンの長さ、nはテキストの長さです。葛西のアルゴリズム。メイン文字列のパターンを検索するにはO（n）が必要です。 入力と出力 Input: Main String: “banana” Output: Suffix Array : 5 3 1 0 4 2 Common Prefix Array