Array
Matrix
Simulation
Description
You are given an m x n
integer matrix grid
, where m
and n
are both even integers, and an integer k
.
The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:
A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:
Return the matrix after applying k
cyclic rotations to it .
Example 1:
Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.
Example 2:
Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.
Constraints:
m == grid.length
n == grid[i].length
2 <= m, n <= 50
Both m
and n
are even integers.
1 <= grid[i][j] <= 5000
1 <= k <= 109
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 class Solution :
def rotateGrid ( self , grid : List [ List [ int ]], k : int ) -> List [ List [ int ]]:
def rotate ( p : int , k : int ):
nums = []
for j in range ( p , n - p - 1 ):
nums . append ( grid [ p ][ j ])
for i in range ( p , m - p - 1 ):
nums . append ( grid [ i ][ n - p - 1 ])
for j in range ( n - p - 1 , p , - 1 ):
nums . append ( grid [ m - p - 1 ][ j ])
for i in range ( m - p - 1 , p , - 1 ):
nums . append ( grid [ i ][ p ])
k %= len ( nums )
if k == 0 :
return
nums = nums [ k :] + nums [: k ]
k = 0
for j in range ( p , n - p - 1 ):
grid [ p ][ j ] = nums [ k ]
k += 1
for i in range ( p , m - p - 1 ):
grid [ i ][ n - p - 1 ] = nums [ k ]
k += 1
for j in range ( n - p - 1 , p , - 1 ):
grid [ m - p - 1 ][ j ] = nums [ k ]
k += 1
for i in range ( m - p - 1 , p , - 1 ):
grid [ i ][ p ] = nums [ k ]
k += 1
m , n = len ( grid ), len ( grid [ 0 ])
for p in range ( min ( m , n ) >> 1 ):
rotate ( p , k )
return grid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 class Solution {
private int m ;
private int n ;
private int [][] grid ;
public int [][] rotateGrid ( int [][] grid , int k ) {
m = grid . length ;
n = grid [ 0 ] . length ;
this . grid = grid ;
for ( int p = 0 ; p < Math . min ( m , n ) / 2 ; ++ p ) {
rotate ( p , k );
}
return grid ;
}
private void rotate ( int p , int k ) {
List < Integer > nums = new ArrayList <> ();
for ( int j = p ; j < n - p - 1 ; ++ j ) {
nums . add ( grid [ p ][ j ] );
}
for ( int i = p ; i < m - p - 1 ; ++ i ) {
nums . add ( grid [ i ][ n - p - 1 ] );
}
for ( int j = n - p - 1 ; j > p ; -- j ) {
nums . add ( grid [ m - p - 1 ][ j ] );
}
for ( int i = m - p - 1 ; i > p ; -- i ) {
nums . add ( grid [ i ][ p ] );
}
int l = nums . size ();
k %= l ;
if ( k == 0 ) {
return ;
}
for ( int j = p ; j < n - p - 1 ; ++ j ) {
grid [ p ][ j ] = nums . get ( k ++ % l );
}
for ( int i = p ; i < m - p - 1 ; ++ i ) {
grid [ i ][ n - p - 1 ] = nums . get ( k ++ % l );
}
for ( int j = n - p - 1 ; j > p ; -- j ) {
grid [ m - p - 1 ][ j ] = nums . get ( k ++ % l );
}
for ( int i = m - p - 1 ; i > p ; -- i ) {
grid [ i ][ p ] = nums . get ( k ++ % l );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 class Solution {
public :
vector < vector < int >> rotateGrid ( vector < vector < int >>& grid , int k ) {
int m = grid . size (), n = grid [ 0 ]. size ();
auto rotate = [ & ]( int p , int k ) {
vector < int > nums ;
for ( int j = p ; j < n - p - 1 ; ++ j ) {
nums . push_back ( grid [ p ][ j ]);
}
for ( int i = p ; i < m - p - 1 ; ++ i ) {
nums . push_back ( grid [ i ][ n - p - 1 ]);
}
for ( int j = n - p - 1 ; j > p ; -- j ) {
nums . push_back ( grid [ m - p - 1 ][ j ]);
}
for ( int i = m - p - 1 ; i > p ; -- i ) {
nums . push_back ( grid [ i ][ p ]);
}
int l = nums . size ();
k %= l ;
if ( k == 0 ) {
return ;
}
for ( int j = p ; j < n - p - 1 ; ++ j ) {
grid [ p ][ j ] = nums [ k ++ % l ];
}
for ( int i = p ; i < m - p - 1 ; ++ i ) {
grid [ i ][ n - p - 1 ] = nums [ k ++ % l ];
}
for ( int j = n - p - 1 ; j > p ; -- j ) {
grid [ m - p - 1 ][ j ] = nums [ k ++ % l ];
}
for ( int i = m - p - 1 ; i > p ; -- i ) {
grid [ i ][ p ] = nums [ k ++ % l ];
}
};
for ( int p = 0 ; p < min ( m , n ) / 2 ; ++ p ) {
rotate ( p , k );
}
return grid ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 func rotateGrid ( grid [][] int , k int ) [][] int {
m , n := len ( grid ), len ( grid [ 0 ])
rotate := func ( p , k int ) {
nums := [] int {}
for j := p ; j < n - p - 1 ; j ++ {
nums = append ( nums , grid [ p ][ j ])
}
for i := p ; i < m - p - 1 ; i ++ {
nums = append ( nums , grid [ i ][ n - p - 1 ])
}
for j := n - p - 1 ; j > p ; j -- {
nums = append ( nums , grid [ m - p - 1 ][ j ])
}
for i := m - p - 1 ; i > p ; i -- {
nums = append ( nums , grid [ i ][ p ])
}
l := len ( nums )
k %= l
if k == 0 {
return
}
for j := p ; j < n - p - 1 ; j ++ {
grid [ p ][ j ] = nums [ k ]
k = ( k + 1 ) % l
}
for i := p ; i < m - p - 1 ; i ++ {
grid [ i ][ n - p - 1 ] = nums [ k ]
k = ( k + 1 ) % l
}
for j := n - p - 1 ; j > p ; j -- {
grid [ m - p - 1 ][ j ] = nums [ k ]
k = ( k + 1 ) % l
}
for i := m - p - 1 ; i > p ; i -- {
grid [ i ][ p ] = nums [ k ]
k = ( k + 1 ) % l
}
}
for i := 0 ; i < m / 2 && i < n / 2 ; i ++ {
rotate ( i , k )
}
return grid
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 function rotateGrid ( grid : number [][], k : number ) : number [][] {
const m = grid . length ;
const n = grid [ 0 ]. length ;
const rotate = ( p : number , k : number ) => {
const nums : number [] = [];
for ( let j = p ; j < n - p - 1 ; ++ j ) {
nums . push ( grid [ p ][ j ]);
}
for ( let i = p ; i < m - p - 1 ; ++ i ) {
nums . push ( grid [ i ][ n - p - 1 ]);
}
for ( let j = n - p - 1 ; j > p ; -- j ) {
nums . push ( grid [ m - p - 1 ][ j ]);
}
for ( let i = m - p - 1 ; i > p ; -- i ) {
nums . push ( grid [ i ][ p ]);
}
const l = nums . length ;
k %= l ;
if ( k === 0 ) {
return ;
}
for ( let j = p ; j < n - p - 1 ; ++ j ) {
grid [ p ][ j ] = nums [ k ++ % l ];
}
for ( let i = p ; i < m - p - 1 ; ++ i ) {
grid [ i ][ n - p - 1 ] = nums [ k ++ % l ];
}
for ( let j = n - p - 1 ; j > p ; -- j ) {
grid [ m - p - 1 ][ j ] = nums [ k ++ % l ];
}
for ( let i = m - p - 1 ; i > p ; -- i ) {
grid [ i ][ p ] = nums [ k ++ % l ];
}
};
for ( let p = 0 ; p < Math . min ( m , n ) >> 1 ; ++ p ) {
rotate ( p , k );
}
return grid ;
}
GitHub