C++程序 检查矩阵的所有行是否是彼此的循环旋转
给定一个n * n大小的矩阵,任务是找到所有行是否彼此的循环旋转。
示例:
输入 :mat [][] = 1, 2, 3
3, 1, 2
2, 3, 1
输出值 : 是的,所有行都是彼此旋转的排列。
输入 :mat [3] [3] = 1, 2, 3
3, 2, 1
1, 3, 2
输出 : 不是的,因为3,2,1不是1,2,3的旋转或循环排列。
这个想法基于下面的文章。
检查字符串是否相互旋转的程序
步骤:
- 创建第一行元素的字符串,并将字符串与自身连接,以便可以高效地执行字符串搜索操作。让这个字符串成为str_cat。
- 遍历所有剩余的行。对于正在遍历的每行,创建当前行元素的字符串str_curr。如果str_curr不是str_cat的子字符串,则返回false。
- 返回true。
下面是上述步骤的实现。
// C++ program to check if all rows of a matrix
// are rotations of each other
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Returns true if all rows of mat[0..n-1][0..n-1]
// are rotations of each other.
bool isPermutedMatrix( int mat[MAX][MAX], int n)
{
// Creating a string that contains elements of first
// row.
string str_cat = "";
for (int i = 0 ; i < n ; i++)
str_cat = str_cat + "-" + to_string(mat[0][i]);
// Concatenating the string with itself so that
// substring search operations can be performed on
// this
str_cat = str_cat + str_cat;
// Start traversing remaining rows
for (int i=1; i<n; i++)
{
// Store the matrix into vector in the form
// of strings
string curr_str = "";
for (int j = 0 ; j < n ; j++)
curr_str = curr_str + "-" + to_string(mat[i][j]);
// Check if the current string is present in
// the concatenated string or not
if (str_cat.find(curr_str) == string::npos)
return false;
}
return true;
}
// Drivers code
int main()
{
int n = 4 ;
int mat[MAX][MAX] = {{1, 2, 3, 4},
{4, 1, 2, 3},
{3, 4, 1, 2},
{2, 3, 4, 1}
};
isPermutedMatrix(mat, n)? cout << "Yes" :
cout << "No";
return 0;
}
输出值:
Yes
时间复杂度: O(n 3 )
辅助空间: O(n)