C++ 返回扩展矩阵中的前一个元素
c++server side programmingprogramming
讨论基于扩展矩阵的问题。扩展矩阵是一个大小以某个因子不断增加的矩阵。
这里我们有一个字符矩阵，其大小以 2 的因子扩大，即，如果矩阵的原始大小为 N * N，则扩展矩阵的大小变为 2N * 2N。我们给定一个出现在 (i, j) 处的字符序列，我们需要返回出现在 (i, (j - N - 1)%N) 处的字符序列。
让我们通过可视化一些初始扩展矩阵来理解，
给定矩阵 -> [ a, b ] [ c, d ], 2 X 2 矩阵
与 { 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 ]
扩展矩阵 - > [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 矩阵
再扩展，将其与 { a, b, c, d } 相乘，将形成一个大小为 8X8 的矩阵。
扩展矩阵 - > [ 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 ]
这里有两个初始扩展矩阵；假设我们得到一个字符序列"bcc"，那么我们需要返回它左边的序列，即"add"。此外，假设矩阵是循环的，即，如果给定的序列在 (i, 0)，则返回 (i, N-1) 处的序列。
输入:abb 输出:aba 解释:abb 左边的序列是 8X8 矩阵中的 aba。 输入:aadc 输出:aacd 输入:abbcd 输出: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 ();
// 从最后一个开始遍历字符串。
for (int i = n; i >= 0; i--){
// 如果元素是 b 或 d，则更改它们并停止遍历。
if (seq[i] == 'b'){
seq[i] = 'a';
break;
}
if (seq[i] == 'd'){
seq[i] = 'c';
break;
}
// 如果元素是 b 或 d，则更改它们并移动到下一个元素。
if (seq[i] == 'a')
seq[i] = 'b';
else if (seq[i] == 'c')
seq[i] = 'd';
}
cout << "前一个序列是:<< seq;
return 0;
}
输出
前一个序列是:abbcc
结论
在本文中，我们讨论了扩展字符矩阵及其形成方式。我们还讨论了在扩展矩阵中查找前一个元素的问题。我们通过理解扩展字符矩阵所创建的模式解决了这个问题。
我们还讨论了这个问题的 C++ 代码，我们可以用任何编程语言(如 C、Java、Python 等)编写它。我们希望本教程对您有所帮助。
