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; }