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是矩阵的行和列的大小。