Spiral Order Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Given n = 3,

You should return the following matrix:

[
  [ 1, 2, 3 ],
  [ 8, 9, 4 ],
  [ 7, 6, 5 ]
]
思路:

我是用OO的思想来做,从1开始到n^2,一个一个fill in,遇到out of bound或者已经fill in的位置就change direction。

Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    private static class Pair {
        int x;
        int y;
       
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
   
    private static class Dir extends Pair {
        public Dir(int x, int y) {
            super(x, y);
        }
    }
   
    public ArrayList<ArrayList<Integer>> generateMatrix(int A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int n = A;
        for (int i = 0; i < n; i ++) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j ++) {
                row.add(0);
            }
            result.add(row);
        }
        int nSquared = n * n;
        int v = 1;
        Dir d = new Dir(0, 1);
        Pair p = new Pair(0, 0);
        while (v <= nSquared) {
            fillInNumber(v++, result, d, p);
        }
        return result;
    }
   
    private void fillInNumber(int v, ArrayList<ArrayList<Integer>> matrix, Dir d, Pair p) {
        matrix.get(p.x).set(p.y, v);
        changeDir(d, p, matrix);
        changeNextPair(d, p);
    }
   
    private void changeDir(Dir curr, Pair p, ArrayList<ArrayList<Integer>> matrix) {
        int n = matrix.size();
        int nextX = p.x + curr.x;
        int nextY = p.y + curr.y;
        if (curr.x == 0 && curr.y == 1) {
            if (nextY >= n || matrix.get(nextX).get(nextY) != 0) {
                curr.x = 1;
                curr.y = 0;
            }
        } else if (curr.x == 1 && curr.y == 0) {
            if (nextX >= n || matrix.get(nextX).get(nextY) != 0) {
                curr.x = 0;
                curr.y = -1;
            }
        } else if (curr.x == 0 && curr.y == -1) {
            if (nextY < 0 || matrix.get(nextX).get(nextY) != 0) {
                curr.x = -1;
                curr.y = 0;
            }
        } else {
            if (nextX < 0 || matrix.get(nextX).get(nextY) != 0) {
                curr.x = 0;
                curr.y = 1;
            }
        }
    }
   
    private void changeNextPair(Dir d, Pair p) {
        p.x = p.x + d.x;
        p.y = p.y + d.y;
    }
}