C++ですべての間隔の交差を検索
{L、R}の形式でN個の間隔があり、Lが開始時刻、Rが終了時刻であるとします。すべての区間の交点を見つける必要があります。交点は、指定されたすべての区間内にある区間です。そのようなものが見つからない場合は、-1を返します。たとえば、間隔が[{1、6}、{2、8}、{3、10}、{5、8}の場合、出力間隔は{5、6}
この問題を解決するために、次の手順に従います-
-
最初の間隔が最後の間隔であると考えてください
-
2番目の間隔から始めて、交差点を検索してみてください。 2つのケースが存在する可能性があります
-
[L1、R1]と[L2、R2]の間に交差は存在せず、R1
になります。 -
[L1、R1]と[L2、R2]の間に交差点はありません。必要な交差点は、{max(L1、L2)、min(R1、R2)}
になります。
-
例
#include<iostream> #include<algorithm> using namespace std; class interval{ public: int left, right; }; void findIntersection(interval intervals[], int N) { int l = intervals[0].left; int r = intervals[0].right; for (int i = 1; i < N; i++) { if (intervals[i].left > r || intervals[i].right < l) { cout << -1; return; } else { l = max(l, intervals[i].left); r = min(r, intervals[i].right); } } cout << "{" << l << ", " << r << "}"; } int main() { interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } }; int N = sizeof(intervals) / sizeof(intervals[0]); findIntersection(intervals, N); }
出力
{5, 6}
-
C++で重複するすべてのサブツリーを検索する
二分木があると考えてください。ツリーに重複するサブツリーがあるかどうかを確認する必要があります。以下のような二分木があるとします- サイズ2の2つの同一のサブツリーがあります。各サブツリーD、BD、およびBEには、両方とも重複するサブツリーがあります。ツリーのシリアル化とハッシュプロセスを使用して、この問題を解決できます。サブツリーの順序どおりの走査をハッシュテーブルに格納します。空のノードには開き括弧と閉じ括弧を挿入します。 例 #include <iostream> #include <unordered_set> #include <unordere
-
二次方程式のすべての根を見つけるためのC++プログラム
二次方程式はax2の形式です。 + bx+c。二次方程式の根は次の式で与えられます- 3つのケースがあります- b 2 <4 * a * c-ルートは本物ではありません。つまり、複雑です b 2 =4 * a * c-根は実数であり、両方の根は同じです。 b 2 4 * a * c-根は実数であり、両方の根は異なります 二次方程式の根を見つけるプログラムは次のとおりです。 例 #include<iostream> #include<cmath> using namespace std; int main() { in