資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告