Skip to content

Commit 451fa18

Browse files
fishercoder1534fishercoder1534
committed
refactor 48
1 parent c0a45fa commit 451fa18

File tree

3 files changed

+74
-48
lines changed

3 files changed

+74
-48
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -570,7 +570,7 @@ Your ideas/fixes/algorithms are more than welcome!
570570
|51|[N-Queens](https://leetcode.com/problems/n-queens/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_51.java)|O(?)|O(?)|Hard|
571571
|50|[Pow(x, n)](https://leetcode.com/problems/powx-n/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_50.java)|O(logn)|O(logn)|Medium|
572572
|49|[Group Anagrams](https://leetcode.com/problems/group-anagrams/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_49.java)|O(m*logn)|O(m*n)|Medium| HashMap
573-
|48|[Rotate Image](https://leetcode.com/problems/rotate-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_48.java)|O(n^2)|O(1)|Medium|Array
573+
|48|[Rotate Image](https://leetcode.com/problems/rotate-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_48.java)|O(n^2)|O(1)| Medium | Array
574574
|47|[Permutations II](https://leetcode.com/problems/permutations-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_47.java)|O(n*n!)|O(n)|Medium|Backtracking
575575
|46|[Permutations](https://leetcode.com/problems/permutations/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_46.java)|O(n*n!)|O(n)|Medium|Backtracking
576576
|45|[Jump Game II](https://leetcode.com/problems/jump-game-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_45.java)|O(?)|O(?)|Hard|

‎src/main/java/com/fishercoder/solutions/_48.java

Lines changed: 55 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -12,57 +12,68 @@
1212
*/
1313
public class _48 {
1414

15-
public void rotate_O1(int[][] matrix) {
16-
/**First swap the elements on the diagonal, then reverse each row:
17-
* 1, 2, 3 1, 4, 7 7, 4, 1
18-
* 4, 5, 6 becomes 2, 5, 8 becomes 8, 5, 2
19-
* 7, 8, 9 3, 6, 9 9, 6, 3
20-
This is done in O(1) space!
21-
**/
22-
int m = matrix.length;
23-
int n = matrix[0].length;
24-
for (int i = 0; i < m; i++) {
25-
for (int j = i; j < n; j++) {
26-
/**ATTN: j starts from i, so that the diagonal changes with itself, no change.*/
27-
int tmp = matrix[i][j];
28-
matrix[i][j] = matrix[j][i];
29-
matrix[j][i] = tmp;
15+
/**Note: this is an n*n matrix, in other words, it's a square, this makes it easier as well.*/
16+
17+
public static class Solution1 {
18+
public void rotate(int[][] matrix) {
19+
/**First swap the elements on the diagonal, then reverse each row:
20+
* 1, 2, 3 1, 4, 7 7, 4, 1
21+
* 4, 5, 6 becomes 2, 5, 8 becomes 8, 5, 2
22+
* 7, 8, 9 3, 6, 9 9, 6, 3
23+
This is done in O(1) space!
24+
**/
25+
int m = matrix.length;
26+
for (int i = 0; i < m; i++) {
27+
for (int j = i; j < m; j++) {
28+
/**ATTN: j starts from i, so that the diagonal changes with itself, results in no change.*/
29+
int tmp = matrix[i][j];
30+
matrix[i][j] = matrix[j][i];
31+
matrix[j][i] = tmp;
32+
}
3033
}
31-
}
3234

33-
for (int i = 0; i < m; i++) {
34-
for (int j = 0; j < n / 2; j++) {
35-
int tmp = matrix[i][j];
36-
matrix[i][j] = matrix[i][n - 1 - j];
37-
matrix[i][n - 1 - j] = tmp;
35+
/**then reverse*/
36+
for (int i = 0; i < m; i++) {
37+
int left = 0;
38+
int right = m - 1;
39+
while (left < right) {
40+
int tmp = matrix[i][left];
41+
matrix[i][left] = matrix[i][right];
42+
matrix[i][right] = tmp;
43+
left++;
44+
right--;
45+
}
3846
}
3947
}
4048
}
4149

42-
/**First swap the rows bottom up, then swap the element on the diagonal:
43-
* 1, 2, 3 7, 8, 9 7, 4, 1
44-
* 4, 5, 6 becomes 4, 5, 6 becomes 8, 5, 2
45-
* 7, 8, 9 1, 2, 3 9, 6, 3
46-
* */
47-
/**This is using O(n) of extra space*/
48-
public void rotate_On(int[][] matrix) {
49-
int m = matrix.length;
50-
int n = matrix[0].length;
51-
int top = 0;
52-
int bottom = n - 1;
53-
while (top < bottom) {
54-
int[] tmp = matrix[top];
55-
matrix[top] = matrix[bottom];
56-
matrix[bottom] = tmp;
57-
top++;
58-
bottom--;
59-
}
50+
public static class Solution2 {
51+
/**First swap the rows bottom up, then swap the element on the diagonal:
52+
* 1, 2, 3 7, 8, 9 7, 4, 1
53+
* 4, 5, 6 becomes 4, 5, 6 becomes 8, 5, 2
54+
* 7, 8, 9 1, 2, 3 9, 6, 3
55+
*
56+
* This is using O(n) of extra space
57+
*/
58+
public void rotate(int[][] matrix) {
59+
int m = matrix.length;
60+
int n = matrix[0].length;
61+
int top = 0;
62+
int bottom = n - 1;
63+
while (top < bottom) {
64+
int[] tmp = matrix[top];
65+
matrix[top] = matrix[bottom];
66+
matrix[bottom] = tmp;
67+
top++;
68+
bottom--;
69+
}
6070

61-
for (int i = 0; i < m; i++) {
62-
for (int j = i + 1; j < n; j++) {
63-
int tmp = matrix[i][j];
64-
matrix[i][j] = matrix[j][i];
65-
matrix[j][i] = tmp;
71+
for (int i = 0; i < m; i++) {
72+
for (int j = i + 1; j < n; j++) {
73+
int tmp = matrix[i][j];
74+
matrix[i][j] = matrix[j][i];
75+
matrix[j][i] = tmp;
76+
}
6677
}
6778
}
6879
}

‎src/test/java/com/fishercoder/_48Test.java

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
package com.fishercoder;
22

3+
import com.fishercoder.common.utils.CommonUtils;
34
import com.fishercoder.solutions._48;
45
import org.junit.BeforeClass;
56
import org.junit.Test;
@@ -8,12 +9,14 @@
89
* Created by fishercoder on 5/8/17.
910
*/
1011
public class _48Test {
11-
private static _48 test;
12+
private static _48.Solution1 solution1;
13+
private static _48.Solution2 solution2;
1214
private static int[][] matrix;
1315

1416
@BeforeClass
1517
public static void setup() {
16-
test = new _48();
18+
solution1 = new _48.Solution1();
19+
solution2 = new _48.Solution2();
1720
}
1821

1922
@Test
@@ -23,6 +26,18 @@ public void test1() {
2326
{4, 5, 6},
2427
{7, 8, 9},
2528
};
26-
test.rotate_On(matrix);
29+
solution1.rotate(matrix);
30+
CommonUtils.print2DIntArray(matrix);
31+
}
32+
33+
@Test
34+
public void test2() {
35+
matrix = new int[][]{
36+
{1, 2, 3},
37+
{4, 5, 6},
38+
{7, 8, 9},
39+
};
40+
solution2.rotate(matrix);
41+
CommonUtils.print2DIntArray(matrix);
2742
}
2843
}

0 commit comments

Comments
 (0)