拡張行列では、C++ で前の要素を返します。

拡張マトリックスに基づいて問題について話し合います。拡張行列とは、サイズが何らかの係数によって増加する行列です。

ここでは、サイズが 2 の倍数で拡張された文字行列があります。つまり、元の行列のサイズが N * N の場合、拡張された行列のサイズは 2N * 2N になります。 。 (i, j) にある文字のシーケンスが与えられており、(i, (j - N - 1)%N) にある文字のシーケンスを返す必要があります。

いくつかの初期展開行列を視覚化して理解しましょう。

Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]

Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.

Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]

これらは 2 つの初期展開行列です。文字シーケンス「bcc」を取得すると仮定すると、そのすぐ左のシーケンス「add」を返す必要があります。また、行列が巡回であると仮定します。つまり、指定されたシーケンスが (i, 0) にある場合、(i, N-1) にあるシーケンスを返します。

Input: abb
Output: aba
Explanation: The sequence just left to abb is aba in the 8X8 matrix.

Input: aadc
Output: aacd

Input: abbcd
Output: abbcc

解を見つける方法

最初に問題について考えると、思い浮かぶ唯一の解決策は、指定されたシーケンスを含むがそれほど複雑に見えない拡張行列を見つけることです。最初に行列を形成してから、シーケンスを検索する必要があります。

効率的な方法

最初に展開された行列をいくつか調べた後、前の要素を確認できるパターンを発見しました。つまり、

• は、最後のインデックスから開始して文字シーケンスを走査します。

• インデックス要素が 'b' または 'd' の場合、それを 'a' または 'c' に変更し、配列の走査を停止します。

• インデックス要素が 'a' または 'c' の場合、 ' それを 'b' または 'd' に変更し、次のインデックスに移動して確認します。

#例

メソッド上の C コード

#include <bits/stdc++.h>
using namespace std;
int main (){
   string seq = "abbcd";
   int n = seq.length ();
   // traverse through the string from last.
   for (int i = n; i >= 0; i--){
      // if the element is b or d, change them and stop traversing.
      if (seq[i] == &#39;b&#39;){
      seq[i] = &#39;a&#39;;
      break;
   }
   if (seq[i] == &#39;d&#39;){
      seq[i] = &#39;c&#39;;
      break;
   }
   // if an element is b or d, change them and move to the next element.
   if (seq[i] == &#39;a&#39;)
      seq[i] = &#39;b&#39;;
   else if (seq[i] == &#39;c&#39;)
      seq[i] = &#39;d&#39;;
   }
   cout << "The Previous sequence is: " << seq;
   return 0;
}

出力

The previous sequence is: abbcc

結論

この記事では、拡張文字マトリックスとその形成方法について説明しました。拡張行列内の前の要素を見つけることについても説明しました。私たちは、拡張文字マトリックスによって作成されるパターンを理解することで、この問題を解決しました。

この問題を解決するための C コードについても説明しました。このコードは、C、Java、Python などの任意のプログラミング言語で作成できます。このチュートリアルがお役に立てば幸いです。

以上が拡張行列では、C++ で前の要素を返します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。