# 返回擴展矩陣中的前一個元素 > 原文： [https://www.geeksforgeeks.org/return-previous-element-in-an-expanding-matrix/](https://www.geeksforgeeks.org/return-previous-element-in-an-expanding-matrix/) 我們有一個正方形矩陣，其大小連續擴大 2 倍。給定任意時間點在位置（i，j）處存在于矩陣中的序列，我們需要返回在位置（i，（j + N -1）% N），其中 N 是矩陣的大小。 當我們說矩陣正在擴展時，擴展矩陣是通過將原始 2 x 2 矩陣的每個元素與當前 N x N 矩陣本身相乘而形成的。 擴展矩陣的尺寸為 2N x 2N。 ``` For Instance, consider below 2x2 matrix, [a b] [c d] Expanding it will result in a 4x4 matrix as follows: ax[a b] bx[a b] [aa ab ba bb] [c d] [c d] [ac ad bc bd] --> [ca cb da db] cx[a b] dx[a b] [cc cd dc dd] [c d] [c d] Expanding it again results in an 8x8 matrix as follows, and so on. ax[aa ab ba bb] bx[aa ab ba bb] [aaa aab aba abb baa bab bba bbb] [ac ad bc bd] [ac ad bc bd] [aac aad abc abd bac bad bbc bbd] [ca cb da db] [ca cb da db] [aca acb ada adb bca bcb bda bdb] [cc cd dc dd] [cc cd dc dd] [acc acd adc add bcc bcd bdc bdd] --> [caa cab cba cbb daa dab dba dbb] cx[aa ab ba bb] dx[aa ab ba bb] [cac cad cbc cbd dac dad dbc dbd] [ac ad bc bd] [ac ad bc bd] [cca ccb cda cdb dca dcb dda ddb] [ca cb da db] [ca cb da db] [ccc ccd cdc cdd dcc dcd ddc ddd] [cc cd dc dd] [cc cd dc dd] ``` 基本上，對于給定的序列，我們需要找出剛剩下的序列。 可以假設矩陣是圓形的，即位置（i，0）處的序列應返回位置（i，N-1）處的序列 **示例**： ``` Input: str = dda Output: dcb Input: str = cca Output: ddb Input: str = aacbddc Output: aacbdcd ``` **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 如果我們仔細分析，我們可以在此處看到一個模式。 **算法**： 我們從最右邊的位置開始掃描字符串，并對每個字符執行以下操作– 1.如果當前字符是“ b”或“ d”，則分別更改為“ a”或“ c”并返回字符串。 2.如果當前字符是“ a”或“ c”，則分別將其更改為“ b”或“ d”，然后移至左側的下一個字符。 對左下一個字符重復步驟 1。 ## C++ ```cpp // C++ Program to return previous element in an expanding // matrix. #include <bits/stdc++.h> using namespace std; // Returns left of str in an expanding matrix of // a, b, c, and d. string findLeft(string str) { ????int n = str.length(); ????// Start from rightmost position ????while (n--) ????{ ????????// If the current character is ‘b’ or ‘d’, ????????// change to ‘a’ or ‘c’ respectively and ????????// break the loop ????????if (str[n] == 'd') ????????{ ????????????str[n] = 'c'; ????????????break; ????????} ????????if (str[n] == 'b') ????????{ ????????????str[n] = 'a'; ????????????break; ????????} ????????// If the current character is ‘a’ or ‘c’, ????????// change it to ‘b’ or ‘d’ respectively ????????if (str[n] == 'a') ????????????str[n] = 'b'; ????????else if (str[n] == 'c') ????????????str[n] = 'd'; ????} ????return str; } // driver program to test above method int main() { ????string str = "aacbddc"; ????cout << "Left of " << str << " is " ?????????<< findLeft(str); ???return 0; } ``` ## Java ```java // Java program to return previous element // in an expanding matrix import java.io.*; class GFG? { ????// Returns left of str in an expanding matrix? ????// of a, b, c? and d. ????static StringBuilder findLeft(StringBuilder str) ????{ ????????int n = str.length(); ????????// Start from rightmost position ????????while (n > 0) ????????{ ????????????n--; ????????????// If the current character is b or d, ????????????// change to a or c respectively and ????????????// break the loop ????????????if (str.charAt(n) == 'd') ????????????{ ????????????????str.setCharAt(n,'c'); ????????????????break; ????????????} ????????????if (str.charAt(n) == 'b') ????????????{ ????????????????str.setCharAt(n,'a'); ????????????????break; ????????????} ????????????// If the current character is a or c, ????????????// change it to b or d respectively ????????????if (str.charAt(n) == 'a') ????????????????str.setCharAt(n,'b'); ????????????else if (str.charAt(n) == 'c') ????????????????str.setCharAt(n,'d'); ????????} ????????return str; ????} ????// driver program to test above method ????public static void main (String[] args)? ????{ ????????StringBuilder str = new StringBuilder("aacbddc"); ????????System.out.print("Left of " + str + " is " +? ????????????????????????????????????findLeft(str)); ????} } // This code is contributed by Prakriti Gupta ``` ## Python3 ```py # Python3 Program to return previous element? # in an expanding matrix. # Returns left of str in an? # expanding matrix of a, b, c, and d. def findLeft(str): ????n = len(str) - 1; ????# Start from rightmost position ????while (n > 0): ????????# If the current character is ‘b’ or ‘d’, ????????# change to ‘a’ or ‘c’ respectively and ????????# break the loop ????????if (str[n] == 'd'): ????????????str = str[0:n] + 'c' + str[n + 1:]; ????????????break; ????????if (str[n] == 'b'): ????????????str = str[0:n] + 'a' + str[n + 1:]; ????????????break; ????????# If the current character is ‘a’ or ‘c’, ????????# change it to ‘b’ or ‘d’ respectively ????????if (str[n] == 'a'): ????????????str = str[0:n] + 'b' + str[n + 1:]; ????????elif (str[n] == 'c'): ????????????str = str[0:n] + 'd' + str[n + 1:]; ????????n-=1; ????return str; # Driver Code if __name__ == '__main__': ????str = "aacbddc"; ????print("Left of", str, "is", findLeft(str)); # This code is contributed by PrinciRaj1992 ``` ## C# ```cs using System; using System.Text; // C# program to return previous element? // in an expanding matrix? public class GFG { ????// Returns left of str in an expanding matrix?? ????// of a, b, c? and d.? ????public static StringBuilder findLeft(StringBuilder str) ????{ ????????int n = str.Length; ????????// Start from rightmost position? ????????while (n > 0) ????????{ ????????????n--; ????????????// If the current character is b or d,? ????????????// change to a or c respectively and? ????????????// break the loop? ????????????if (str[n] == 'd') ????????????{ ????????????????str[n] = 'c'; ????????????????break; ????????????} ????????????if (str[n] == 'b') ????????????{ ????????????????str[n] = 'a'; ????????????????break; ????????????} ????????????// If the current character is a or c,? ????????????// change it to b or d respectively? ????????????if (str[n] == 'a') ????????????{ ????????????????str[n] = 'b'; ????????????} ????????????else if (str[n] == 'c') ????????????{ ????????????????str[n] = 'd'; ????????????} ????????} ????????return str; ????} ????// driver program to test above method? ????public static void Main(string[] args) ????{ ????????StringBuilder str = new StringBuilder("aacbddc"); ????????Console.Write("Left of " + str + " is " + findLeft(str)); ????} } // This code is contributed by Shrikant13 ``` ## PHP ```php <?php? // PHP program to return previous element in an expanding // matrix. // Returns left of str in an expanding matrix of // a, b, c? and d. function findLeft($str) { ????$n = strlen($str); ????// Start from rightmost position ????while ($n--) ????{ ????????// If the current character is ‘b’ or ‘d’, ????????// change to ‘a’ or ‘c’ respectively and ????????// break the loop ????????if ($str[$n] == 'd') ????????{ ????????????$str[$n] = 'c'; ????????????break; ????????} ????????if ($str[$n] == 'b') ????????{ ????????????$str[$n] = 'a'; ????????????break; ????????} ????????// If the current character is ‘a’ or ‘c’, ????????// change it to ‘b’ or ‘d’ respectively ????????if ($str[$n] == 'a') ????????????$str[$n] = 'b'; ????????else if ($str[$n] == 'c') ????????????$str[$n] = 'd'; ????} ????return $str; } // Driver Code $str = "aacbddc"; echo "Left of " . $str . " is " ?????????. findLeft($str); return 0; ?> ``` **輸出**： ``` Left of aacbddc is aacbdcd ```