数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 ]这里有两个初始扩展矩阵；所以假设我们给定了一个字符序列“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++ 代码，我们可以用任何编程语言（如 C、Java、Python 等）编写。希望本教程对您有所帮助。
更新于: 2021 年 11 月 26 日
138 次查看
广告