Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7513359

Browse files
committed
Add square matrix rotation in-place algorithm.
1 parent17ad4dc commit7513359

File tree

4 files changed

+178
-0
lines changed

4 files changed

+178
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -116,6 +116,7 @@ a set of rules that precisely define a sequence of operations.
116116
*`B`[Tower of Hanoi](src/algorithms/uncategorized/hanoi-tower)
117117
*`A`[N-Queens Problem](src/algorithms/uncategorized/n-queens)
118118
*`A`[Knight's Tour](src/algorithms/uncategorized/knight-tour)
119+
*`B`[Square Matrix Rotation](src/algorithms/uncategorized/square-matrix-rotation) - in-place algorithm
119120

120121
###Algorithms by Paradigm
121122

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
#Square Matrix In-Place Rotation
2+
3+
##The Problem
4+
5+
You are given an`n x n` 2D matrix (representing an image).
6+
Rotate the matrix by`90` degrees (clockwise).
7+
8+
**Note**
9+
10+
You have to rotate the image**in-place**, which means you
11+
have to modify the input 2D matrix directly.**DO NOT** allocate
12+
another 2D matrix and do the rotation.
13+
14+
##Examples
15+
16+
**Example#1**
17+
18+
Given input matrix:
19+
20+
```
21+
[
22+
[1, 2, 3],
23+
[4, 5, 6],
24+
[7, 8, 9],
25+
]
26+
```
27+
28+
Rotate the input matrix in-place such that it becomes:
29+
30+
```
31+
[
32+
[7, 4, 1],
33+
[8, 5, 2],
34+
[9, 6, 3],
35+
]
36+
```
37+
38+
**Example#2**
39+
40+
Given input matrix:
41+
42+
```
43+
[
44+
[5, 1, 9, 11],
45+
[2, 4, 8, 10],
46+
[13, 3, 6, 7],
47+
[15, 14, 12, 16],
48+
]
49+
```
50+
51+
Rotate the input matrix in-place such that it becomes:
52+
53+
```
54+
[
55+
[15, 13, 2, 5],
56+
[14, 3, 4, 1],
57+
[12, 6, 8, 9],
58+
[16, 7, 10, 11],
59+
]
60+
```
61+
62+
##Algorithm
63+
64+
We would need to do two reflections of the matrix:
65+
66+
- reflect vertically
67+
- reflect diagonally from bottom-left to top-right
68+
69+
Or we also could Furthermore, you can reflect diagonally
70+
top-left/bottom-right and reflect horizontally.
71+
72+
A common question is how do you even figure out what kind
73+
of reflections to do? Simply rip a square piece of paper,
74+
write a random word on it so you know its rotation. Then,
75+
flip the square piece of paper around until you figure out
76+
how to come to the solution.
77+
78+
Here is an example of how first line may be rotated using
79+
diagonal top-right/bottom-left rotation along with horizontal
80+
rotation.
81+
82+
```
83+
A B C A - - . . A
84+
/ / --> B - - --> . . B
85+
/ . . C - - . . C
86+
```
87+
88+
##References
89+
90+
-[LeetCode](https://leetcode.com/problems/rotate-image/description/)
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
importsquareMatrixRotationfrom'../squareMatrixRotation';
2+
3+
describe('squareMatrixRotation',()=>{
4+
it('should rotate matrix #0 in-place',()=>{
5+
constmatrix=[[1]];
6+
7+
constrotatedMatrix=[[1]];
8+
9+
expect(squareMatrixRotation(matrix)).toEqual(rotatedMatrix);
10+
});
11+
12+
it('should rotate matrix #1 in-place',()=>{
13+
constmatrix=[
14+
[1,2],
15+
[3,4],
16+
];
17+
18+
constrotatedMatrix=[
19+
[3,1],
20+
[4,2],
21+
];
22+
23+
expect(squareMatrixRotation(matrix)).toEqual(rotatedMatrix);
24+
});
25+
26+
it('should rotate matrix #2 in-place',()=>{
27+
constmatrix=[
28+
[1,2,3],
29+
[4,5,6],
30+
[7,8,9],
31+
];
32+
33+
constrotatedMatrix=[
34+
[7,4,1],
35+
[8,5,2],
36+
[9,6,3],
37+
];
38+
39+
expect(squareMatrixRotation(matrix)).toEqual(rotatedMatrix);
40+
});
41+
42+
it('should rotate matrix #3 in-place',()=>{
43+
constmatrix=[
44+
[5,1,9,11],
45+
[2,4,8,10],
46+
[13,3,6,7],
47+
[15,14,12,16],
48+
];
49+
50+
constrotatedMatrix=[
51+
[15,13,2,5],
52+
[14,3,4,1],
53+
[12,6,8,9],
54+
[16,7,10,11],
55+
];
56+
57+
expect(squareMatrixRotation(matrix)).toEqual(rotatedMatrix);
58+
});
59+
});
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
*@param {*[][]} originalMatrix
3+
*@return {*[][]}
4+
*/
5+
exportdefaultfunctionsquareMatrixRotation(originalMatrix){
6+
constmatrix=originalMatrix.slice();
7+
8+
// Do top-right/bottom-left diagonal reflection of the matrix.
9+
for(letrowIndex=0;rowIndex<matrix.length;rowIndex+=1){
10+
for(letcolumnIndex=rowIndex+1;columnIndex<matrix.length;columnIndex+=1){
11+
consttmp=matrix[columnIndex][rowIndex];
12+
matrix[columnIndex][rowIndex]=matrix[rowIndex][columnIndex];
13+
matrix[rowIndex][columnIndex]=tmp;
14+
}
15+
}
16+
17+
// Do horizontal reflection of the matrix.
18+
for(letrowIndex=0;rowIndex<matrix.length;rowIndex+=1){
19+
for(letcolumnIndex=0;columnIndex<matrix.length/2;columnIndex+=1){
20+
constmirrorColumnIndex=matrix.length-columnIndex-1;
21+
consttmp=matrix[rowIndex][mirrorColumnIndex];
22+
matrix[rowIndex][mirrorColumnIndex]=matrix[rowIndex][columnIndex];
23+
matrix[rowIndex][columnIndex]=tmp;
24+
}
25+
}
26+
27+
returnmatrix;
28+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp