Java程式檢查矩陣的所有行是否彼此迴圈旋轉

---

矩陣由行和列組成，形成一個矩形陣列。迴圈旋轉意味著旋轉陣列的元素，使得一次旋轉將最後一個元素置於第一個位置，其餘元素向右移動。在這個問題中，我們給定了一個n * n的矩陣，我們的任務是檢查矩陣的所有行是否彼此迴圈旋轉，如果是則列印“YES”，否則列印“NO”。

讓我們看看下面的例子及其解釋，以便更好地理解這個問題。

輸入1

mat = [ [ 1, 5, 6],
      [ 5, 6, 1],
      [ 6, 1, 5] ]

輸出1

YES

解釋

假設第一行是一個給定的陣列[1, 5, 6]，現在檢查剩餘的行[5, 6, 1]和[6, 1, 5]

第二行[5, 6, 1]的旋轉為：[1, 5, 6]與第一行匹配。

第三行[6, 1, 5]的旋轉為：[5, 6, 1]，[1, 5, 6]與第一行匹配。

因此，答案是“YES”，因為所有行都是彼此的排列。

輸入2

mat = [ [ 0, 9, 8],
    [ 9, 0, 8] ]

輸出

NO

解釋

假設第一行是一個給定的陣列[0, 9, 8]，現在檢查剩餘的行[9, 0, 8]

第二行[9, 0, 8]的旋轉為：[8, 9, 0]和[0, 8, 9]，它們都不等於給定的陣列。

因此，答案是“NO”，因為所有行都不是彼此的排列。

方法

我們已經看到了上面給定矩陣的示例，讓我們轉向方法

方法1：樸素方法

這種方法的思路是將第一行儲存為字串，然後將該字串與自身組合，以便能夠使用此字串進行子字串搜尋操作來執行。之後遍歷矩陣並檢查剩餘的行，將行轉換為字串，然後檢查該字串是否是第一行字串的子字串（執行子字串操作），返回true，否則返回false。

讓我們看看下面的程式碼，以便更好地理解上述方法。

示例

下面是一個Java程式，用於檢查矩陣的所有行是否彼此迴圈旋轉

public class Rotations{ 
   // Function to check every row are circular rotations to each  other or not
   static boolean circularRotations(int mat[][], int n) {
      // create variable strFirstRow to store first  row's number and initialize it with empty string
      String strFirstRow = "";       
      // Traverse the matrix to store first row as string
      for (int i = 0; i < n; i++) {
         // add the first row numbers to the varible strFirstRow
         strFirstRow = strFirstRow + "-" + String.valueOf(mat[0][i]);
      } 
      // Combining the strFirstRow with strFirstRow to enable the use of this string for substring search operations
      strFirstRow = strFirstRow + strFirstRow; 
      // Traverse the matrix from 1 row to check all remaning rows
      for (int i = 1; i < n; i++) {
         // intialize variable strCurrentRow
         String strCurrentRow = "";
         // Traverse the curret row
         for (int j = 0; j < n; j++) {
            // Add current rows number to the variable strCurrentRow
            strCurrentRow = strCurrentRow + "-" + String.valueOf(mat[i][j]);
         } 
         // if the strCurrentRow is not present in the combining string strFirstRow
         if (strFirstRow.contentEquals(strCurrentRow)) {
            return false;
         }
      }
      // Returns true if every row of given matrix is circular rotations of each other
        return true;
   } 
   public static void main(String[] args)  {
      int n = 4;  // Given size of Matrix
      // Given Matrix
      int mat[][] = {{1, 5, 6, 9},
      {9, 1, 5, 6},
      {6, 9, 1, 5},
      {5, 6, 9, 1}
      };        
      // call function circularRotations to check every row of mat are circular rotations of each other or not
      if (circularRotations(mat, n)) {
            System.out.println("YES" + ", all rows of the matrix are circular rotations of each other");
      } else {
           System.out.println("NO" + ", all rows of the matrix are not circular rotations of each other");
      }
   }
}

輸出

YES, all rows of the matrix are circular rotations of each other

時間和空間複雜度

上述程式碼的時間複雜度為O(N^3)，因為我們遍歷矩陣並使用content equal函式。

上述程式碼的空間複雜度為O(N)，因為我們需要將矩陣的行儲存為字串。

其中N是矩陣的行和列的大小。

結論

在本教程中，我們實現了Java程式來檢查矩陣的所有行是否彼此迴圈旋轉。我們實現了一種方法，將行轉換為字串並使用content-equal函式。時間複雜度為O(N^3)，空間複雜度為O(N)。其中N是矩陣的行和列的大小。