当我陷入困境时,我正在解决HackerRank上的问题。
问题陈述
您将获得一个二维矩阵a,尺寸为MxN和一个正整数R。您必须旋转矩阵R次并打印所得矩阵。旋转应为逆时针方向。
下图表示4x5矩阵的旋转。请注意,旋转一圈时,只需将元素移动一级(请参阅样本测试以获取更多清晰度)。
保证M和N的最小值是偶数。
输入值
第一行包含三个以空格分隔的整数M,N和R,其中M是行数,N是矩阵中的列数,R是矩阵必须旋转的次数。然后是M行,每行包含N个空格分隔的正整数。这些M线代表矩阵。
输出量
打印旋转的矩阵。
约束条件
2 <= M, N <= 300
1 <= R <= 10^9
min(M, N) % 2 == 0
1 <= aij <= 108, where i ∈ [1..M] & j ∈ [1..N]'
我试图做的是将圆存储在一维数组中。这样的事情。
while(true)
{
k = 0;
for(int j = left; j <= right; ++j) {temp[k] = a[top][j]; ++k;}
top++;
if(top > down || left > right) break;
for(int i = top; i <= down; ++i) {temp[k] = a[i][right]; ++k;}
right--;
if(top > down || left > right) break;
for(int j = right; j >= left; --j) {temp[k] = a[down][j] ; ++k;}
down--;
if(top > down || left > right) break;
for(int i = down; i >= top; --i) {temp[k] = a[i][left]; ++k;}
left++;
if(top > down || left > right) break;
}
然后,我可以通过计算一维矩阵的长度模R轻松地旋转一维矩阵。但是然后我如何将其放回矩阵形式呢?再次使用循环可能会导致超时。
请不要提供代码,而只能提供建议。我想自己做。
解决方案已创建:
#include <iostream>
using namespace std;
int main() {
int m,n,r;
cin>>m>>n>>r;
int a[300][300];
for(int i = 0 ; i < m ; ++i){
for(int j = 0; j < n ; ++j)
cin>>a[i][j];
}
int left = 0;
int right = n-1;
int top = 0;
int down = m-1;
int tleft = 0;
int tright = n-1;
int ttop = 0;
int tdown = m-1;
int b[300][300];
int k,size;
int temp[1200];
while(true){
k=0;
for(int i = left; i <= right ; ++i)
{
temp[k] = a[top][i];
// cout<<temp[k]<<" ";
++k;
}
++top;
if(top > down || left > right)
break;
for(int i = top; i <= down ; ++i)
{
temp[k]=a[i][right];
// cout<<temp[k]<<" ";
++k;
}
--right;
if(top > down || left > right)
break;
for(int i = right; i >= left ; --i)
{
temp[k] = a[down][i];
// cout<<temp[k]<<" ";
++k;
}
--down;
if(top > down || left > right)
break;
for(int i = down; i >= top ; --i)
{
temp[k] = a[i][left];
// cout<<temp[k]<<" ";
++k;
}
++left;
if(top > down || left > right)
break;
//________________________________\\
size = k;
k=0;
// cout<<size<<endl;
for(int i = tleft; i <= tright ; ++i)
{
b[ttop][i] = temp[(k + (r%size))%size];
// cout<<(k + (r%size))%size<<" ";
// int index = (k + (r%size))%size;
// cout<<index;
++k;
}
++ttop;
for(int i = ttop; i <= tdown ; ++i)
{
b[i][tright]=temp[(k + (r%size))%size];
++k;
}
--tright;
for(int i = tright; i >= tleft ; --i)
{
b[tdown][i] = temp[(k + (r%size))%size];
++k;
}
--tdown;
for(int i = tdown; i >= ttop ; --i)
{
b[i][tleft] = temp[(k + (r%size))%size];
++k;
}
++tleft;
}
size=k;
k=0;
if(top != ttop){
for(int i = tleft; i <= tright ; ++i)
{
b[ttop][i] = temp[(k + (r%size))%size];
++k;
}
++ttop;
}
if(right!=tright){
for(int i = ttop; i <= tdown ; ++i)
{
b[i][tright]=temp[(k + (r%size))%size];
++k;
}
--tright;
}
if(down!=tdown){
for(int i = tright; i >= tleft ; --i)
{
b[tdown][i] = temp[(k + (r%size))%size];
++k;
}
--tdown;
}
if(left!=tleft){
for(int i = tdown; i >= ttop ; --i)
{
b[i][tleft] = temp[(k + (r%size))%size];
++k;
}
++tleft;
}
for(int i = 0 ; i < m ;++i){
for(int j = 0 ; j < n ;++j)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
您需要解决这个问题(让我想起gg和fb的采访问题):
让我们考虑一个长度数组的情况,该数组L
需要旋转R
时间。注意,如果R
是的倍数L
,则数组将保持不变。x
还要注意,向右旋转的时间与向左旋转的时间相同L - x
(反之亦然)。
R
向左旋转时间到向左旋转R modulo L
的问题R modulo L
向左旋转到向左旋转R modulo L
或向右旋转的问题L - R modulo L
。这意味着,如果您有100个元素,并且必须向左旋转99个,则最好向右旋转1个并对其进行处理。因此复杂度将为O(圈数x圈长x单次旋转成本)
阵列就位意味着 O( min(N,m) * (N * M)^2 )
如果您使用双向链表作为临时存储,则通过移除前部并将其放在尾部来完成单个旋转序列(反之亦然,以向右旋转)。因此,您可以做的是先将所有数据复制到链接列表中。运行单R modulo L
次旋转算法次数,复制回环位置上的链表,然后向右移直到处理完所有环。
ring
资料至清单为O(L), L <= N*M
R modulo L
为O(L)
min(N,m) rings
使用备用的双链表,这意味着 O( min(N,m) * (N * M))
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句