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