使用状态机解决两个leetcode螺旋矩阵问题[54,59]

第一题：顺时针输出螺旋矩阵：
螺旋矩阵

在本题中，这个状态就是当前的矩阵坐标和运行方向，而状态的转移遵循题目的限制规则：

1. 顺时针旋转走位，这表示 如果当前是向右行走，那么接下来只能是向右或者向下，如果继续向右不会越界，也不会踩到已经走过的格子，那么就向右，否则就向下。 以此类推。所以很容易得出状态表：

    right: ['right', 'bottom'] //当前方向是right 只能保持right或者转向bottom，据此穷举出状态对应关系 
    bottom: ['bottom', 'left'] //同上...
    left: ['left', 'top']
    top: ['top', 'right']
   

/**
* 状态机存储以下几个信息： 
* 当前的行进方向 curDir 
* 状态转移关系表 STATUS_TABLE
* 当前的坐标 x y  
* 矩阵的宽高 w h 
* 已经走过的格子 viewedTable 是一个二维数组 存储布尔值 
*/
class AutoMachine {
    constructor(w, h, x = -1, y = 0, curDir = 'right') {
        this.viewedTable = new Array(h).fill(0).map(i => new Array(w).fill(false));
        this.w = w;
        this.h = h;
        this.curDir = curDir;
        this.x = x;
        this.y = y;
    }
    //获取下一步的取值坐标
    getNextCord() {
        this.curDir = this.getNextDir();//获取下一步行进的方向
        let { curDir, x, y } = this;
        switch (curDir) {
            case 'left':
                x--;
                break;
            case 'right':
                x++
                break;
            case 'top':
                y--;
                break;
            case 'bottom':
                y++;
                break;
        }
        this.x = x;
        this.y = y;
        this.viewedTable[y][x] = true;//标记这个取值过的坐标
        return [x, y];
    }
    getNextDir() {
        //获取接下来行进的方向
        //通过isRightDir判断当前方向是否还能前进,
        //如果可以继续行进  则维持当前状态  如果不能继续  则切换到下一个状态(转换方向) 
        //状态切换的规则在状态对应表table中定义
        let { curDir, x, y } = this;
        let colIndex;
        if (this.isRightDir(x, y, curDir)) colIndex = 0;
        else colIndex = 1;
        return this.STATUS_TABLE[curDir][colIndex];
    }
    //状态对应表:
    STATUS_TABLE = {
        //由于是顺时针螺旋,很容易得出状态的转移规则: 右 -> 下 -> 左 -> 上  -> 右 ... 
        right: ['right', 'bottom'],
        bottom: ['bottom', 'left'],
        left: ['left', 'top'],
        top: ['top', 'right'],
    };
    isRightDir() {
        //通过探测 判断下一步是否还能沿着当前的方向前进 
        let { w, h, x, y, curDir } = this;
        if (curDir === 'left') x--;
        if (curDir === 'right') x++;
        if (curDir === 'top') y--;
        if (curDir === 'bottom') y++;
        if (x < 0 || x > w - 1 || y < 0 || y > h - 1) return false; //下一步越界了 不应该维持当前方向 返回false
        if (this.viewedTable[y][x]) return false;//下一步会走入已经走过的格子 返回false
        return true;//可以继续行进  返回true
    }
}

var spiralOrder = function (matrix) {
    let x = -1, y = 0;
    //假设我们当前在矩阵的左上角的左边 还未进入矩阵 
    //状态机启动后 由于我们的初始化坐标为 -1,0 方向为right 所以第一个进入的格子就是左上角的格子
    let h = matrix.length;
    if(h === 0) return [];
    let w = matrix[0].length;
    let len = w * h;
    let res = [];
    const AM = new AutoMachine(w, h, x, y,'right');
    while (res.length < len) {
        let [_x, _y] = AM.getNextCord();//状态机自动查找下一个坐标，然后利用坐标取值
        res.push(matrix[_y][_x]);
    }
    return res;
};

//测试用例：
var matrix = [
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
];
console.log( spiralOrder(matrix) ) //输出: [1,2,3,6,9,8,7,4,5]

第二题：顺时针填写矩阵

螺旋矩阵二

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let x = -1, y = 0;
    let h = n;
    let w = n;
    let len = w * h;
    let i = 0;
    let matrix = new Array(h).fill(0).map(i => new Array(w).fill(0));
    const AM = new AutoMachine(w, h, x, y);
    while (i++<len) {
        let [_x, _y] = AM.getNextCord();
        matrix[_y][_x] = i;
    }
    return matrix;
};

状态机解法并不快，但是胜在容易实现和理解，并且可以复用。即使某些题目条件变了，比如说从右下角开始填写，或者逆时针填写，我们仍然不需要修改状态机的代码，只需要改一下初始状态。