合計がC++の指定された値xに等しい2つのBSTからペアをカウントします
入力として2つの二分探索木と変数xが与えられます。目標は、ノードの値の合計がxに等しくなるように、各ツリーからノードのペアを見つけることです。 BST_1からノード1を取得し、BST_2からノード2を取得して、両方のデータ部分を追加します。 sum=xの場合。インクリメントカウント。
例を挙げて理解しましょう。
入力
出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 1
説明 −ペアは(8,6)
入力
出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 2
説明 −ペアは(5,15)と(4,16)
以下のプログラムで使用されているアプローチは次のとおりです
このアプローチでは、反復順序法を使用してBSTをトラバースします。反復順序法を使用して最小ノードから最大ノードにBST1をトラバースし、反復順序法の逆からBST2をトラバースします。両方のBSTの現在のノードの合計を取ります。合計がxインクリメントカウントの場合。 sum> xの場合、BST2の現在のノードの順序の前の先行に移動します。sum
-
整数データ部分と子ノードへの左右のポインタを持つ2つのツリーBST_1とBST_2を取ります。
-
関数insert_node(int data)は、データを含むツリーに新しいノードを挿入し、そのノードへのポインターを返します。
-
inser_node()を使用して両方のBSTを作成し、BST_sum_x(Tree * BST_1、Tree * BST_2、int x)に渡します。
-
関数BST_sum_x(Tree * BST_1、Tree * BST_2、int x)は、両方のツリーのルートノードを取得し、データ部分の合計をxとして持つノードのペアの数を返します。
-
合計xのペアの数の初期カウントを0とします。
-
反復的な順序トラバーサルの場合、2つの変数Tree * stack_top_1、* stack_top_2;
を取ります。 -
2つのスタックを作成しますstackstack_1、stack_2;
-
次に、外側のwhileループを開始します。
-
whileループを使用してBST_1の左端(最小)のノードに移動し、すべてのノードをstack_1にプッシュします
-
whileループを使用してBST_2の右端(最大)のノードに移動し、すべてのノードをstack_2にプッシュします
-
スタックのいずれかが空の場合は、外側のwhileループを解除します。
-
両方のスタックの最上位ノードを取得し、それらのデータパーツを追加して、一時的に保存します。
-
temp(sum)==xの場合、カウントをインクリメントします。ポップ操作を使用して、stack_1とstack_2の両方から最上位の要素を削除します。
-
BST_1 =stack_1->rightおよびBST_2=stack_2-> left(BST_1の次の後続およびBST_2の先行)を設定します
-
temp
-
temp> xの場合、stack_2からtopのみを削除し、BST_1の次の先行タスクに移動します。
-
外側のwhileの終わりに、countには、合計xを持つ両方のBSTのノードを持つペアの数があります。
-
結果としてカウントを返します。
例
#include <bits/stdc++.h> using namespace std; struct Tree{ int data; Tree* left, *right; }; Tree* insert_node(int data){ Tree* newNode = (Tree*)malloc(sizeof(Tree)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; } int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){ int count = 0; Tree* stack_top_1, *stack_top_2; stack<Tree*> stack_1, stack_2; if (BST_1 == NULL || BST_2 == NULL){ return 0; } while (1){ while (BST_1 != NULL){ stack_1.push(BST_1); BST_1 = BST_1->left; } while (BST_2 != NULL){ stack_2.push(BST_2); BST_2 = BST_2->right; } if (stack_1.empty() || stack_2.empty()){ break; } stack_top_1 = stack_1.top(); stack_top_2 = stack_2.top(); int temp = stack_top_1->data + stack_top_2->data; if (temp == x){ count++; stack_1.pop(); stack_2.pop(); BST_1 = stack_top_1->right; BST_2 = stack_top_2->left; } else if (temp < x){ stack_1.pop(); BST_1 = stack_top_1->right; } else{ stack_2.pop(); BST_2 = stack_top_2->left; } } return count; } int main(){ //BST 1 Tree* BST_1 = insert_node(15); BST_1->left = insert_node(10); BST_1->right = insert_node(8); BST_1->left->left = insert_node(12); BST_1->left->right = insert_node(24); BST_1->right->left = insert_node(16); //BST 2 Tree* BST_2 = insert_node(20); BST_2->left = insert_node(16); BST_2->right = insert_node(4); BST_2->left->left = insert_node(18); BST_2->left->right = insert_node(28); BST_2->right->left = insert_node(22); int x = 28; cout<<"Count of pairs from two BSTs whose sum is equal to a given value x ar: "<<BST_sum_x(BST_1, BST_2, x); return 0; }
出力
上記のコードを実行すると、次の出力が生成されます-
Count of pairs from two BSTs whose sum is equal to a given value x ar: 1
-
合計がC++の指定された値xに等しい、ソートされた二重リンクリストのトリプレットをカウントします
整数値を含むソートされた二重リンクリストが与えられます。目標は、積が指定された値xに等しいトリプレットを見つけることです。入力リンクリストが3-4-1-2で、xが6の場合、カウントは1になります(トリプレット(3,1,2)) 例 入力 linked list: [ 3−4−13−5−10−10−0 ] x=20 出力 Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 2 説
-
ソートされた二重リンクリスト内のトリプレットをカウントします。このリストの積は、C++で指定された値xに等しくなります。
整数値を含むソートされた二重リンクリストが与えられます。目標は、積が与えられた値xに等しいトリプレットを見つけることです。入力リンクリストが3−4−1−2で、xが6の場合、カウントは1になります(トリプレット(3,1,2)) 例 入力 linked list: [ 200−4−16−5−10−10−2 ] x=200 出力 Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: