PHP程序：检查矩阵的所有行是否彼此循环旋转

---

矩阵是一个由行和列组成的矩形数组。循环旋转是指旋转数组的元素，使得旋转一次后，最后一个元素位于第一个位置，其他元素向右移动。在本题中，我们给定一个N*N矩阵，我们的目标是确定所有行是否彼此循环旋转。如果是，则打印“YES”，否则打印“NO”。

为了更好地理解这个问题，让我们看一些带有解释的案例。

输入1

mat = [ [ 7, 8, 9],
      [ 9, 7, 8],
      [ 8, 9, 7] ]

输出1

YES

解释

将第一行视为给定数组 [7, 8, 9]，现在检查其余行 [9, 7, 8] 和 [8, 9, 7]

第二行 [9, 7, 8] 的旋转是：[8, 9, 7] 和 [7, 8, 9]

第二次旋转与第一行匹配。

第三行 [8, 9, 7] 的旋转是：[7, 8, 9] 和 [9, 7, 8]

第一次旋转与第一行匹配。

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

输入2

mat = [ [ 8, 9, 4],
      [ 9, 8, 4] ]

输出2

NO

解释

将第一行视为给定数组 [8, 9, 4]，现在检查其余行 [9, 8, 4]

第二行 [9, 8, 4] 的旋转是：[4, 9, 8] 和 [8, 4, 9]

它们都不等于第一行。

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

方法

我们已经看到了上面给定大小为 N*N 的矩阵的示例，让我们来看一下方法

方法1：朴素方法

此方法背后的概念是将第一行存储为字符串，然后将其自身与自身组合，以便用于子串搜索操作。然后，遍历矩阵以检查其他行。将每一行转换为字符串后，检查它是否是第一行字符串的子串。如果是，则返回true；否则，返回false。

为了进一步理解上述方法，让我们看下面的代码。

示例

PHP程序：检查矩阵的所有行是否彼此循环旋转

<?php
//Create a Function to check every row are circular rotations to each other or not.
function circularRotations( &$mat, $n){
   // Making a string that contains 
   // the first row's integers.
   $strFirstRow = "";    
   // Traverse the matrix to store the first row as a string
   for ($i = 0 ; $i < $n ; $i++) {
      // add the first row numbers to the variable strFirstRow
      $strFirstRow = $strFirstRow . "-" .
         strval($mat[0][$i]);
   } 
   // Combining the string 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 ($i = 1; $i < $n; $i++){
      // Creating variable strCurrentRow and intialize it
      $strCurrentRow = "";       
      // Traverse the curret row
      for ($j = 0 ; $j < $n ; $j++) {
         // Store current rows number to the variable strCurrentRow
         $strCurrentRow = $strCurrentRow . "-" . strval($mat[$i][$j]);
      }
      // Verify whether the combining string strFirstRow contains the strCurrentRow string or not.
      if (strpos($strFirstRow, $strCurrentRow)){
         // Returns true if every row of given matrix are circular rotations of one another.
         return true;
      }
   }
   // If none of the specified matrix's rows are circular rotations of one another the function returns false.
   return false;
}
$n = 4; // Given size of the matrix
// Given matrix
$mat = array(array(6, 7, 8, 9),
            array(9, 6, 7, 8),
            array(8, 9, 6, 7),
            array(7, 8, 9, 6));       
// call function to check all rows of matrix are circular rotations of each other or not
if (circularRotations($mat, $n)){
   echo "YES";
   echo ", all rows of the matrix are circular rotations of each 
other";
} else{
   echo "NO";
   echo ", 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)，因为我们遍历矩阵并使用 strval 和 strpos 函数。

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

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

结论

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