[LeetCode] 1886. Determine Whether Matrix Can Be Obtained By Rotation

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:
n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] and target[i][j] are either 0 or 1.

判断矩阵经轮转后是否一致。

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/determine-whether-matrix-can-be-obtained-by-rotation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题给了一个小小的提示顺时针旋转90度，可惜我第一次做的时候没有意识到。其实这道题跟 48 题很像。48 题只是请你把 input matrix 顺时针旋转90度；这道题是请你判断 target 是否有可能是通过将 input matrix 顺时针旋转了若干次而得来的。既然48题我们都可以不用额外空间实现，这道题也可以。我们需要把48题的方法照搬过来，只是每次旋转90度之后都要判断一次，一共判断四次即可。同时注意 target matrix 有可能跟原来的 mat 一样，不需要 rotate。

复杂度

时间O(n^2)
空间O(1)

代码

Java实现

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
class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        for (int i = 0; i < 4; i++) {
            int[][] rotated = helper(mat);
            if (isSame(rotated, target)) {
                return true;
            }
        }
        return false;
    }

    private int[][] helper(int[][] matrix) {
        // 按左上 - 右下对角线交换
        int m = matrix.length;
        for (int i = 0; i < m; i++) {
            for (int j = i; j < m; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 左右对折
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][m - 1 - j];
                matrix[i][m - 1 - j] = temp;
            }
        }
        return matrix;
    }

    private boolean isSame(int[][] a, int[][] b) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] != b[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

同时我也分享一下第一次做的代码，我是把 rotate 过后的结果 matrix 模拟出来了才判断的。细节很不好想，而且容易错。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        // corner case
        if (helper(target, mat)) {
            return true;
        }

        // normal case
        int[][] first = rotateOnce(mat);
        int[][] second = rotateTwice(mat);
        int[][] third = rotateThird(mat);
        if (helper(target, first) || helper(target, second) || helper(target, third)) {
            return true;
        }
        return false;
    }

    private boolean helper(int[][] matrix1, int[][] matrix2) {
        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1[0].length; j++) {
                if (matrix1[i][j] != matrix2[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    // rotate 90
    private int[][] rotateOnce(int[][] mat) {
        int len = mat.length;
        int[][] A = new int[len][len];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                A[j][len - 1 - i] = mat[i][j];
            }
        }
        return A;
    }

    // rotate 180
    private int[][] rotateTwice(int[][] mat) {
        int len = mat.length;
        int[][] B = new int[len][len];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                B[i][j] = mat[len - 1 - i][len - 1 - j];
            }
        }
        return B;
    }

    // rotate 270
    private int[][] rotateThird(int[][] mat) {
        int len = mat.length;
        int[][] C = new int[len][len];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                C[len - 1 - j][i] = mat[i][j];
                // System.out.println("old, i " + i + " j " + j);
                // System.out.println("new, i " + (len - 1 - i) + " j " + (len - 1 - j));
            }
        }
        // for (int i = 0; i < C.length; i++) {
        //     System.out.println(Arrays.toString(C[i]));
        // }
        return C;
    }
}

相关题目

1
2
48. Rotate Image
1886. Determine Whether Matrix Can Be Obtained By Rotation
#leetcode #array #java #matrix
[LeetCode] 1886. Determine Whether Matrix Can Be Obtained By Rotation
https://shurui91.github.io/posts/1631282000.html
Author
Aaron Liu
Posted on
June 17, 2021
Licensed under