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)，因为我们要遍历矩阵并使用内容相等的函数。

以上代码的空间复杂度是O(N)，因为我们需要将矩阵的行存储为字符串。

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

结论

在本教程中，我们已经实现了一个Java程序，用于检查矩阵的所有行是否互为循环旋转。我们实现了一种将行转换为字符串并使用内容相等函数的方法。时间复杂度为O(N^3)，空间复杂度为O(N)。其中N是矩阵的行和列的大小。