Thảo luận một vấn đề dựa trên việc mở rộng ma trận. Ma trận mở rộng là ma trận có kích thước liên tục tăng theo một số yếu tố.
Ở đây chúng ta có một ma trận các ký tự có kích thước được mở rộng theo hệ số 2, tức là, nếu kích thước ban đầu của ma trận là N * N, thì kích thước của ma trận mở rộng trở thành 2N * 2N. Chúng ta được cung cấp một chuỗi các ký tự có tại (i, j) và chúng ta cần trả về chuỗi các ký tự có tại (i, (j - N - 1)% N).
Hãy hiểu bằng cách hình dung một số ma trận mở rộng ban đầu,
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 ] Đây là hai ma trận mở rộng ban đầu; vì vậy, giả sử chúng ta được cung cấp một chuỗi ký tự “bcc”, sau đó chúng ta cần trả lại chuỗi ký tự còn lại cho nó, tức là “thêm”. Ngoài ra, ma trận được giả định là hình tròn, tức là nếu dãy đã cho ở (i, 0), thì trả về dãy ở (i, N-1) chẳng hạn
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
Phương pháp tiếp cận để tìm giải pháp
Nhìn vào vấn đề trước tiên và giải pháp duy nhất nghĩ đến là tìm ma trận mở rộng có chứa dãy đã cho nhưng có vẻ không phức tạp lắm. Trước tiên, chúng ta cần tạo ma trận và sau đó tìm kiếm chuỗi.
Phương pháp tiếp cận hiệu quả
Sau khi xem xét một số ma trận được mở rộng ban đầu, chúng tôi tìm thấy một mẫu mà qua đó chúng tôi có thể nhìn thấy phần tử trước đó. Tức là
-
Duyệt qua chuỗi ký tự từ chỉ mục cuối cùng.
-
Nếu phần tử được lập chỉ mục là 'b' hoặc 'd', thì hãy thay đổi nó thành 'a' hoặc 'c' và ngừng duyệt qua mảng.
-
Nếu phần tử được lập chỉ mục là 'a' hoặc 'c', hãy thay đổi nó thành 'b' hoặc 'd' và chuyển sang chỉ mục tiếp theo và kiểm tra nó.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#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;
} Đầu ra
The previous sequence is: abbcc
Kết luận
Trong bài viết này, chúng tôi đã thảo luận về ma trận ký tự mở rộng và cách nó hình thành. Chúng ta cũng đã thảo luận về vấn đề tìm phần tử trước trong ma trận mở rộng. Chúng tôi đã giải quyết vấn đề này bằng cách hiểu mẫu được tạo bằng cách mở rộng ma trận các ký tự.
Chúng tôi cũng đã thảo luận về mã C ++ cho vấn đề này mà chúng tôi có thể viết bằng bất kỳ ngôn ngữ lập trình nào như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.