59. 螺旋矩阵 II

59. 螺旋矩阵 II

方法一：

每次只走一步

判断下一步是否为临界值，如果是，按照预定的的四个方向的顺序进行转变

一个巧妙的点：通过判断下一步是否有值来确定是否是边界，就可以不用记录已走过的边界框

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int data = 1;
        int x = 0, y = 0;
//        int l = 0, r = n - 1, top = 0, bottom = n - 1;
        int[][] step = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dire = 0;
        while(data <= n*n){
            System.out.println(x + ", " + y);
            ans[x][y] = data;
            ++data;
            int stepx = x + step[dire][0];
            int stepy = y + step[dire][1];
            if(stepx < 0 || stepx >= n
                    || stepy < 0 || stepy >= n
                    || ans[stepx][stepy] != 0){
                dire = (dire + 1) % 4;
            }
            x += step[dire][0];
            y += step[dire][1];
        }
        return ans;
    }
}

方法二：

每次都将一个方向的所有步给走完，更新边界值，接着才走向下一个方向

注意：这里必须是 data < maxData, 如果写成 data <= maxData 将选入死循环

因为 data 等于 maxData 后， left, right, top, bottom之间的关系将不再进入四个方向的循环，data的值也不会增加

public class Solution2 {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int data = 0;
        int maxData = n*n;
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        while(data < maxData){
//            System.out.println(top + ", " + right + ", " + bottom + ", " + left);
            for(int y = left; y <= right; ++ y){
                ans[top][y] = ++data;
            }
            ++top;
            for(int x = top; x <= bottom; ++ x){
                ans[x][right] = ++data;
            }
            --right;
            for(int y = right; y >= left; --y){
                ans[bottom][y] = ++data;
            }
            --bottom;
            for(int x = bottom; x >= top; --x){
                ans[x][left] = ++data;
            }
            ++left;
        }
        return ans;
    }
}