LeetCode54: 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/spiral-matrix

• 解法思想：想象为撞墙，如果撞墙，那么direction就转90度。撞墙对应着题目里的三种情况，x越界，y越界或者坐标[x,y]已经被访问过。
• 具体实现：注意HashSet的contains方法需要类中重写equals和hashCode方法

package leetcode;

import java.util.*;

public class SpiralOrder {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    class Node {
        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return x == node.x &&
                    y == node.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int x = 0, y = 0;
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;
        Set<Node> nodes = new HashSet<>();
        int n = matrix.length * matrix[0].length;
        int idx = 1;
        int direction = 0;
        result.add(matrix[x][y]);
        nodes.add(new Node(x, y));
        while (idx < n) {
            int tmpX = x + dx[direction];
            int tmpY = y + dy[direction];
            if (nodes.contains(new Node(tmpX, tmpY)) || tmpX < 0 || tmpX >= matrix.length || tmpY < 0 || tmpY >= matrix[0].length) {
                direction = (direction + 1) % 4;
            } else {
                x = tmpX;
                y = tmpY;
                idx++;
                result.add(matrix[x][y]);
                nodes.add(new Node(x, y));
            }

        }
        return result;
    }
}

• 可以直接开一个boolean数组记录有没有被访问过，不需要用hashSet..

package leetcode;

import java.util.*;

public class SpiralOrder {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public List<Integer> spiralOrder(int[][] matrix) {
        int x = 0, y = 0;
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;
        boolean[][] flag = new boolean[matrix.length][matrix[0].length];
        int n = matrix.length * matrix[0].length;
        int idx = 1;
        int direction = 0;
        result.add(matrix[x][y]);
        flag[x][y] = true;
        while (idx < n) {
            int tmpX = x + dx[direction];
            int tmpY = y + dy[direction];
            if (tmpX < 0 || tmpX >= matrix.length || tmpY < 0 || tmpY >= matrix[0].length || flag[tmpX][tmpY]) {
                direction = (direction + 1) % 4;
            } else {
                x = tmpX;
                y = tmpY;
                idx++;
                result.add(matrix[x][y]);
                flag[x][y] = true;
            }

        }
        return result;
    }
}