Gibt in einer erweiterten Matrix das vorherige Element in C++ zurück

Besprechen Sie ein Problem anhand der erweiterten Matrix. Eine erweiterte Matrix ist eine Matrix, deren Größe um einen bestimmten Faktor zunimmt.

Hier haben wir eine Zeichenmatrix, deren Größe um ein Vielfaches von 2 erweitert wird, d. h. wenn die Größe der ursprünglichen Matrix N * N beträgt, dann beträgt die Größe der erweiterten Matrix 2N * 2N. Wir erhalten eine Zeichenfolge, die sich bei (i, j) befindet, und wir müssen die Zeichenfolge zurückgeben, die sich bei (i, (j - N - 1)%N) befindet.

Lassen Sie uns das verstehen, indem wir einige anfängliche Erweiterungsmatrizen visualisieren.

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 ]

Dies sind zwei anfängliche Erweiterungsmatrizen. Angenommen, wir erhalten eine Zeichenfolge „bcc“, dann müssen wir die gerade verbleibende Sequenz zurückgeben, nämlich „add“. Nehmen wir außerdem an, dass die Matrix zyklisch ist, d. h. wenn die gegebene Sequenz bei (i, 0) liegt, dann wird die Sequenz bei (i, N-1) zurückgegeben.

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

Möglichkeiten, die Lösung zu finden

Denken Sie zuerst über das Problem nach , die einzige Lösung, die mir in den Sinn kommt. Die Lösung besteht darin, eine erweiterte Matrix zu finden, die die angegebene Sequenz enthält, aber nicht sehr komplex aussieht. Wir müssen zuerst die Matrix bilden und dann nach der Sequenz suchen.

Effizienter Ansatz

Nachdem wir uns einige zunächst erweiterte Matrizen angesehen hatten, entdeckten wir ein Muster, durch das wir das vorherige Element sehen konnten. Das heißt,

• durchläuft die Zeichenfolge ab dem letzten Index.

• Wenn das Indexelement „b“ oder „d“ ist, ändern Sie es in „a“ oder „c“ und beenden Sie das Durchlaufen des Arrays.

• Wenn das Indexelement „a“ oder „c“ ist, ändern Sie es in „b“ oder „d“, gehen Sie zum nächsten Index und überprüfen Sie ihn.

Beispiel

C++-Code der oben genannten Methode

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

Ausgabe

The previous sequence is: abbcc

Schlussfolgerung

In diesem Artikel haben wir über die erweiterte Zeichenmatrix und deren Bildung gesprochen. Wir haben auch die Suche nach dem vorherigen Element in einer erweiterten Matrix besprochen. Wir haben dieses Problem gelöst, indem wir die durch die erweiterte Zeichenmatrix erzeugten Muster verstanden haben.

Wir haben auch C++-Code zur Lösung dieses Problems besprochen, den wir in jeder Programmiersprache wie C, Java, Python usw. schreiben können. Wir hoffen, dass Sie dieses Tutorial hilfreich finden.

Das obige ist der detaillierte Inhalt vonGibt in einer erweiterten Matrix das vorherige Element in C++ zurück. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!