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] == 'b'){
      seq[i] = 'a';
      break;
   }
   if (seq[i] == 'd'){
      seq[i] = 'c';
      break;
   }
   // if an element is b or d, change them and move to the next element.
   if (seq[i] == 'a')
      seq[i] = 'b';
   else if (seq[i] == 'c')
      seq[i] = 'd';
   }
   cout << "The Previous sequence is: " << seq;
   return 0;
}

出力

The previous sequence is: abbcc

結論

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

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