54. Spiral Matrix

自己写的时候转向的部分用了一个flag，后来发现直接转不就行了。。。有点蠢了

看了一眼论坛的答案，写的比我还蠢，遭不住。

• Time Complexity: O(N)
• Space Complexity: O(N)

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;

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

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[][] a = new boolean[m][n];

        int i = 0;
        int j = 0;
        int index = 0;
        boolean flag = true;
        while (result.size() != m * n) {
            result.add(matrix[i][j]);
            a[i][j] = true;
            int newX = i + dx[index];
            int newY = j + dy[index];
            if (newX < m && newX >= 0 && newY < n && newY >= 0 && !a[newX][newY]) {
                i = newX;
                j = newY;
            } else {
                index = (index + 1) % 4;
                i += dx[index];
                j += dy[index];
            }
        }
        return result;
    }
}

59. Spiral Matrix II

和上一道思路相同，很简单。

class Solution {
    public int[][] generateMatrix(int n) {
        if (n == 0) return new int[0][0];

        int[][] result = new int[n][n];

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

        int i = 0;
        int j = 0;
        int index = 0;
        int cur = 1;
        for (int k = 0; k < n * n; ++k) {
            result[i][j] = cur;
            cur++;
            int newX = i + dx[index];
            int newY = j + dy[index];
            if (newX < n && newX >= 0 && newY < n && newY >= 0 && result[newX][newY] == 0) {
                i = newX;
                j = newY;
            } else {
                index = (index + 1) % 4;
                i += dx[index];
                j += dy[index];
            }
        }
        return result;
    }
}