54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

---

比较直接的写法

代码的逻辑比较直接, 用direction来控制方向:

1. 0 代表 left to right
2. 1 代表 top to bottom
3. 2 代表 right to
4. 1 代表 top to bottom

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

    int m = matrix.length;
    int n = matrix[0].length;
    int i = 0, j = 0;
    int left = 0, right = n - 1, top = 0, bottom = m - 1;
    int direction = 0;

    while (ans.size() != m * n) {
        ans.add(matrix[i][j]);
        if (direction == 0) {
            // left to right
            if (j == right) {
                i++;
                direction = 1;
                top++;
            } else
                j++;
        } else if (direction == 1) {
            // top to bottom
            if (i == bottom) {
                j--;
                direction = 2;
                right--;
            } else
                i++;
        } else if (direction == 2) {
            // right to left
            if (j == left) {
                i--;
                direction = 3;
                bottom--;
            } else
                j--;
        } else {
            // bottom to top
            if (i == top) {
                j++;
                direction = 0;
                left++;
            } else
                i--;
        }
    }
    return ans;
}

State Desing Patterns

感觉这个题目的意思跟Sate模式比较符合, 就用State模式重写了一遍, 就当熟悉一下设计模式吧.

当然时间效率上不如上面一个好.

class Context {
    private State state;
    int[][] matrix;
    public int left, right, top, bottom;
    public int i, j;

    public Context(int[][] matrix) {
        this.state = new Right();
        this.matrix = matrix;
        i = 0;
        j = 0;
        left = 0;
        top = 0;
        bottom = matrix == null ? -1 : matrix.length - 1;
        right = (matrix == null || matrix.length == 0 || matrix[0] == null) ? -1 : matrix[0].length - 1;
    }

    public int next() {
        return state.next(this);
    }

    public void setState(State state) {
        this.state = state;
    }

    public int getCurrent() {
        return matrix[i][j];
    }

    public boolean hasNext() {
        return j >= left && j <= right && i >= top && i <= bottom;
    }
}

abstract class State {
    public abstract int next(Context context);
}

class Right extends State {
    @Override
    public int next(Context context) {
        int ans = context.getCurrent();
        if (context.j == context.right) {
            context.i++;
            context.top++;
            context.setState(new Bottom());
        } else {
            context.j++;
        }
        return ans;
    }
}

class Bottom extends State {
    @Override
    public int next(Context context) {
        int ans = context.getCurrent();
        if (context.i == context.bottom) {
            context.j--;
            context.right--;
            context.setState(new Left());
        } else {
            context.i++;
        }
        return ans;
    }
}

class Left extends State {
    @Override
    public int next(Context context) {
        int ans = context.getCurrent();
        if (context.j == context.left) {
            context.i--;
            context.bottom--;
            context.setState(new Top());
        } else {
            context.j--;
        }
        return ans;
    }
}

class Top extends State {
    @Override
    public int next(Context context) {
        int ans = context.getCurrent();
        if (context.i == context.top) {
            context.j++;
            context.left++;
            context.setState(new Right());
        } else {
            context.i--;
        }
        return ans;
    }
}

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    Context context = new Context(matrix);

    while (context.hasNext()) {
        ans.add(context.next());
    }
    return ans;
}